Heapsort & Priority Queues

By the end of this lesson you will be able to explain exactly how a binary heap is stored as a plain array with no pointers at all, trace maxHeapify, buildMaxHeap and heapSort line by line, prove buildMaxHeap runs in O(n) (not the "obvious" O(n lg n)), and implement a working priority queue (insert, find-max, extract-max, increase-key) — the same data structure that powers job schedulers, Dijkstra's algorithm, and "top-k" interview questions.

1. The binary heap as an array

Picture a family tree drawn level by level: one person at the top (generation 1), their two children below (generation 2), four grandchildren below that (generation 3), and so on, with every row completely full before the next row starts — except possibly the very last row, which fills left to right. A binary heap is exactly this shape, called a nearly-complete binary tree. The trick is that you never need boxes-and-arrows to store this tree: because every row's length is predictable (1, 2, 4, 8, …), you can lay every node out in a single flat array and compute "who is whose parent/child" with pure arithmetic.

A heap has two attributes on top of the raw array a: its length (the physical size of the array) and heapSize (how many of those slots currently belong to the heap — always ≤ length). Array positions start at 0, exactly like a Dart List, so the root of the tree always lives at a[0]. For any node stored at index i:

Relationship	Formula (0-indexed)	Why it works
Parent of `i`	`parent(i) = ⌊(i − 1) / 2⌋`	Subtract the root slot, then integer division throws away the remainder, landing on the row above.
Left child of `i`	`left(i) = 2i + 1`	Doubling always lands in the next row down.
Right child of `i`	`right(i) = 2i + 2`	One slot to the right of the left child.

A max-heap obeys the max-heap property: for every node i other than the root, a[parent(i)] ≥ a[i] — every parent is at least as large as its children. This says nothing about left vs. right, or about siblings, or about any two nodes that aren't in a parent/child relationship — only "parent ≥ child" all the way up. The consequence: the maximum element of the whole heap always sits at the root, a[0], because every other element has a chain of ancestors leading up to it. A min-heap is the mirror image (a[parent(i)] ≤ a[i], minimum at the root) — heapSort uses a max-heap; later lessons use min-heaps for scheduling and shortest paths.

The same arithmetic as code — the 0-indexed Dart versions (the root is index 0, so index 10 has its parent at (10 − 1) ~/ 2 = 4):

Because a nearly-complete binary tree with n nodes has height ⌊lg n⌋ (each row roughly doubles the node count, so the number of rows grows only as the logarithm of n), and every heap operation you'll meet in this chapter walks up or down one root-to-leaf path, every basic heap operation costs O(lg n) — except building a whole heap from scratch, which is the pleasant surprise in Section 3.

Height ⌊lg n⌋ and the leaf boundary, as code (the leaves are exactly the indices n ~/ 2 up to n − 1):

Not every array of numbers is a max-heap. Try your own array below and watch the check run exactly the property definition, index by index:

The property check behind that animation, as code (the maximum then sits at index 0):

Input size → what’s feasible. parent/left/right are O(1), so even n = 10⁹ is fine arithmetically (2n + 2 ≤ 2·10⁹ + 2 fits a 64-bit int); the real limit is memory: n = 10⁷ ints ≈ 80 MB, height ⌊lg 10⁷⌋ = 23. Checking the property is O(n).

A very common beginner mix-up: a max-heap is NOT a sorted array. Max-heap only guarantees "parent ≥ children" — a[1] and a[2] (two children of the root) can be in either order relative to each other, and neither has any required relationship to a[3] or a[4] (which live one level further down, under a different parent). A sorted-in-increasing-order array happens to also be a valid min-heap but is generally not a max-heap at all.

Starting at index 0 is what makes the formulas match every mainstream language (Dart, Java, Python, C, JavaScript, …): with the root at index 0, parent(i) = (i - 1) ~/ 2, left(i) = 2i + 1, right(i) = 2i + 2. Some courses start counting at 1 to get the tidier ⌊i/2⌋, 2i, 2i+1; if you ever read code or notes written that way, shift every index by one. Every algorithm in this lesson uses the 0-indexed formulas, so what you read here is exactly what you type in Dart.

A binary heap is a nearly-complete binary tree stored with zero pointers, purely as an array, using arithmetic to find parents/children. Max-heap property: every parent ≥ its children, so the maximum is always at the root. Height is Θ(lg n), which is why almost every heap operation is O(lg n).

2. Maintaining the heap property: maxHeapify

Imagine every row of the family tree is correctly sorted by "seniority" (parent ≥ children) except the person right at the top, who is actually junior to one of their own children. maxHeapify is the procedure that fixes exactly this one broken spot: it looks at that person and their two direct children, finds whichever of the three is most senior, and if it isn't already the person at the top, swaps them down — then repeats the same check one level further down, following the demoted person as they "sink" toward a level where they finally outrank both of their new children.

maxHeapify assumes the two subtrees rooted at left(i) and right(i) are already valid max-heaps, but a[i] itself might be smaller than one of its children — the single node that's out of place. The pseudocode appears in the player below (0-indexed, like the Dart code); line 3 starts with largest ← i and lines 4–7 let each child challenge it:

Dart implementation. First the recursion line for line (left(i) = 2i+1, right(i) = 2i+2, and l < heapSize is the bounds check), then the loop version used everywhere else:

The two-thirds bound and the recurrence T(n) ≤ T(2n/3) + Θ(1), with an exchange counter (each exchange moves the value one level down):

minHeapify is the mirror image — flip every comparison:

Input size → what’s feasible. maxHeapify is O(lg n): at most ⌊lg 10⁶⌋ = 19 exchanges for n = 10⁶, so 10⁶ calls cost about 2·10⁷ steps (< 1 s). The recursive form uses O(lg n) stack, the loop form O(1).

Running time. In the worst case the element at the root of an n-node subtree sinks all the way to a leaf, following one root-to-leaf path. Because a heap's bottom row can be up to half-empty, a node's two subtrees can each hold up to 2n/3 of the elements in the worst case (the worst case is a bottom row that is exactly half full), giving a recurrence T(n) ≤ T(2n/3) + Θ(1). Here a = 1 and b = 3/2, so n^{log_b a} = n⁰ = 1 = Θ(f(n)): master-theorem case 2, where every level of the recursion does the same Θ(1) work, so the total is Θ(1) × (number of levels) and T(n) = O(lg n). Equivalently: maxHeapify called on a node of height h does O(h) work, since it follows exactly one path down to a leaf.

maxHeapify only fixes a violation at the very top of the subtree rooted at i — it assumes both children's subtrees are already valid heaps. Calling it on an array where some deeper node also violates the property will silently produce garbage; you must call it bottom-up (exactly what buildMaxHeap does next) to make an arbitrary array into a heap.

Line 8's check largest ≠ i is also maxHeapify's own base case: as soon as a[i] already outranks both children, the recursive calls stop — the function does not keep recursing all the way to a leaf every single time, only as far as it needs to.

maxHeapify(a, heapSize, i) assumes both children of i are already max-heap roots and repairs a violation only at i, sinking the out-of-place value down one level at a time until it outranks both its new children (or hits a leaf). Cost: O(h) for a node of height h, i.e. O(lg n) worst case.

3. Building a heap in linear time: buildMaxHeap

Every leaf of the tree is trivially a valid 1-person "heap" all by itself — a single person has nobody to out-rank. So instead of fixing the tree top-down, buildMaxHeap works from the bottom row of non-leaf people upward: fix the lowest row of parents first (their children are leaves, so they're already valid mini-heaps), then the row above that (whose children were just fixed), and so on, until the very top person is fixed last — by which point everything beneath them is already guaranteed to be a correct heap.

About half the nodes of any heap (exactly ⌈n/2⌉) are leaves — indices ⌊n/2⌋ through n − 1 — and a single node is trivially already a max-heap, so buildMaxHeap only needs to call maxHeapify on the remaining internal nodes, from ⌊n/2⌋ − 1 down to 0.

Loop invariant: at the start of each iteration of the for loop, every node i+1, i+2, …, n−1 is the root of a valid max-heap.

Initialization: before the first iteration, i = ⌊n/2⌋ − 1, and every node ⌊n/2⌋, …, n−1 is a leaf — trivially the root of a (1-node) max-heap.
Maintenance: both children of node i have indices larger than i, so by the invariant they are already roots of max-heaps — exactly what maxHeapify(a, heapSize, i) requires — and after it runs, node i is a max-heap root too. Decrementing i re-establishes the invariant for the next iteration.
Termination: the loop stops when i = −1, so the invariant says nodes 0, …, n−1 — the whole array — are max-heap roots, i.e. the array is now a valid max-heap. ∎

Dart implementation (the pseudocode’s for i from ⌊n/2⌋ − 1 down to 0 is for (i = n ~/ 2 - 1; i >= 0; i--)), and the same loop with the loop invariant checked at the top of every iteration:

Running time — the pleasant surprise. A loose bound of "n calls to an O(lg n) procedure" gives O(n lg n) — correct, but not tight. The tight bound uses two facts: (1) a heap of n nodes has at most ⌈n / 2^{h+1}⌉ nodes of height h, and (2) maxHeapify on a node of height h costs O(h). The visual below adds up cost × count over every height level:

Heights and counts as code: the number of nodes of each height, the ⌈n/2^h+1⌉ bound, and the summed cost bound:

The series Σ h/2^h numerically (the closed form of the partial sum is 2 − (t+2)/2^t, so the limit is exactly 2):

Summing Σ (n / 2^{h+1}) · O(h) over h = 0 to ⌊lg n⌋ pulls out the constant n and leaves O(n · Σ h/2^h). The infinite sum Σ_{h=0}^{∞} h/2^h converges to exactly 2 (a standard identity: Σ h·x^h = x/(1−x)² at x = 1/2), so the whole sum is O(n · 2) = O(n). buildMaxHeap runs in linear time — the same total work as just scanning the array a couple of times, even though it calls a "logarithmic" subroutine n times.

And the measured comparison counts (buildMaxHeap stays under 3n; heapSort is counted the same way):

Input size → what’s feasible. buildMaxHeap is Θ(n): n = 10⁷ costs at most 3n = 3·10⁷ comparisons, versus n lg n ≈ 2.3·10⁸ for n separate inserts.

The mistake almost everyone makes on first read: multiplying "n calls" by "O(lg n) each" and stopping there. That bound is true but not tight — the vast majority of maxHeapify calls happen near the bottom of the tree, on nodes of small height, where each call is cheap. Only a tiny number of calls (near the root) are expensive, and there just aren't enough of them to add up to more than O(n).

buildMaxHeap calls maxHeapify on every internal node, bottom-up, in ⌊n/2⌋ calls. Because most nodes are near the bottom (cheap to fix) and only a few are near the top (expensive but rare), the total cost is Θ(n), not Θ(n lg n).

4. The Heapsort algorithm

Once the whole group is arranged as a max-heap, the single most senior person is guaranteed to be standing right at the front (the root). heapSort repeatedly: pulls that most-senior person out to the very back of the line (their final, correctly sorted spot), shrinks the "still needs sorting" group by one, and re-heapifies what's left so the new most-senior person again floats to the front — over and over, until only one person is left.

Loop invariant: at the start of each iteration of the for end from heapSize − 1 down to 1 loop, the subarray a[0..end] is a max-heap containing the end + 1 smallest elements of the original array, and a[end+1..n−1] holds the n − 1 − end largest elements, already in their final sorted position.

Dart implementation (for end from heapSize − 1 down to 1 is for (end = n - 1; end >= 1; end--); heapSize is a plain variable), and the same loop with its invariant checked:

Input size → what’s feasible. heapSort is Θ(n lg n): n = 10⁶ → about 4·10⁷ comparisons (fits a second), n = 10⁷ → about 5·10⁸ (borderline); for n ≤ 10⁴ even an O(n²) sort (10⁸ steps) would do.

Running time. buildMaxHeap costs O(n), then the loop runs n - 1 times, each iteration doing O(1) work for the exchange plus one O(lg n) call to maxHeapify. Total: O(n) + (n-1)·O(lg n) = O(n lg n). Unlike insertion sort, heapsort has no better best-case: even a best-case, all-distinct input still forces Ω(n lg n) work overall, because the heap-repair step doesn't get meaningfully cheaper just because the final order happens to favor it.

Heapsort sorts in-place (needs only O(1) extra memory beyond the input array) but it is not stable: two equal elements can easily end up swapped relative to their original order, because maxHeapify's comparisons only look at value, never at original position. If your problem needs equal keys to keep their relative order, heapsort is the wrong tool — use merge sort or a stable variant of insertion/counting sort instead.

The “not stable” claim, demonstrated on (key, label) pairs — three equal keys come out as b, c, a:

Heapsort combines the best of both worlds theoretically achievable by comparison sorts: like merge sort, it guarantees O(n lg n) in every case (no O(n²) worst case the way quicksort has); like insertion sort, it sorts in-place with O(1) extra space (merge sort needs Θ(n) extra space to merge). In practice, well-tuned quicksort usually beats heapsort due to better cache behavior, which is why heapsort is more often seen as a fallback (e.g. introsort, used by many standard library sorts, switches to heapsort only when quicksort's recursion gets suspiciously deep).

heapSort = buildMaxHeap once (O(n)), then repeatedly swap the root (the max) to the end, shrink the heap by one, and maxHeapify the root back into shape — n-1 times, each O(lg n). Total: Θ(n lg n), in-place, NOT stable.

5. Priority queues: heapMaximum, heapExtractMax, heapIncreaseKey, maxHeapInsert

A priority queue is like a hospital emergency room, not a bank line: patients aren't served first-come-first-served, they're served in order of how urgent their condition is (their priority / key), and a patient's urgency can be raised while they're already waiting (their condition worsens). A max-heap is the classic engine behind a "highest priority first" queue, because it always keeps the single most urgent item instantly accessible at the root while still letting you add or promote items cheaply.

A max-priority queue supports four operations, all backed directly by the array-plus-heapSize structure from Section 1:

heapMaximum — just return a[0]. Θ(1), no search needed at all, because the max-heap property guarantees the maximum is always at the root.
heapExtractMax — removes and returns the maximum.
heapIncreaseKey(i, key) — raises the key of an existing element at index i (it is an error to try to decrease it with this operation).
maxHeapInsert(key) — adds a brand-new element.

These four live as methods of the Heap class shown in §7 (fields a and heapSize; 0-indexed). heapMaximum:

heapExtractMax: after saving the root's value, the problem is "the root slot is now empty, but every other slot must stay full for the array to represent a valid, gapless nearly-complete tree." The fix: move the very last element (the one that's easiest to remove without leaving a hole anywhere else) up to the root, shrink the heap, and let maxHeapify sink it into its correct place.

heapExtractMax in Dart (the last element is a[heapSize - 1]):

heapIncreaseKey: raising a value can only ever break the property upward (the node might now outrank its own parent) — it can never break anything below, since the node only got bigger. So instead of a full maxHeapify sink, heapIncreaseKey does the opposite motion: it repeatedly compares the node to its parent and swaps upward ("bubbles up") until it finds a parent at least as large, or reaches the root.

heapIncreaseKey in Dart (the loop stops at the root, so the test is i > 0):

maxHeapInsert: to add a new element without breaking the "nearly-complete" shape, the trick is to first extend the heap by one slot and fill that brand-new leaf with a sentinel value guaranteed smaller than every real key (conceptually -∞). This makes it perfectly safe to hand off to heapIncreaseKey, since "increasing" from -∞ up to the real key can never trigger that procedure's underflow-style error check.

maxHeapInsert in Dart (a 64-bit int has no true -∞, so a very small stand-in is used):

heapDelete(h, i), removing an arbitrary element, built from those pieces:

Input size → what’s feasible. each operation is O(lg n): 10⁵ operations on a 10⁵-element heap are about 1.7·10⁶ steps, while a plain unsorted array makes every extractMax Θ(n), i.e. 10¹⁰ steps in total.

Why set the new leaf to −∞? It teaches a lesson worth internalizing: maxHeapInsert reuses heapIncreaseKey's bubble-up logic instead of duplicating it, purely by exploiting the -∞ sentinel trick. This is a general lesson in algorithm design — express a new operation in terms of one you've already proven correct, rather than writing new (and newly-buggy) logic from scratch.

In real code there is no literal "-∞" for a fixed-width integer type. Our Dart implementation below uses a sentinel value guaranteed smaller than any realistic key (or, when keys can be arbitrarily large, a nullable "empty slot" marker checked before every comparison) — a small, deliberate simplification you should always call out explicitly when translating pseudocode into production code.

All four priority-queue operations run in O(lg n) (heapMaximum is O(1)) because each one does at most one root-to-leaf walk (down for extractMax's re-heapify, up for increaseKey and maxHeapInsert's bubble-up). A binary heap turns "always know / update the most urgent item" into a logarithmic-time guarantee.

6. Going further: d-ary heaps & Young tableaus

A d-ary heap is the same idea as a binary heap, except every internal node gets up to d children instead of just 2 — like reorganizing the family tree so each parent can have, say, 4 children instead of 2. More children per row means a shorter tree (fewer rows for the same headcount), but now maxHeapify must compare against d children instead of 2 at every level it visits.

For an n-element d-ary heap: parent(i) = ⌊(i−1)/d⌋, and the children of i occupy a contiguous block of d slots. Height is Θ(log_d n) = Θ(lg n / lg d) — shorter as d grows. Insert and increaseKey only ever compare a node against its one parent while bubbling up, so they cost O(log_d n) — genuinely faster for large d. But extractMax must find the largest of up to d children at every level while sinking down, costing O(d · log_d n) — which actually gets worse once d is large enough that the extra comparisons outweigh the shorter tree. Explore the trade-off:

d-ary heap in Dart: the index formulas, the height, and the class (children of i sit at d·i + 1 … d·i + d):

Input size → what’s feasible. n = 10⁶ keys: d = 2 gives height 19 (about 38 comparisons per extractMax), d = 4 gives height 10 (about 40), d = 16 gives height 5 (about 80); insert does one comparison per level, so 19 / 10 / 5. Pick d = 2 to 4 unless inserts and increase-keys far outnumber extractions (Dijkstra-style workloads).

A Young tableau is an m × n grid where every row is sorted left-to-right and every column is sorted top-to-bottom (using +∞ to mark unused cells). It generalizes a heap into two dimensions: the smallest finite value is always at the top-left corner, and both insert and extractMin take O(m + n) by "bubbling" along whichever direction (row or column) currently violates the order — and because searching can eliminate an entire row or column at every step (start at a corner, and every comparison rules out a whole line), searching for a target value also only takes O(m + n).

Young tableau in Dart (inf marks an empty cell); the steps counter shows the O(m + n) bound, and sorting n² numbers uses it:

Input size → what’s feasible. a tableau of 1000 × 1000 = 10⁶ cells does each insert / extractMin / search in at most m + n = 2000 steps; sorting those 10⁶ numbers with it costs about n³ = 10⁹ moves, too slow — use heapSort (about 4·10⁷ comparisons) instead.

Search is the other half of the story. Try any target and watch each comparison throw away a whole row or a whole column:

A d-ary heap trades tree height against per-node work — more children means a shorter tree but pricier extractMax. A Young tableau is a 2-D generalization of a heap: sorted rows AND columns give O(m+n) insert, extract-min, and search, all via corner-based bubbling.

7. From pseudocode to working Dart

The pseudocode and Dart are both 0-indexed, so the translation is almost mechanical: parent(i) = (i - 1) ~/ 2, left(i) = 2*i + 1, right(i) = 2*i + 2, and "is there a parent?" is the test "i > 0" (index 0 is the root). Every comparison, every swap, every loop bound carries over line for line. Here is the whole thing packaged as a small Heap class (full source, tested against 200 random arrays and every edge case below, lives in verify/c06.dart):

Input size → what’s feasible. the same loop-based maxHeapify/buildMaxHeap as above, so n = 10⁶ elements build in about 3·10⁶ comparisons; BinaryHeap<T> (below, used by the interview questions) does push/pop in O(lg n).

Notice maxHeapify is written as a while loop instead of recursion — an iterative rewrite of the exact same logic. It produces the identical sequence of swaps as the recursive version, but avoids pushing a new stack frame on every sink step; Dart has no tail-call optimization (see D07), so for a very deep heap the iterative form is the safer production choice.

A subtle off-by-one that trips people up when moving between index origins: with the root at index 0 the "has a parent" test is i > 0, while code written for a 1-indexed root says i > 1. Copy-pasting comparison operators from a 1-indexed source without re-deriving them for the new origin is one of the most common heap bugs.

Quiz

Interview questions

Cheat sheet

Operation	Time	Space	Notes
parent / left / right	Θ(1)	Θ(1)	Pure arithmetic, no pointers stored
maxHeapify(a, heapSize, i)	O(lg n) worst (O(h) for a node of height h)	O(1) iterative / O(lg n) recursion stack	Assumes both children already valid heaps; sinks one node down
buildMaxHeap(a)	Θ(n) — tight bound, not the loose O(n lg n)	O(1) extra (in-place)	Most of the ⌊n/2⌋ calls are cheap (near the bottom)
heapSort(a)	Θ(n lg n) best, average, AND worst case (distinct keys; all-equal keys is Θ(n))	O(1) extra (in-place)	NOT stable; comparison sort so no lower bound below n lg n
heapMaximum()	Θ(1)	Θ(1)	Max always at the root by the heap property
heapExtractMax()	O(lg n)	O(1)	Move last element to root, shrink, maxHeapify
heapIncreaseKey(i, key)	O(lg n)	O(1)	Bubble up; errors if key < current value
maxHeapInsert(key)	O(lg n)	O(1)	Insert -∞ sentinel leaf, then heapIncreaseKey
d-ary heap insert / increaseKey	O(log_d n)	—	Shorter tree than binary (d=2)
d-ary heap extractMax	O(d · log_d n)	—	Must scan up to d children per level while sinking
Young tableau insert / extractMin / search	O(m + n)	Θ(mn) grid	2-D generalization: sorted rows AND columns