Heap & Priority Queue Pattern Guide for LeetCode

1. Core Heap Templates

Template 1: Basic Heap Operations

import heapq

# Min Heap
class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, val):
        heapq.heappush(self.heap, val)

    def pop(self):
        return heapq.heappop(self.heap) if self.heap else None

    def peek(self):
        return self.heap[0] if self.heap else None

# Max Heap (using negatives)
class MaxHeap:
    def __init__(self):
        self.heap = []

    def push(self, val):
        heapq.heappush(self.heap, -val)

    def pop(self):
        return -heapq.heappop(self.heap) if self.heap else None

    def peek(self):
        return -self.heap[0] if self.heap else None

Template 2: K-th Element Pattern

def kth_element_template(nums, k):
    # For kth largest: use min heap of size k
    heap = []

    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        else:
            if num > heap[0]:
                heapq.heapreplace(heap, num)

    return heap[0]

Template 3: Two-Heap Pattern

class MedianFinder:
    def __init__(self):
        self.small = []  # max heap for smaller half
        self.large = []  # min heap for larger half

    def addNum(self, num: int) -> None:
        if len(self.small) == len(self.large):
            heapq.heappush(self.large, -heapq.heappushpop(self.small, -num))
        else:
            heapq.heappush(self.small, -heapq.heappushpop(self.large, num))

2. LeetCode Problem Categories

Category 1: K-th Element Problems

1. LeetCode 215: Kth Largest Element

def findKthLargest(nums: List[int], k: int) -> int:
    heap = []

    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)

    return heap[0]

1. LeetCode 703: Kth Largest Element in Stream

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = []
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

Category 2: Merge Problems

1. LeetCode 23: Merge K Sorted Lists

def mergeKLists(lists: List[ListNode]) -> ListNode:
    heap = []
    dummy = ListNode(0)
    curr = dummy

    # Add first element from each list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))

    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next

        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

1. LeetCode 373: Find K Pairs with Smallest Sums

Category 3: Continuous Stream Median

1. LeetCode 295: Find Median from Data Stream