Heaps and Priority Queues

A priority queue is a to-do list that always gives you the most important item next, rather than the oldest. A heap is the data structure that implements it efficiently. The deal it offers is very specific and very useful: the extreme element, the smallest in a min-heap or the largest in a max-heap, is always sitting at the top where you can read it in $O(1)$, and you can insert a new item or remove the top in $O(\log n)$. Crucially, it does not keep everything sorted, which is exactly why it is cheaper than a sorted array.

That trade, "cheap access to the extreme, no full ordering", is why heaps power top-k queries, merging many sorted streams, shortest-path search, and streaming statistics. For a trader the picture is immediate: the top of an order book is two priority queues back to back. The best bid is the maximum of all buy prices; the best ask is the minimum of all sell prices. A heap keeps each of those at the top so the matching engine reads the best price instantly.

The heap property, and the array trick

A binary heap is a tree where every parent obeys one rule. In a min-heap, each parent is less than or equal to its children. That alone forces the global minimum to the root (nothing above it can be smaller), while leaving the rest only loosely ordered. Because the tree is always "complete" (filled level by level), you can store it in a plain array with no pointers: the children of index $i$ live at $2i+1$ and $2i+2$, and the parent of $i$ is at $\lfloor (i-1)/2 \rfloor$.

How the operations stay O(log n)

• Peek the top: read index 0. $O(1)$.
• Push: append the new value at the end, then "sift up", repeatedly swap it with its parent while it is smaller. It rises at most the height of the tree, $\log n$ levels. $O(\log n)$.
• Pop the top: move the last element into the root, then "sift down", repeatedly swap it with its smaller child until the heap property holds again. Again at most $\log n$ swaps. $O(\log n)$.

Building a heap from n items in bulk is $O(n)$ (a tighter bound than n pushes would suggest). What a heap does not give you: sorted iteration, or fast lookup of an arbitrary element, for those, use a different structure.

Worked example: the three largest numbers

Find the 3 largest values in [4, 1, 7, 3, 9, 2, 8]. The lazy way sorts everything ($O(n \log n)$) and takes the last three. A heap does better: keep a min-heap of size 3 holding the three largest seen so far. Its top is the smallest of those three, the bar to beat.

• Push 4, 1, 7 → heap {1, 4, 7}, top (smallest) = 1.
• 3 > 1? Yes: pop 1, push 3 → {3, 4, 7}, top = 3.
• 9 > 3? Yes: pop 3, push 9 → {4, 7, 9}, top = 4.
• 2 > 4? No, skip.
• 8 > 4? Yes: pop 4, push 8 → {7, 8, 9}, top = 7.

The heap now holds the answer: 7, 8, 9. Each step is $O(\log k)$ with $k = 3$, so the whole scan is $O(n \log k)$, better than sorting when k is much smaller than n.

import heapq

def k_largest(a, k):              # O(n log k) time, O(k) space
    heap = a[:k]
    heapq.heapify(heap)           # min-heap of the first k, O(k)
    for x in a[k:]:
        if x > heap[0]:           # bigger than the smallest kept?
            heapq.heapreplace(heap, x)
    return heap                   # the k largest, unsorted

(Python's heapq is a min-heap; for a max-heap, push negated values.)

The two-heap trick and other classics

Split a stream down the middle with a max-heap for the lower half and a min-heap for the upper half, rebalance after each insert, and the two tops straddle the running median, the standard answer to Median from a Data Stream. Heaps also drive merging k sorted lists ($O(N \log k)$), Dijkstra's shortest path (always expand the nearest unvisited node), and task-scheduling by priority.

Where it trips people up

• It is not sorted. The array behind a heap looks jumbled beyond the root. Reading it top-to-bottom does not give sorted order, only the root is guaranteed.
• No cheap arbitrary lookup or delete. Finding or removing a value that is not the top is $O(n)$; if you need that, pair the heap with a hash map of positions, or "lazy-delete" by marking entries stale.
• Min vs max confusion. Most libraries give a min-heap. Wanting the largest? Negate the keys, or store (-priority, item) tuples, and remember to flip the sign back.

In quant-dev interviews heaps own top-k / k-th-largest, merge-k-sorted, streaming-median, and shortest-path questions. On the desk the same structure is the top of an order book, a max-heap of bids and a min-heap of asks keep the best prices one lookup away, which is why this data structure comes up so often in market-making screens.