Heap / Priority Queue
Use when: top-K elements, streaming median, greedy scheduling by priority, Dijkstra.
Signal words: K largest, K smallest, K most frequent, median of stream, task scheduling.
Core Idea
Python’s heapq is a min-heap by default. To simulate max-heap, negate values.
import heapq
# Min-heap
heap = []
heapq.heappush(heap, val)
smallest = heapq.heappop(heap)
# Max-heap (negate)
heapq.heappush(heap, -val)
largest = -heapq.heappop(heap)
# Heapify existing list in O(n)
heapq.heapify(arr)Top-K Pattern
# K largest elements
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap) # discard smallest
return list(heap) # or heapq.nlargest(k, nums)Two-Heap Pattern (running median)
Maintain a max-heap for the lower half and min-heap for the upper half.
- Max-heap top = median candidate from left
- Min-heap top = median candidate from right
- Keep sizes balanced (differ by at most 1)