Heaps & Priority Queues

A heap answers one question, over and over, very cheaply: what is the best item right now?

Think of a hospital triage desk. The most urgent patient is always seen next, no matter who arrived when. A new arrival is slotted in according to how urgent they are, not pushed to the back; and when the most urgent is taken in, the desk settles on the next-most-urgent in a moment, without anyone scanning the whole waiting room. A task scheduler, a shortest-path search, a “top 10 results” buffer — all of them are that same desk. The structure behind it is the heap.

A tree that lives in an array

A heap is a binary tree with a strict rule, but it carries no pointers at all — it lives inside a plain array, and the tree shape comes purely from arithmetic on the indices:

• the node at index i has its children at 2i + 1 and 2i + 2;
• and so its parent is at (i − 1) // 2.

Because the tree is always filled level by level, left to right, with no gaps, the array stays dense and cache-friendly.

The heap property

The rule is wonderfully local. In a min-heap, every parent is ≤ both of its children — and nothing more is required. It says nothing about siblings or cousins; only the parent-child line matters. From that one local rule a global fact follows for free: the smallest value in the whole heap can only be the root, at index 0. (A max-heap is the same with ≥, putting the largest at the root.) That is why “what is the best item right now?” is just reading index 0 — O(1).

Keeping the property: sift-up and sift-down

When you push a new value, you drop it at the end of the array and let it sift up: compare it with its parent, and if it is smaller (in a min-heap), swap, then repeat from the parent’s spot. Each swap climbs one level, and a complete tree of n nodes is only ⌊log₂ n⌋ levels tall — so a push is O(log n).

When you pop the best item, you take the root as your answer, move the last element into the root spot, and let it sift down: compare it with its children, swap it with the smaller one if needed, and repeat. Again one root-to-leaf path at most — O(log n).

A heap is a priority queue

This is the standard way to build a priority queue — a collection that always serves the highest- (or lowest-) priority item next. Push O(log n), pop O(log n), peek O(1). Python’s heapq module is precisely this, always as a min-heap; for a max-heap you negate the values going in and out.

import heapq

h = []
for val in [34, 12, 78, 5, 56, 23, 91]:
    heapq.heappush(h, val)
print("smallest right now:", h[0])

print("popped in order:", [heapq.heappop(h) for _ in range(len(h))])

smallest right now: 5
popped in order: [5, 12, 23, 34, 56, 78, 91]

Popping repeatedly hands the items back smallest-first — the heap never sorted the whole array, it just kept the minimum cheap to reach each time.

The streaming top-K trick

Here is the pattern that makes heaps indispensable in data work. Given a stream of n numbers, find the K largest. Sorting everything is O(n log n). A heap does better: keep a min-heap of size K, and for each new number, if it beats the heap’s current minimum, replace that minimum; otherwise ignore it. The heap always holds the K largest seen so far, and each step costs O(log K).

import heapq

def top_k(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:               # beats the smallest of our current best K
            heapq.heapreplace(heap, x)  # pop the min, push x — one O(log K) step
    return sorted(heap, reverse=True)

data = [41, 7, 93, 55, 28, 76, 13, 62, 84, 37]
print(top_k(data, 3))
print(heapq.nlargest(3, data))         # the stdlib does the same thing

[93, 84, 76]
[93, 84, 76]

The whole pass is O(n log K). When K is much smaller than n — the 10 largest out of ten million — that is close to a single linear scan, and far cheaper than sorting the lot.

Practice