Heap / Priority Queue Pattern: Template + 163 LeetCode Problems

What the heap / priority queue pattern is

A heap gives you the smallest element in constant time and maintains that promise through inserts and removals in logarithmic time, without ever fully sorting anything — which is the whole saving. For top-k questions, keep a min-heap capped at size k: push every element, pop whenever the heap grows past k, and the smallest survivor is the kth largest. That is O(n log k) against O(n log n) for a sort, and it works on a stream whose length you do not know. Python's heapq is min-only, so a max-heap is built by pushing negated values, and tuples are compared element by element — which is how you order by a key while carrying a payload, and also how you accidentally crash when the payload is a type that cannot be compared and two keys tie. The two-heap arrangement is worth memorising separately: a max-heap of the lower half against a min-heap of the upper half, rebalanced so their sizes differ by at most one, keeps the median at the tops.

When to use it

• —You need the k largest, k smallest, or k closest — and k is much smaller than n.
• —Elements arrive as a stream and the answer must stay current without re-sorting.
• —A scheduling or simulation loop always processes the currently cheapest or earliest item.
• —Dijkstra's algorithm, or any BFS where edges carry weights.
• —A running median is required, which is the two-heap arrangement.

The heap / priority queue template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 163 problems listed below.

import heapq

def k_largest(nums, k):
    heap = []                       # min-heap holding the k best seen so far
    for value in nums:
        heapq.heappush(heap, value)
        if len(heap) > k:
            heapq.heappop(heap)     # evict the smallest, keeping the top k

    return sorted(heap, reverse=True)   # heap[0] alone is the kth largest

Complexity characteristics

Time

O(log n) per push or pop; O(n log k) for top-k

Auxiliary space

O(n), or O(k) for top-k

A heap is a complete binary tree, so sifting up or down touches one node per level and costs log n. Keeping a capped heap of size k answers top-k in O(n log k) against O(n log n) for a full sort — a real saving when k is small, and the only option at all when the input is a stream of unknown length. Building a heap from an array with heapify is O(n) rather than O(n log n), which is worth knowing when the whole input is available up front.

All 163 heap / priority queue LeetCode problems

Every problem in the library the heap / priority queue pattern applies to, grouped by LeetCode's own difficulty rating. 138 of the 163 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Heap / Priority Queue pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.