Heaps and priority queues

A queue serves items in the order they arrived. Many problems instead need the most urgent item first, whatever order the items arrived in: an operating system runs the highest-priority ready task, a network router sends voice packets before bulk downloads, a simulation processes the earliest scheduled event next, and a hospital emergency room sees the most serious case first. The abstract data type for this is the priority queue, which supports inserting an item with a priority and removing the item with the highest priority, or equivalently the smallest key. The standard implementation is the binary heap, a complete binary tree stored in an array, which makes both operations O(log n) and finding the minimum O(1). Heaps are also the basis of heapsort, of the top-k selection that analysts use every day, and of the shortest-path algorithms in later courses.

Jonah meets two priority queues at once. On the NS-4, the modem can send only one message at a time, and several kinds of message compete for it: alarms, such as an open cabinet door, must go first; scheduled count reports next; and bulk uploads of raw records whenever the link is otherwise idle. Within each class, older messages go before newer ones. On the server, the morning report lists the 100 highest speeds recorded across all nodes the previous day, out of roughly 30 million records, and the first version sorted all 30 million records to find them.

The heap property

A binary min-heap is a complete binary tree in which every node's key is less than or equal to the keys of its children. Applied at every node, this heap-order property means the smallest key in the heap is always at the root. A max-heap reverses the comparison, keeping the largest key at the root. Note what the heap property does not say: there is no ordering between siblings or between the left and right subtrees, so a heap is far less ordered than a binary search tree. That looseness is exactly what makes it cheap to maintain. A heap answers only one question quickly, which item is smallest, but answers it in constant time and updates in logarithmic time.

Because a heap is a complete binary tree, it is stored in an array exactly as lesson 7 described: the root at index 0, then each level from left to right, with the children of index i at 2i + 1 and 2i + 2 and its parent at ⌊(i − 1)/2⌋. There are no pointers, no wasted slots and no balancing to worry about: a complete tree of n nodes always has height ⌊log₂ n⌋. A heap of a million items has height 19. This compact array layout is also cache-friendly near the top of the tree, which is where most operations spend their time.

Insert: sift up

To insert a key, place it in the next free position, at the end of the array, which keeps the tree complete. The new key may be smaller than its parent, breaking the heap property, so compare it with its parent and swap if it is smaller; repeat from its new position until it is no smaller than its parent or it reaches the root. This is called sift-up, or bubble-up. Each swap moves the key one level up, so at most height swaps are needed: O(log n). On average, for random keys, insertion is even cheaper, about a constant number of swaps, because most new keys belong near the bottom.

Remove the minimum: sift down

The minimum is at the root, so reading it is O(1). Removing it leaves a hole at the top. Move the last element of the array into the root, which keeps the tree complete, then restore the heap property by sift-down: compare the key with its two children; if it is larger than the smaller child, swap with that child; repeat from the child's position until the key is no larger than either child or it reaches a leaf. Swapping with the smaller child is essential, because that child becomes the parent of the other and must not be larger than it. Each step moves down one level, so removing the minimum costs O(log n).

# NS-4 modem queue: priority by message class, then by age (sequence number)
import heapq

ALARM, REPORT, BULK = 0, 1, 2          # smaller number = more urgent
queue, seq = [], 0

def submit(cls, text):
    global seq
    heapq.heappush(queue, (cls, seq, text))   # ties on class are broken by age
    seq += 1

submit(BULK, "raw records 09:00-09:05")
submit(REPORT, "15-min counts 09:00")
submit(BULK, "raw records 09:05-09:10")
submit(ALARM, "cabinet door opened")
submit(REPORT, "15-min counts 09:15")
submit(ALARM, "loop 2 open circuit")

print("heap array:", [m[1] for m in queue])
while queue:
    cls, s, text = heapq.heappop(queue)
    print(f"send class {cls} (#{s}): {text}")

heap array: [3, 1, 5, 0, 4, 2]
send class 0 (#3): cabinet door opened
send class 0 (#5): loop 2 open circuit
send class 1 (#1): 15-min counts 09:00
send class 1 (#4): 15-min counts 09:15
send class 2 (#0): raw records 09:00-09:05
send class 2 (#2): raw records 09:05-09:10

Python's heapq module implements a binary min-heap on an ordinary list, with heappush and heappop doing sift-up and sift-down. Storing tuples makes the comparison work on the first field, the class, and break ties with the second, a sequence number that grows with each submission, so older messages of the same class go first. The sequence number also guarantees that two entries never compare equal on both fields, so Python never tries to compare the message texts. The printed heap array shows that the list is not sorted, only heap-ordered; the messages nonetheless come out in exactly the required order. On the NS-4 itself, the same queue is a fixed array of 16 message descriptors with hand-written sift-up and sift-down, about 40 lines of C.

Building a heap in linear time

Sometimes all the items are available at once, and the heap must be built from an unordered array. Inserting them one at a time costs O(n log n). A cleverer method, due to Robert Floyd, does it in O(n): treat the array as a complete tree, and call sift-down on every internal node, starting from the last one, at index ⌊n/2⌋ − 1, and working backwards to the root. Each sift-down makes the subtree rooted at that node a valid heap, because its children's subtrees are already heaps. The total cost is linear because most nodes are near the bottom: half the nodes are leaves and need no work, a quarter can move down at most one level, an eighth at most two, and so on.

Top-k selection

The morning report needs the 100 highest speeds out of 30 million. Sorting everything costs O(n log n), about 30 million × 25 comparisons, and needs all 30 million values in memory at once. A heap does better. Keep a min-heap of the k largest values seen so far. For each new value, if the heap holds fewer than k items, push it; otherwise compare it with the heap's minimum, the smallest of the current top k, and if the new value is larger, replace the minimum with it and sift down. Each value costs O(log k), so the total is O(n log k), and the memory is only k items. With k = 100, log₂ k is about 7, so the work drops by a factor of three or four compared with sorting, and the data can be streamed from the database without ever being held in memory.

# Top-k speeds from a stream with a size-k min-heap, counting comparisons
import heapq, math, random

random.seed(11)
n, k = 300_000, 100
speeds = (round(random.gauss(92, 14), 1) for _ in range(n))   # km/h, streamed

top = []
for s in speeds:
    if len(top) < k:
        heapq.heappush(top, s)
    elif s > top[0]:                       # larger than the smallest of the top k
        heapq.heapreplace(top, s)          # pop the minimum and push s in one sift-down

best = sorted(top, reverse=True)
print("highest five:", best[:5])
print(f"100th highest: {best[-1]}")
print(f"heap approach ~ n log2 k = {n * math.log2(k):,.0f} steps at most; "
      f"full sort ~ n log2 n = {n * math.log2(n):,.0f}")

highest five: [153.9, 151.8, 150.9, 150.7, 150.0]
100th highest: 139.2
heap approach ~ n log2 k = 1,993,157 steps at most; full sort ~ n log2 n = 5,458,381

In practice the heap approach is faster still than the estimate, because most values in a stream are smaller than the current 100th highest and are rejected by a single comparison with the root, without touching the heap. The same pattern finds the k nearest nodes to a breakdown, the k busiest intersections or the k most recent alarms. Python's heapq.nlargest uses this technique internally. For finding only the median, or any single order statistic, the quickselect algorithm in later courses does it in O(n) average time.

Heapsort and other uses

A heap also gives a sorting algorithm. Build a max-heap from the array in O(n); then repeatedly swap the root, the largest remaining item, with the last item of the heap, shrink the heap by one and sift the new root down. After n − 1 steps the array is sorted in ascending order. Heapsort costs O(n log n) in the worst case and sorts in place with only a constant amount of extra memory, which makes it attractive in embedded and real-time systems where both a guaranteed bound and a fixed memory footprint matter. Its weakness is cache behavior: sift-down jumps between distant array positions, so in practice it is usually slower than quicksort and merge sort, the subject of lesson 11. Many library sort routines use heapsort as a fallback when quicksort's recursion becomes too deep, a combination called introsort.

Beyond sorting, priority queues appear wherever events must be processed in time order. Operating system timers keep pending timeouts in a heap keyed by expiry time, so the next one to fire is always at the root. Discrete-event simulators, which Northway uses to model how a new signal timing plan will affect queues at an intersection, keep future events in a heap. Dijkstra's shortest-path algorithm and Prim's minimum-spanning-tree algorithm, covered in CMP-301, both depend on a priority queue for their efficiency. When items' priorities must change while they are in the queue, an indexed heap keeps a separate table of each item's position so that its key can be decreased and sifted up in O(log n).