07. Heap & Priority Queue

What you'll learn

• 1Use heapq for a min-heap
• 2Flip signs to get a max-heap
• 3Solve Top-K and stream-merging problems

Overview

Python's heapq is a min-heap implemented as an array. Push and pop are O(log n). It's much faster than re-sorting a list every time you need the minimum.

Core Concepts

1. heapq basics (min-heap)

import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heap[0])           # 1 (peek — smallest)
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 2

2. Build from list

data = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(data)   # O(n) in place
# Now data is a valid heap.

3. Max-heap with sign flipping

max_heap = []
for x in [3, 1, 4, 1, 5]:
    heapq.heappush(max_heap, -x)
-heapq.heappop(max_heap)   # 5

4. Custom priority with tuples

# (priority, id, payload) — earlier tuple elements win
tasks = []
heapq.heappush(tasks, (3, 'low priority'))
heapq.heappush(tasks, (1, 'urgent'))
heapq.heappop(tasks)   # (1, 'urgent')

5. Top-K with a bounded heap

def top_k_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)   # drop smallest
    return sorted(heap, reverse=True)

# Or use heapq.nlargest
heapq.nlargest(3, nums)

Examples

Example 1 — src/01_heap_basics.py

push, pop, peek, heapify in one script.

Example 2 — src/02_max_heap.py

Max-heap via negation.

Example 3 — src/03_top_k.py

Top-K with a heap of size K — O(N log K).

Example 4 — src/04_merge_streams.py

Merge K sorted lists with heapq.merge (returns an iterator).

Common Mistakes

1. Forgetting heapq is a min-heap. Use negation or (-priority,) tuples for max-heaps.
2. Using `min()` on a list every iteration instead of a heap (O(n) vs O(log n)).
3. Calling `sorted(heap)` and treating that as a sorted output — sorted is O(n log n) and is fine for finalization, but not for the running 'min' you wanted.
4. Storing dicts directly in a heap — dicts aren't comparable. Use (priority, counter, dict) tuples.

Recap

• heapq = min-heap, O(log n) push/pop, O(1) peek.
• Sign-flip for max-heaps.
• Tuples give you custom priorities; second element should be a unique tie-breaker.

Try It

1. BOJ 1927 (Min heap).
2. BOJ 11279 (Max heap).
3. BOJ 11286 (Absolute-value heap).