21 of 32 · 6 min

When you only ever want the best one

A hospital queue is not first come first served. A print queue has urgent jobs. A route finder always wants to examine the nearest unvisited place next.

All three want the same operation: give me the smallest, repeatedly, while things keep arriving.

Why the obvious answers are bad

A sorted array gives the smallest instantly and costs O(n) to insert into. An unsorted array inserts instantly and costs O(n) to find the smallest. A balanced BST does both in O(log n), which is fine, but it maintains a total ordering you never asked for.

A heap gives up that total ordering and keeps only what is needed.

The rule

A binary heap is a binary tree with one rule: every node is smaller than its children. That is it. Siblings are in no particular order.

code

            3
         /     \
       5        8
      / \      /
    9    6   10

5 and 8 are ordered against 3, and not against each other. That weaker promise is what makes the operations cheap, and it is enough, because the only thing ever asked for is the root.

It is an array

The tree is a picture. A heap is stored as a flat array, with the children of index i at 2i + 1 and 2i + 2:

code

index:  0  1  2  3  4  5
value:  3  5  8  9  6  10

No pointers, no allocation per node, and excellent cache behaviour. This is a good example of a structure being a way of interpreting memory rather than a thing in memory.

The two operations

Insert: put it at the end, then swap it upward while it is smaller than its parent. At most the height, so O(log n).

Extract minimum: take the root, move the last element into its place, then swap it downward while a child is smaller. Again O(log n).

Operation	Cost
Find minimum	O(1)
Insert	O(log n)
Extract minimum	O(log n)
Build from n items	O(n)

That last row surprises people. Building a heap from an existing array is linear, not n log n, because most nodes are near the bottom and barely move.

Where you will meet it

heapq in Python, PriorityQueue in Java, priority_queue in C++. It is the engine inside Dijkstra's algorithm, it solves "top k items from a stream" in O(n log k) with a heap of size k, and it is the scheduler in most operating systems.