Heaps and Priority Queues: Keeping Only the Top

A scheduler must repeatedly pick the highest-priority job. A pathfinder must repeatedly expand the nearest unvisited node. Both need the same operation: give me the extreme element, then let me insert more.

Sorting the whole collection solves it, but does far too much work. Sorting establishes the relative order of every pair, and you only ever asked about the front. Worse, each insertion would require re-establishing that order.

A balanced search tree is closer, and would work, but it also maintains full ordering. A heap is the structure that maintains exactly the amount of order this problem requires, and no more. That restraint is what makes it small, fast, and array-shaped.

A binary heap is a binary tree with one rule: every node is less than or equal to both of its children. That is a min-heap; flip the comparison for a max-heap.

Notice how much weaker this is than a search tree. It says nothing about left versus right, so siblings are unordered and the structure is not sorted in any useful sense. All it guarantees is that the smallest element in the whole heap sits at the root, because the property chains upward along every path.

That one guarantee is the entire product. You get the minimum in constant time by reading the root. You get nothing else cheaply, which is exactly the bargain: less order maintained means less work per update.

The second design choice is what makes heaps fast in practice. A binary heap is kept complete, meaning every level is full except possibly the last, which fills left to right.

A complete tree has no gaps, so it can be stored in a plain array with the tree structure implied by arithmetic rather than pointers. For a node at index i, zero-based:

parent = (i - 1) // 2
left   = 2 * i + 1
right  = 2 * i + 2

There are no node objects and no pointer chasing. Navigating to a child is an index computation, and the whole heap occupies one contiguous block of memory. This is why a heap frequently outperforms a pointer-based tree with identical asymptotics: it is far friendlier to the cache.

Only two operations maintain the heap, and both walk a single root-to-leaf path.

To insert, append the new value at the end of the array, which keeps the tree complete, then sift up: while it is smaller than its parent, swap the two. The value rises until its parent is smaller, and the property holds again.

To extract the minimum, take the root, then move the last array element into the root slot to keep the tree complete, and sift down: repeatedly swap it with its smaller child until both children are larger.

Each operation touches at most one node per level, and a complete tree of n nodes has height about log n. Both are therefore logarithmic, with a very small constant.

Given an unsorted array, you could insert each element one at a time for n log n total. There is a better way, and the reason is a genuinely surprising piece of arithmetic.

Instead, treat the array as an already-complete tree and sift down every non-leaf node, starting from the last one and working backwards to the root. The classic analysis in CLRS shows this costs linear time overall.

The intuition is that cost is not uniform across nodes. Sifting down from a node costs its height, and a complete tree is overwhelmingly leaves: about half the nodes are at the bottom with height 0, a quarter have height 1, an eighth height 2. Summing height times count gives a series that converges to a constant multiple of n. The expensive nodes are the rare ones.

Build a max-heap, then repeatedly swap the root with the last element and shrink the heap by one. The array ends up sorted, in place, with a guaranteed n log n worst case and no extra memory.

On paper that beats quicksort, whose worst case is quadratic. In practice heapsort is rarely the default, and the reason is memory access. Sifting down jumps between indices i, 2i+1 and 4i+3, striding further with each level, so it misses cache constantly. Quicksort scans linearly and predictably.

The compromise most standard libraries ship is introsort: run quicksort, monitor recursion depth, and switch to heapsort only if it goes too deep. You get quicksort's speed with heapsort's worst-case guarantee as a backstop, which is the same safety-net pattern as a hash bucket falling back to a tree.

The most useful everyday application is finding the k largest items in a stream too big to sort, or too big to hold.

The trick is counterintuitive: to find the k largest, keep a min-heap of size k. For each incoming item, if the heap has fewer than k items, push it. Otherwise compare against the root, which is the smallest of your current winners. If the new item is larger, pop the root and push the new item; if not, discard it.

import heapq

def top_k(stream, k):
    heap = []
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)

Memory is proportional to k, not to the stream length, and each item costs at most log k. Sorting a billion records to take the top ten is the mistake this replaces.

A binary heap gives you the minimum and nothing else. Searching for an arbitrary value means scanning the array, because the heap property says nothing about where a given key lives.

That matters for algorithms like Dijkstra's, which need to decrease the priority of a node already in the queue. Doing that requires knowing its index, so implementations either maintain a side map from key to index, or take the common shortcut of pushing a duplicate entry with the better priority and ignoring stale entries when they surface.

Every language ships one: heapq in Python, PriorityQueue in Java, std::priority_queue in C++, container/heap in Go.

Two details cause most of the confusion. First, direction: Python's heapq is a min-heap only, so for a max-heap you push negated values or a key wrapper. C++'s priority_queue defaults to a max-heap. Getting this backwards is the single most common bug.

Second, stability and ties. Heaps are not stable, and comparing tuples falls through to the next element on a tie, which throws if that element is not comparable. The fix is to push a tuple of priority, a monotonic counter, and the payload, so the counter breaks every tie before the payload is ever examined.