Heaps & Priority Queue
Quick reference
| push | O(log n) |
| pop | O(log n) |
| peek | O(1) |
| heapify (from an existing array) | O(n) |
Think of a hospital triage line. The most urgent patient is always at the front, and the front is never wrong. But the rest of the line is not sorted. Patient #5 might be more urgent than patient #3. Nobody keeps the whole line in perfect order, because the only thing that anyone needs is this: who is next? A heap is this triage line, made formal. It keeps the smallest (or largest) item always reachable at the top immediately. It does just enough work (a little reshuffle each time someone joins or leaves) to keep that one guarantee true. Everything below the top is ordered only "well enough".
Compare this to a fully sorted array. Every new arrival must go into its exact position, which means a move of every element after it. This is expensive, every time. A heap refuses to pay that price. It does not promise that the third-most-urgent item is at index 2, or that a scan from left to right gives you sorted order. It promises exactly one thing: the top is always correct. This narrower promise is what makes it cheap to maintain.
The array
# A heap is a plain array. There is no node and no pointer. # For the element at index i: # left child -> index 2*i + 1 # right child -> index 2*i + 2 # parent -> index floor((i - 1) / 2) # # (This comes directly from Arrays & Strings Fundamentals: index math gives instant # access to "the next thing" without a stored address for it.) # # min-heap invariant: the value of every parent <= the values of both of its children. # (It says nothing 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) // the new element goes at the end
i = heap.length - 1
while i > 0:
parent = floor((i - 1) / 2)
if heap[i] < heap[parent]: // smaller than its parent: the invariant is broken
swap(heap[i], heap[parent])
i = parent
else:
break // the parent is already smaller: stop 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 // fill the hole with the last element
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]: // Check BOTH children. Keep the smaller one.
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 at index 0heapify — build a heap from an existing array bottom-up — O(n)
function heapify(array):
n = array.length
// Go from the last parent down to the root. Skip the leaves: they are valid heaps of one element.
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 is full except possibly the last level, which fills from left to right with no gaps. This is not an invariant that you must check. It comes directly from an insert always at the end and a remove always from the end. The height of a complete tree is always O(log n), with no exception, and no rebalance logic. This is unlike a plain BST (the neighbor of the next topic), 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. The extra space beyond the array itself is O(1) for every operation.
| Operation | Time | Space | Why |
|---|---|---|---|
| push | O(log n) | O(1) | In the 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) | This is the same shape as push in reverse: the moved element sifts down at most the height of the tree. |
| peek | O(1) | O(1) | The minimum is guaranteed to be at index 0. There is no comparison and no traversal. |
| heapify (from an existing array) | O(n) | O(1) | Most of the n nodes are near the bottom and sift down only a level or two. The sum of all that work across the whole array is 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 a read of index 0 of an empty array. This is the same discipline as a check that head == NULL on an empty linked list before you touch it.
"A heap is a sorted array" — no, it is not
The only promise that a min-heap makes is parent <= children. heap[1] and heap[2] are both children of the root and can be in either order relative to each other. heap[1] can be larger than heap[4], which is two levels down on the other side. The array is not sorted. Only the path from any node up to the root is guaranteed to be non-decreasing. To get sorted order out of a heap, you must pop every element one at a time (this is heap sort, and it costs the full O(n log n)).
Sifting down against the wrong child
The sift-down of a min-heap must compare against the smaller of the two children, then swap with that one, never the other, and never an arbitrary choice. If you swap with the larger child, the smaller child ends up under a value that should be above it. The heap invariant breaks silently, one level down, with no error and no crash. It quietly starts to return wrong answers from pop() later.
Off-by-one in the index math
Easy mistakes: use i/2 for the parent instead of floor((i-1)/2) (they agree only for even i), forget the -1, or swap which formula is left and which is right. Also common: forget the bounds check (left < n and right < n) before you read 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.