Heaps & Priority Queues6 min read

Priority Queue Patterns

K-th largest, merge K lists, top-K frequent — solved with a small heap
push: \(O(\log k)\)pop: \(O(\log k)\)space: \(O(k)\)

A priority queue (PQ) is an abstract data type backed by a heap: you push items in any order, but always pop the highest-priority item first. Think of a hospital triage system — patients arrive in random order but the most critical case is always treated next, regardless of arrival time.

The key insight for interview problems: you almost never need the entire heap. You need a heap of size k, where k is some small constraint in the problem. This keeps space at \(O(k)\) and operations at \(O(\log k)\).

Pattern 1: K-th Largest Element

Maintain a min-heap of size k. For each element: push it onto the heap, then if size exceeds k, pop the minimum. When done, the root (minimum of the heap) is the k-th largest overall.

pseudocode
1
2
3
4
5
6
7
8
9
import heapq


def kth_largest(nums, k):
    heap = []  # min-heap
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]  # root = k-th largest

Why a min-heap? You want to evict the smallest among the current top-k candidates. The heap root gives you that cheaply.

◈ Explore priority queue

← → arrow keys to step · click elements to interact

Priority Queue Patterns

import heapq


# Min-heap (default)
min_heap = []
for v in [5, 1, 3, 2, 4]:
    heapq.heappush(min_heap, v)
print([heapq.heappop(min_heap) for _ in range(5)])  # [1, 2, 3, 4, 5]


# Max-heap: negate values
max_heap = []
for v in [5, 1, 3, 2, 4]:
    heapq.heappush(max_heap, -v)
print([-heapq.heappop(max_heap) for _ in range(5)])  # [5, 4, 3, 2, 1]


# Priority queue with (priority, value)
tasks = [(3,'low'),(1,'high'),(2,'medium')]
heapq.heapify(tasks)
while tasks:
    print(heapq.heappop(tasks))
Output
[1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]
(1, 'high')
(2, 'medium')
(3, 'low')

Pattern 2: Merge K Sorted Lists

Given k sorted linked lists (or arrays), merge them into one sorted list. Push the head of each list into a min-heap with the list index. Repeatedly pop the minimum, append to result, and push the next element from the same list.

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
def merge_k_sorted(lists):
    result = []
    heap = []  # (value, list_index, element_index)
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    while heap:
        val, li, ei = heapq.heappop(heap)
        result.append(val)
        if ei + 1 < len(lists[li]):
            heapq.heappush(heap, (lists[li][ei+1], li, ei+1))
    return result
# O(n log k) where n = total elements

Pattern 3: Top-K Frequent Elements

Build a frequency map (\(O(n)\)), then use a min-heap of size k keyed by frequency. Same eviction trick as K-th largest: if heap size exceeds k, pop the least frequent. The k remaining elements are the top-k most frequent.

Bucket sort alternative: Create an array of buckets indexed 0 to n (frequency as index). Fill each bucket with elements of that frequency. Read from the back until you have k elements. \(O(n)\) time and space.

Note: The 'min-heap of size k' trick appears in dozens of interview problems. When you see 'find the k largest / k most frequent / k closest' — immediately think: maintain a min-heap, evict below k. Space is \(O(k)\), time is \(O(n \log k)\).
Pattern selection guide: choose the right heap strategy based on problem type

Complexity

Push to size-k heapSift up within the small heap
Log k\(O(\log k)\)
Pop min from size-k heapSift down within the small heap
Log k\(O(\log k)\)
K-th largest (n elements)Process each element, heap never exceeds size k
n log k\(O(n \log k)\)
Merge k lists (n total)n pops, each \(O(\log k)\) where k = number of lists
n log k\(O(n \log k)\)
SpaceOnly the heap itself; input not counted
K entries\(O(k)\)

Merge K Sorted Lists

import heapq


def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    result = []
    while heap:
        val, li, idx = heapq.heappop(heap)
        result.append(val)
        if idx + 1 < len(lists[li]):
            heapq.heappush(heap, (lists[li][idx+1], li, idx+1))
    return result


lists = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(merge_k_sorted(lists))  # [1, 2, 3, 4, 5, 6, 7, 8, 9]
Output
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Challenge

Quick check

You want to find the 3rd largest element from a stream of 1 million numbers. Which heap and size do you use?

Continue reading

Heaps
Always know the smallest (or largest) in \(O(1)\) — with \(O(\log n)\) updates
→
Two-Heap Pattern
Split the data in half — find the median in \(O(1)\) always
→