Heaps & Priority Queue
Quick reference
| push | O(log n) |
| pop | O(log n) |
| peek | O(1) |
| heapify (from an existing array) | O(n) |
Picture a hospital triage line. The most urgent patient is always at the front — the front is never wrong. But the rest of the line isn't sorted at all; patient #5 might be more urgent than patient #3. Nobody's wasting time keeping the whole line in perfect order, because the only thing anyone actually needs is: who's next? A heap is that triage line, formalized. It keeps the smallest (or largest) item always instantly reachable at the top, and does just enough work — a little reshuffling each time someone joins or leaves — to keep that one guarantee true. Everything below the top is only "roughly enough" ordered.
Compare that to keeping a fully sorted array. Every new arrival has to be slotted into its exact position, which means shifting every element after it — expensive, every single time. A heap refuses to pay that price: it doesn't promise the third-most-urgent item is at index 2, or that scanning left to right gives you sorted order. It promises exactly one thing — the top is always correct — and that narrower promise is what makes it cheap to maintain.
The array
# a heap is a plain array — no node, no pointers. # for the element at index i: # left child -> index 2*i + 1 # right child -> index 2*i + 2 # parent -> index floor((i - 1) / 2) # # (straight out of Arrays & Strings Fundamentals: index math gives instant # access to "the next thing" without ever storing an address for it.) # # min-heap invariant: every parent's value <= both of its children's values. # (nothing is said about how two children, or two cousins, compare to each other.)
push — append, then sift up — O(log n)
function push(heap, value):
heap.append(value) // new element goes at the very end
i = heap.length - 1
while i > 0:
parent = floor((i - 1) / 2)
if heap[i] < heap[parent]: // smaller than its parent — invariant broken
swap(heap[i], heap[parent])
i = parent
else:
break // parent is already smaller — done climbingpop — remove the root, sift down — O(log n)
function pop(heap):
if heap.length == 0:
return NULL // nothing to remove
top = heap[0]
last = heap.removeLast()
if heap.length > 0:
heap[0] = last // plug the hole with whatever was last
siftDown(heap, 0)
return top
function siftDown(heap, i):
n = heap.length
while true:
left = 2*i + 1
right = 2*i + 2
smallest = i
if left < n and heap[left] < heap[smallest]:
smallest = left
if right < n and heap[right] < heap[smallest]: // must check BOTH, keep the smaller
smallest = right
if smallest == i:
break // both children are already >= this node — done
swap(heap[i], heap[smallest])
i = smallestpeek — O(1)
function peek(heap):
if heap.length == 0:
return NULL
return heap[0] // the minimum is always sitting at index 0heapify — build a heap from an existing array bottom-up — O(n)
function heapify(array):
n = array.length
// last parent down to the root — skip leaves, they're trivially valid heaps of one
for i from floor(n / 2) - 1 down to 0:
siftDown(array, i)
return arrayA heap stored in an array is always a complete binary tree — every level full except possibly the last, which fills left to right with no gaps. That's not a maintained invariant you have to check; it falls straight out of always inserting at the end and always removing from the end. A complete tree's height is always O(log n), full stop — no rebalancing logic required, unlike a plain BST (next topic's neighbor) which can skew into a straight line. And because the whole structure lives in one array, there are no node objects and no pointers to allocate — extra space beyond the array itself is O(1) across every operation.
| Operation | Time | Space | Why |
|---|---|---|---|
| push | O(log n) | O(1) | Worst case, the new element sifts up from a leaf all the way to the root — one swap per level, and a complete tree of n nodes has O(log n) levels. |
| pop | O(log n) | O(1) | Same shape as push in reverse: the relocated element sifts down at most the height of the tree. |
| peek | O(1) | O(1) | The minimum is guaranteed to be at index 0 — no comparisons, no traversal. |
| heapify (from an existing array) | O(n) | O(1) | Most of the n nodes sit near the bottom and sift down only a level or two; the sum of all that work across the whole array works out to O(n), not O(n log n) — see the callout in Build It. |
Empty heap
Both must check heap.length == 0 first and return cleanly (NULL, or however your language signals "nothing here") instead of reading index 0 of an empty array. Same discipline as checking head == NULL on an empty linked list before touching it.
"A heap is a sorted array" — no, it isn't
The only promise a min-heap makes is parent <= children. heap[1] and heap[2] are both children of the root and could be in either order relative to each other, and heap[1] could easily be larger than heap[4] two levels down on the other side. The array is not sorted — only the path from any node up to the root is guaranteed non-decreasing. To actually get sorted order out of a heap you'd have to pop every element one at a time (that's heap sort, and it costs the full O(n log n)).
Sifting down against the wrong child
A min-heap's sift-down must compare against the smaller of the two children, then swap with that one — never the other, never an arbitrary pick. Swap with the larger child and the smaller child ends up buried under a value that should have floated above it: the heap invariant breaks silently, one level down, with no error and no crash — it just quietly starts returning wrong answers from pop() later.
Off-by-one in the index math
Easy slips: using i/2 for the parent instead of floor((i-1)/2) (they only agree for even i), forgetting the -1 entirely, or swapping which formula is left vs. right. Just as common: forgetting the bounds check — left < n and right < n — before reading heap[left] or heap[right], which reads past the end of the array on any node near the bottom.
Sign in to mark problems done — progress syncs across devices.