hashing and treessolid

Heaps, Priority Queues, and Heap Sort

An emergency room does not serve patients in arrival order. A broken finger waits; a heart attack goes first even if it walked in last. And look closely at what question the triage desk actually asks. Nobody ever wants the median patient, or an alphabetical printout of everyone in the building. The desk asks one question, over and over, forever: who is most urgent right now? Treat them, then ask it again.

Lesson 6 called this shape "a queue where the line is jumped" and promised the structure that runs it. This is that lesson. The contract is called a priority queue, and in lesson 6's discipline it's an ADT, a job description, not an implementation: insert an item with a priority, peek at the most urgent, remove the most urgent. That's the whole menu. No ranges, no sorted walks, no floor or ceiling, no "where is the 7".

Last lesson closed on exactly this trade. The BST maintains total order, every key ranked against every other, whether or not you ever ask, and it pays for that in pointers, in O(height) anxiety, and in the degenerate case. If the only question your workload ever asks is "what's next?", you can keep one much weaker promise instead, and the structure that keeps it is smaller, simpler, and structurally immune to the disease that kills naive BSTs. That structure is the binary heap.

The weaker invariant

Here is the entire promise: every parent beats its children. In a min-heap, "beats" means "is less than or equal to", so every parent is ≤ both of its children. Nothing about left versus right. Nothing about where any key lives globally. Compare that to the BST invariant, which constrained every node against entire subtrees on both sides; this rule is one local comparison per edge, and that's all.

Here is the heap this whole lesson lives in:

        2
      /   \
     5     3
    / \   / \
   9   7 8   4

Check it: 2 beats 5 and 3. 5 beats 9 and 7. 3 beats 8 and 4. Every parent wins, so it's a valid min-heap. Now notice what a BST would never tolerate: the 9 sits in the left subtree and the 4 sits in the right. Smaller-left, larger-right is simply not a rule here.

What did weakening the invariant cost? Ask this structure "where is the 7?" and it shrugs. The only thing the heap knows is that 7 is somewhere below something smaller than 7, which is nearly everywhere. Search is O(n), a full scan. Range queries, sorted iteration, nearest key: all gone. That loss is real.

And what survived: the root beats its children, they beat theirs, and the promise chains all the way down, so the root beats everything. The minimum of a min-heap is always at the top, available in O(1), no search required. We gave up every question except the one the emergency room asks, and that question got the best possible answer.

Complete trees pack into arrays

The heap has a second rule, and it's about shape rather than values: the tree must be complete. Every level full except possibly the last, and the last level filled left to right with no gaps. Our example is complete: level 0 full, level 1 full, level 2 full.

Completeness is what cashes the trick lesson 13 teased and lesson 14's bridge promised. Read the tree top to bottom, left to right, like text, and write the values into an array in that order:

index:  0  1  2  3  4  5  6
value: [2, 5, 3, 9, 7, 8, 4]

No pointers were stored. Instead, the family relationships become arithmetic:

children of index i:  2i + 1  and  2i + 2
parent of index i:    (i - 1) / 2   (integer division, rounds down)

Round-trip it on the real heap. Index 1 holds the 5; its children should be at 2(1)+1 = 3 and 2(1)+2 = 4, which hold 9 and 7, exactly the 5's children in the picture. Backwards: index 6 holds the 4; its parent is (6−1)/2 = 2, which holds the 3, correct again. It works at every index, and it works because the tree is complete: no gaps means the text-order numbering never skips, so the level-by-level positions line up with the arithmetic perfectly. (Some textbooks 1-index the array so the formulas become 2i, 2i+1, and i/2; same idea, off by one.)

A tree with no pointers

Say what just happened in lesson 2's vocabulary, because this is the payoff that lesson has been waiting thirteen lessons for. This is a tree with zero pointers. The BST spent two 8-byte pointers per node, 16 bytes of addresses to chaperone every value, plus an allocation per node scattered across the heap. The binary heap stores just the values, in one contiguous block: cache-warm, prefetcher-friendly, a fraction of the memory, and the tree structure is never stored at all. It's computed, on demand, from indexes.

The second gift is bigger. Last lesson's villain was the degenerate case: feed sorted input to a BST and it collapses into a height-n chain with every invariant intact. A heap cannot do that, because completeness is part of its definition. Every level is packed full before the next begins, so n nodes always stack into height exactly ⌊log₂ n⌋. Not expected height, not amortized, not "if the input is random": by construction. There is no insertion order, no adversarial stream, no input on earth that makes a heap lean. A million elements is height 19, every time. The balance anxiety that consumed the back half of lesson 14 is gone, structurally.

Sift up: insert

The promises only matter if the structure survives change, and the heap has exactly two repair moves. Here's the first.

Insert a 1 into our heap. The shape rule dictates the only legal place to grow: the next free slot on the bottom level, left to right, which is simply the end of the array. Append the 1 there; it lands at index 7, child of the 9. Shape fixed, values broken: 9 is the 1's parent, and 9 does not beat 1.

So the 1 bubbles up. Compare with the parent and swap while the child wins:

[2, 5, 3, 9, 7, 8, 4, 1]    1 vs parent 9: 1 wins, swap
[2, 5, 3, 1, 7, 8, 4, 9]    1 vs parent 5: 1 wins, swap
[2, 1, 3, 5, 7, 8, 4, 9]    1 vs parent 2: 1 wins, swap
[1, 2, 3, 5, 7, 8, 4, 9]    1 is the root, done

This is sift up (also "bubble up" or "swim"): append at the end, swap with your parent while you beat them, stop the moment you don't. Each comparison it wins on the way up is exactly the proof the invariant holds again. Worst case it walks one root-to-leaf path, and the height is ⌊log n⌋ guaranteed, so insert is O(log n), always.

Sift down: extract-min

The second move runs the other way, and it's the one the emergency room pays for. Extract the minimum from the original 7-element heap. The answer is the root, 2, at index 0. Take it. But that leaves a hole at the top, and the shape rule says a heap may only shrink at the end of the array. Hence the strange-looking move that makes this all work: take the last element, the 4, and drop it into the root's empty chair.

Shape fixed, values broken: 4 sits above 5 and 3 and doesn't beat 3. So the 4 sinks. At each step, compare the node with both children and swap with the smaller child (the smaller child is the only one fit to rule the other; swap with the larger and the invariant breaks immediately):

[4, 5, 3, 9, 7, 8]    4 vs children 5 and 3: smaller child is 3, 3 wins, swap
[3, 5, 4, 9, 7, 8]    4 vs its one child 8: 4 wins, stop

The invariant holds everywhere, and the new root is 3, the correct next minimum. This is sift down: one path from the root toward a leaf, O(log n) by the same height argument.

And that's the entire API:

operation	mechanism	cost
peek	read index 0	O(1)
insert	append, sift up	O(log n)
extract-min	swap last to root, sift down	O(log n)
search / delete arbitrary key	full scan	O(n), not what heaps are for

Two repair moves, about ten lines each. That's the whole structure.

Build-heap in O(n)

One more trick, because production asks for it constantly: you're handed a full unsorted array and want a heap now. Inserting each element costs n sift-ups, O(n log n). There's a cheaper way.

Take [9, 5, 8, 2, 7, 3, 4]. As an array it's already a complete tree; only the values are wrong. Walk backwards from the last parent (index n/2 − 1 = 2), sifting each node down:

sift down index 2 (the 8): swaps with 3      → [9, 5, 3, 2, 7, 8, 4]
sift down index 1 (the 5): swaps with 2      → [9, 2, 3, 5, 7, 8, 4]
sift down index 0 (the 9): sinks below 2, 5  → [2, 5, 3, 9, 7, 8, 4]

Out comes exactly the heap this lesson has been using. Why backwards is the win: count where the nodes live. Half of all nodes are leaves and never sink at all. A quarter sink at most one level. An eighth at most two. Only one node can ever sink the full log n. The sum telescopes: total work under 2n swaps, so build-heap is O(n), flat. Every standard library's heapify does exactly this.

The real code

Videos stay in pseudocode; here is a complete min-heap in the three course languages: sift up, sift down, insert, extract, and the O(n) build.

class MinHeap {
  private a: number[] = []
 
  static from(values: number[]): MinHeap {
    const h = new MinHeap()
    h.a = [...values]
    for (let i = (h.a.length >> 1) - 1; i >= 0; i--) h.siftDown(i) // build-heap, O(n)
    return h
  }
 
  size(): number {
    return this.a.length
  }
 
  peek(): number | undefined {
    return this.a[0] // the answer, always at index 0
  }
 
  insert(x: number): void {
    this.a.push(x) // the only gap-free place to grow
    this.siftUp(this.a.length - 1)
  }
 
  extractMin(): number | undefined {
    if (this.a.length === 0) return undefined
    const min = this.a[0]
    const last = this.a.pop()!
    if (this.a.length > 0) {
      this.a[0] = last // last element fills the hole at the root
      this.siftDown(0)
    }
    return min
  }
 
  private siftUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1
      if (this.a[parent] <= this.a[i]) return // parent beats us: invariant holds
      ;[this.a[i], this.a[parent]] = [this.a[parent], this.a[i]]
      i = parent
    }
  }
 
  private siftDown(i: number): void {
    const n = this.a.length
    while (true) {
      let smallest = i
      const l = 2 * i + 1
      const r = 2 * i + 2
      if (l < n && this.a[l] < this.a[smallest]) smallest = l
      if (r < n && this.a[r] < this.a[smallest]) smallest = r
      if (smallest === i) return // beats both children: invariant holds
      ;[this.a[i], this.a[smallest]] = [this.a[smallest], this.a[i]]
      i = smallest
    }
  }
}

type MinHeap struct{ a []int }
 
func NewMinHeap(values []int) *MinHeap {
	h := &MinHeap{a: append([]int(nil), values...)}
	for i := len(h.a)/2 - 1; i >= 0; i-- { // build-heap, O(n)
		h.siftDown(i)
	}
	return h
}
 
func (h *MinHeap) Len() int  { return len(h.a) }
func (h *MinHeap) Peek() int { return h.a[0] } // caller checks Len first
 
func (h *MinHeap) Insert(x int) {
	h.a = append(h.a, x)
	h.siftUp(len(h.a) - 1)
}
 
func (h *MinHeap) ExtractMin() int {
	min := h.a[0]
	last := len(h.a) - 1
	h.a[0] = h.a[last]
	h.a = h.a[:last]
	if len(h.a) > 0 {
		h.siftDown(0)
	}
	return min
}
 
func (h *MinHeap) siftUp(i int) {
	for i > 0 {
		parent := (i - 1) / 2
		if h.a[parent] <= h.a[i] {
			return
		}
		h.a[i], h.a[parent] = h.a[parent], h.a[i]
		i = parent
	}
}
 
func (h *MinHeap) siftDown(i int) {
	n := len(h.a)
	for {
		smallest := i
		if l := 2*i + 1; l < n && h.a[l] < h.a[smallest] {
			smallest = l
		}
		if r := 2*i + 2; r < n && h.a[r] < h.a[smallest] {
			smallest = r
		}
		if smallest == i {
			return
		}
		h.a[i], h.a[smallest] = h.a[smallest], h.a[i]
		i = smallest
	}
}

class MinHeap {
    std::vector<int> a;
 
    void sift_up(size_t i) {
        while (i > 0) {
            size_t parent = (i - 1) / 2;
            if (a[parent] <= a[i]) return;
            std::swap(a[i], a[parent]);
            i = parent;
        }
    }
 
    void sift_down(size_t i) {
        size_t n = a.size();
        while (true) {
            size_t smallest = i, l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && a[l] < a[smallest]) smallest = l;
            if (r < n && a[r] < a[smallest]) smallest = r;
            if (smallest == i) return;
            std::swap(a[i], a[smallest]);
            i = smallest;
        }
    }
 
  public:
    explicit MinHeap(std::vector<int> values = {}) : a(std::move(values)) {
        for (size_t i = a.size() / 2; i-- > 0;) sift_down(i); // build-heap, O(n)
    }
 
    size_t size() const { return a.size(); }
    int peek() const { return a[0]; } // caller checks size first
 
    void insert(int x) {
        a.push_back(x);
        sift_up(a.size() - 1);
    }
 
    int extract_min() {
        int min = a[0];
        a[0] = a.back();
        a.pop_back();
        if (!a.empty()) sift_down(0);
        return min;
    }
};

Read the two private methods against the walked examples. siftUp is the insert repair: (i - 1) >> 1 is the parent formula, the loop swaps upward while the child wins, and the early return is the "stop the moment you don't" beat. siftDown is the extract repair: it finds the smaller of up-to-two children (the bounds checks l < n, r < n handle the ragged bottom level), swaps if that child beats the current node, and follows the value down. from is the backwards build: start at the last parent, (n >> 1) - 1, and sift everything down. Note what extractMin does in exactly the order the prose did: save the root, pop the end, move it to the front, repair.

The Go version is the same machine on a slice, and it shows off how little a heap is: no nodes, no allocation per element, append and reslice are the only memory operations, and both come from lesson 3's dynamic array. The if l := ...; l < n && ... form scopes each child index to its own check, which reads nicely as "if the left child exists and wins".

One C++-specific detail worth a pause: the build loop is written for (size_t i = a.size() / 2; i-- > 0;) because size_t is unsigned, and the natural i >= 0 would loop forever (an unsigned value is always >= 0). The decrement-in-condition form visits n/2 - 1 down to 0 and stops cleanly.

What the standard libraries actually give you, one honest line each. Python: heapq, a module of functions over a plain list, min-heap, with heapify as the O(n) build; this is the most-used heap on earth. Go: container/heap, an interface you implement with five methods (Len, Less, Swap, Push, Pop), famously awkward, and as of this writing the stdlib still has no generic replacement, so plenty of teams hand-roll exactly the code above. C++: std::priority_queue (a max-heap by default; pass std::greater<> for min), plus the in-place algorithm trio make_heap / push_heap / pop_heap over any vector. JavaScript: nothing built in; you write the class above or import one.

Priority queues in production

Once you know the contract, you see it running everywhere.

Timers. Every setTimeout you have ever scheduled is a priority queue entry. Node's runtime (via libuv) keeps pending timers in a min-heap ordered by fire time, because the event loop only ever needs one answer: which timer fires soonest, to size its next sleep. Go's runtime keeps per-scheduler timer heaps too (a slightly wider-than-binary heap, same machine). Millions of pending timers, and "what's next" stays O(log n) to maintain and O(1) to read.

Merging k sorted streams. Lesson 10's external sort ended with k sorted runs on disk that had to become one output. The tool is a min-heap of size k holding each run's head element: extract the smallest, emit it, refill from the run it came from. Each output element costs O(log k), where k is maybe 64, not O(log n) over the billion total records. LSM-tree storage engines (the RocksDB and LevelDB family) run exactly this k-way merge during compaction, continuously, as their core background activity.

Top-K. The marquee example, worked in its own section below, because it's the most interview-transferable idea in this lesson.

Dijkstra's shortest path. The famous graph algorithm keeps its frontier of candidate nodes in a priority queue and repeatedly extracts the closest one. That's a dsa-patterns story; the structure will be sitting here waiting for it. (One honest footnote: textbook Dijkstra wants a decrease-key operation, lowering a priority in place, which plain binary heaps don't directly support. Real implementations dodge it by inserting duplicate entries and skipping stale ones on extraction. File the name away.)

Top-K: the min-heap that finds maximums

Find the 10 largest items in a stream of a billion. Sorting is off the table: O(n log n) work, and holding a billion 64-bit keys is 8GB of memory before you start. The heap answer uses ten slots.

And here's the part that trips everyone the first time: you want the ten largest, so you keep a min-heap. Not max. Min.

Think about what the root of that ten-element min-heap is. The heap holds the ten best candidates seen so far, and its root is the smallest of them: the weakest member of the club. The bouncer at the door. Now stream the billion items past it:

New item arrives. Compare it with the root, once.
If it can't beat the weakest member of the club, it has no business inside: discard, O(1). For a billion items against a top-10, this is what happens almost every time.
If it does beat the root, the weakest member is out: replace the root with the newcomer and sift down, O(log 10), three or four swaps.

One pass, O(n log k) worst case and close to O(n) in practice, ten slots of memory. A max-heap of all billion items answers the wrong question brilliantly: it surfaces the single largest instantly but holds everything to do it. The min-heap works because the question you ask a billion times is about the threshold: who is the weakest of my current best? Keep that answer at the root and everything else is one comparison. The same shape runs leaderboards, "10 slowest queries" dashboards, and monitoring top-talkers, anywhere "biggest few out of way too many" appears.

Heap sort: the sorting story, completed

Lesson 10's table had a row marked "wait for lesson 15": the comparison sort with guaranteed O(n log n) and no extra memory. You can now build it in two sentences.

Flip the comparison: "parent beats children" now means parent is larger, a max-heap, and the largest element sits at index 0. Then sort in place:

function heap_sort(a):
    build_max_heap(a)                  # backwards sift-downs, O(n)
    for end from n-1 down to 1:
        swap a[0], a[end]              # max goes to its final slot
        sift_down(a, 0, end)           # heap is now a[0..end-1], repair it

Walk one round on the max-heap [9, 7, 8, 2, 5, 3, 4]. The maximum, 9, is at the root, and the back of the array is exactly where a sorted array wants its maximum. So swap root and last: [4, 7, 8, 2, 5, 3 | 9]. The 9 is parked in its final sorted position, permanently outside the heap. The new root 4 is wrong, so sift down: 4 versus children 7 and 8, larger child 8 wins, swap; 4 versus its one remaining child 3, 4 wins, stop. [8, 7, 4, 2, 5, 3 | 9], a valid max-heap of six, and the next round will park the 8 next to the 9. Swap, shrink, sift, until the heap is gone and the array is sorted, smallest to largest, in place.

The ledger, completing lesson 10's table:

	quicksort	merge sort	heap sort
worst case	O(n²)	O(n log n)	O(n log n)
extra space	O(log n) stack	O(n) buffer	O(1)
stable	no	yes	no
memory behavior	streams	streams	commutes

Heap sort is the only one with both the guaranteed bound and constant space. So why isn't it simply the sort? The last row, in lesson 2's vocabulary. Watch the addresses one deep sift-down touches: index 0, then 1, then 3, then 7, then 15: each level lives twice as far away as the last, so in a big array nearly every level is a fresh cache line, a miss. Sift-down commutes. Quicksort's partition streams: two pointers marching through adjacent memory, the exact pattern the prefetcher rewards. Same big-O shape, physically cheaper steps, so quicksort usually wins on real hardware.

Which is why production uses heap sort exactly the way lesson 10 promised: as insurance. Introsort, the engine inside C++'s std::sort, runs quicksort while counting recursion depth; if depth blows past about 2 log n, the pivots have gone bad and the O(n²) cliff is near, so it hands the whole job to heap sort. Guaranteed O(n log n), no extra memory, disaster cancelled. Quicksort's constants with heap sort's floor: that's the sort your programs have been calling all along.

What the module taught

This closes the module. Three structures, three contracts: the hash table bought O(1) lookups by destroying order entirely; the BST kept total order and paid in pointers, height anxiety, and rebalancing machinery; the heap keeps exactly one bit of order, "what's next", in a flat array with log n guarantees by construction. The module's lesson in one line: order is not free, so buy exactly as much of it as your queries need.

And now step back further, because every structure in this course so far has assumed your data has one of two shapes. A sequence: arrays, lists, stacks, queues, sorted runs. Or a hierarchy: trees, heaps, one parent above, children below. A social network is neither. A road map is neither. Package dependencies, microservice call graphs, the internet itself: things pointing at things, many to many, no single parent, no first element. That shape is a graph, it's the course's final module, and the first problem is more basic than any algorithm: how do you even store one in memory? Two classic answers, with a familiar trade between them. That's next.

Command Palette