Heaps & Priority Queues: The Most Urgent Item First

What you'll learn

• What a priority queue promises: it always hands you the smallest (or largest) item next
• How a binary heap keeps that promise in O(log n) using nothing but an array and the heap order rule
• Push (sift up), pop (sift down) and heapify, which builds a heap in O(n)
• How to use the heap in your language (Python heapq, Java PriorityQueue, C++ std::priority_queue) and avoid its traps
• Two classic patterns: top-k with a heap of size k, and merging k sorted streams
• You will write: your own min-heap, a running k-th largest tracker and a k-way merge

The emergency room

At a hospital emergency department, patients are not seen in the order they arrive. A nurse assigns each one an urgency (triage), and whenever a doctor becomes free the question is always the same: who is the most urgent right now? New patients keep arriving while others are being treated.

You could keep the waiting list sorted at all times, but then every arrival shifts the list. You could leave it unsorted and scan everyone each time a doctor is free. A heap sits in between: it keeps just enough order to answer "who is next?" instantly and to absorb a new arrival quickly.

The same question appears everywhere in software: an operating system choosing the next process to run, a simulation processing the next event in time order, a router sending high-priority packets first, a "top 10 trending" list, and Dijkstra's shortest-path algorithm, which you will meet in the next lesson.

Priority queues and the binary heap

A priority queue supports three operations: push an item, peek at the smallest, and pop (remove and return) the smallest. (A max-priority queue does the same for the largest.) The obvious implementations each make one operation slow:

                   push        pop smallest    peek
unsorted array     O(1)        O(n)            O(n)
sorted array       O(n)        O(1)            O(1)
binary heap        O(log n)    O(log n)        O(1)

A binary heap is a complete binary tree stored in an array. "Complete" means every level is full except possibly the last, which fills from the left. Because there are no gaps, the tree needs no pointers: with 0-based indexes,

• the children of index i are at 2i + 1 and 2i + 2
• the parent of index i is at (i - 1) // 2

Heap order (min-heap): every parent is less than or equal to its children. So the smallest item is always at the root, index 0. Nothing is said about siblings or cousins: a heap is not sorted, and that freedom is what makes it cheap.

              1
           /     \
          3       2
         / \     / \
        7   4   5   9
       /
      8

index:  0  1  2  3  4  5  6  7
array: [1, 3, 2, 7, 4, 5, 9, 8]

A complete tree with n nodes has height ⌊log₂ n⌋, and both operations walk a single root-to-leaf path:

• push (sift up): append the item at the end (the next free leaf), then, while it is smaller than its parent, swap it with the parent. Pushing 0 above: it starts at index 8 under the 7, swaps with 7, then 3, then 1, and becomes the root.
• pop (sift down): remember the root, move the last item to the root, then, while it is larger than one of its children, swap it with the smaller child (swapping with the larger one would put a large value above a small one). Popping from the array above: 8 moves to the root, swaps with 2 (the smaller child), then with 5, and stops: [2, 3, 5, 7, 4, 8, 9].

Heapify, heap sort and the heap in your language

Heapify in O(n). Building a heap with n pushes costs O(n log n). Robert Floyd's method (1964) is faster: put the items in the array as they are, then sift down every node that has children, from the last parent (n // 2 - 1) back to the root. Half the nodes are leaves and never move, a quarter move at most one level, an eighth at most two, and so on; the total is less than n swaps, so heapify is O(n). Python's heapq.heapify documents exactly this: it transforms a list into a heap in place, in linear time.

Heap sort (J. W. J. Williams, 1964) heapifies, then pops n times: O(n log n) in the worst case with O(1) extra space. It is not stable, and in practice library sorts are usually faster, but it is a guaranteed-time fallback (introsort, behind many C++ std::sort implementations, switches to heap sort when quicksort recursion gets too deep).

The heap in your language:

• Python heapq: functions on a plain list, always a min-heap: heappush, heappop, heapify, heapreplace, heappushpop, nsmallest, nlargest and merge. For a max-heap, push -x (Python 3.14 added heappush_max and related functions, but negation works in every version). To store items that cannot be compared, or to break ties in insertion order, push tuples (priority, counter, item), as the heapq documentation recommends.
• Java PriorityQueue: a min-heap by natural order or by a Comparator. Its documentation promises O(log n) for offer and poll, constant time for peek, but linear time for remove(Object) and contains. Iterating over it does not give sorted order.
• C++ std::priority_queue: a max-heap by default. For a min-heap write std::priority_queue<T, std::vector<T>, std::greater<T>>.
• Rust BinaryHeap: also a max-heap; wrap items in std::cmp::Reverse for a min-heap. Go offers container/heap, which runs on your own type once it implements five methods (Len, Less, Swap, Push, Pop).

What heaps do not do: find an arbitrary item, or change its priority, quickly. The common workaround is lazy deletion: push the item again with its new priority and, when an outdated entry is popped later, skip it. Dijkstra's algorithm uses exactly that trick.

Top-k: a small heap for a big stream

You want the k largest values from n numbers, or the k-th largest at every moment of a stream. Sorting everything costs O(n log n) time and O(n) memory, and you cannot sort a stream that never ends.

Keep a min-heap of size k holding the k largest values seen so far. For each new value, push it; if the heap now has k + 1 items, pop the smallest. The root is then the k-th largest value so far, the weakest member of the top k, which is exactly the one to evict when something better arrives. That is why the k largest use a min-heap.

k = 3, stream 5 1 9 3 7 6

read 5   heap holds {5}            fewer than 3 values: no answer yet
read 1   heap holds {1, 5}
read 9   heap holds {1, 5, 9}      3rd largest = 1 (the root)
read 3   push 3, pop 1  -> {3, 5, 9}   3rd largest = 3
read 7   push 7, pop 3  -> {5, 7, 9}   3rd largest = 5
read 6   push 6, pop 5  -> {6, 7, 9}   3rd largest = 6

Every step is O(log k), so the whole stream costs O(n log k) time and only O(k) memory. For k = 10 and a hundred million numbers that is a few comparisons per number and ten stored values. Python's heapq.nlargest(k, data) applies the same idea, and heapq.heappushpop does the push and the pop in one step.

The mirror image also holds: the k smallest use a max-heap of size k. Combining both, a max-heap for the lower half and a min-heap for the upper half, gives the median of a stream in O(log n) per value.

Merging k sorted streams

You have k sorted lists with N values in total and need one sorted list. Concatenating and sorting costs O(N log N) and ignores the order you already have. Merging the lists one after another costs up to O(N x k), because early values are copied again in every round.

Use a heap of the current front of every list. Each heap entry is (value, list index, position). Pop the smallest entry, output its value, and push the next value of the same list, if there is one. The heap never holds more than k entries, so every step is O(log k) and the whole merge is O(N log k).

A = 1 4 9     B = 2 3 10     C = 5 6

heap of fronts        pop     push the next value of that list
1A  2B  5C            1       4 (from A)
2B  4A  5C            2       3 (from B)
3B  4A  5C            3       10 (from B)
4A  5C  10B           4       9 (from A)
5C  9A  10B           5       6 (from C)
6C  9A  10B           6       -  (C is finished)
9A  10B               9       -
10B                   10      -
output: 1 2 3 4 5 6 9 10

The list index inside the entry is more than bookkeeping: when two values are equal, the comparison moves on to the list index, so ties are broken in a fixed order and the entries never need to compare anything else.

Where this runs for real: external sorting (sort chunks that fit in memory, write them to disk, then k-way merge the sorted runs), log-structured storage engines that merge sorted files in the background, and combining time-ordered logs from many servers. Python's heapq.merge performs the same merge lazily, one value at a time.

Summary

• A priority queue hands out the smallest (or largest) item next. A binary heap implements it with an array: children of i at 2i + 1 and 2i + 2, parent at (i - 1) // 2, and every parent no larger than its children.
• push sifts up and pop moves the last item to the root and sifts down towards the smaller child: both O(log n); peek is O(1). A heap is not sorted.
• heapify builds a heap in O(n); heap sort is O(n log n) worst case with O(1) extra space, but not stable.
• Know your library: Python heapq and Java PriorityQueue are min-heaps, C++ std::priority_queue and Rust BinaryHeap are max-heaps. Use (priority, counter, item) entries for ties, and lazy deletion to "change" a priority.
• Top-k: a min-heap of size k gives the k largest in O(n log k) time and O(k) memory, even on a stream. k-way merge: a heap of list fronts merges N values from k sorted lists in O(N log k).

Practice next: find the k closest points to the origin, keep the median of a stream with two heaps, and schedule tasks by deadline with a priority queue. Then continue with Shortest Paths & Union-Find, where Dijkstra's algorithm runs on a heap.