Module A-1 — Heaps: Min-Heap, Max-Heap, and Heapify
What this module covers: A heap is a binary tree (Module P-4) with one structural guarantee a BST (Module P-5) doesn't have: it's always a complete tree, which means its height is always O(log n), regardless of insertion order — no degeneration possible, unlike the BST worst case. This module covers how that guarantee is implemented (as an array, with no pointers at all), insertion and extraction, and why a heap is the structure behind every priority queue.
The Heap Property and Completeness
A heap enforces one rule at every node — the heap property: in a min-heap, every parent is smaller than or equal to both its children; in a max-heap, every parent is larger than or equal to both its children. Note what this rule does not require: there's no left-smaller-right-larger ordering between siblings, the way a BST requires (Module P-5) — only a parent-to-child relationship.
text
The second guarantee — completeness — is what makes heaps structurally different from a BST: every level of the tree is completely filled, except possibly the last level, which fills strictly left to right with no gaps. This isn't a property that depends on the order values happen to be inserted in (unlike a BST, where sorted-order insertion produces a degenerate, linear tree per Module P-5) — completeness is a structural invariant the insert and extract operations actively maintain on every single operation, which is exactly why a heap's height is always O(log n), with no adversarial-input failure mode to worry about.
No Pointers Needed: The Array Representation
Because a heap is always complete, its shape is entirely predictable — which means it can be stored as a plain array, with parent/child relationships computed by arithmetic instead of left/right pointers (Module P-4, P-5):
typescript
This is a direct callback to Module F-2: array indexing is O(1), and because a heap's shape is always predictable (complete, filling left to right), every node's parent and children can be found by pure arithmetic on its index — no node object, no left/right fields, no pointer-chasing at all. This is a meaningfully more compact representation than the tree node classes from Modules P-4 and P-5.
Insert: Add at the End, Then Bubble Up
typescript
Adding at the end of the array preserves completeness automatically (it's always the correct next slot in a left-to-right-filling complete tree). The new value might now violate the heap property relative to its parent, so bubbleUp repeatedly swaps it upward until either it reaches the root or finds a parent it's no longer smaller than. Since the tree's height is O(log n) (guaranteed by completeness), this swap-upward chain can happen at most O(log n) times — insertion is O(log n), full stop, with no worst-case degradation possible.
Extract-Min: Swap, Remove, Bubble Down
typescript
The minimum is always at index 0 — the direct consequence of the heap property applied all the way to the root. Removing it leaves a gap; moving the last element into that gap (rather than any other element) preserves completeness for free, since removing the last array slot is exactly the "correct" way to shrink a complete tree by one node. That relocated element likely violates the heap property now, so bubbleDown repeatedly swaps it with whichever child is smaller, until it settles somewhere it belongs. Same O(log n) bound as insertion, for the identical structural reason.
Heaps vs. BSTs: Two Different Kinds of Order
Worth stating the contrast plainly, since both are binary trees maintaining some ordering invariant: a BST (Module P-5) supports O(log n) search for an arbitrary value, because its left-smaller/right-larger rule holds recursively across the whole tree — but that guarantee only holds if the tree stays balanced, which insertion order can break. A heap supports O(1) access to the minimum (or maximum) only — it makes no promise at all about finding an arbitrary value quickly (searching a heap for an arbitrary value is O(n), no better than a plain unsorted array) — but its O(log n) height is unconditionally guaranteed by completeness, regardless of insertion order. Different trees, solving different problems: "give me the smallest thing, repeatedly, fast" is a heap's job; "find this specific value quickly" is a BST's job.
Where This Shows Up in Your Stack
Priority queues in job scheduling: BullMQ's priority-based job processing, and job schedulers generally, need "give me the highest-priority pending job" in O(log n) — exactly extractMin (or its max-heap equivalent), repeated as jobs complete and new ones arrive.
Operating system and Kubernetes schedulers: deciding which process or pod to run/place next based on priority or resource score is the same extract-highest-priority operation, applied at the OS or cluster-orchestration level instead of an application-level job queue.
Dijkstra's algorithm (Module A-6, immediately relevant soon): repeatedly extracting the unvisited node with the smallest known distance is the exact extractMin operation — this is precisely why Dijkstra's algorithm is described as "BFS with a min-heap standing in for a plain queue."
Heap sort (Module A-2, next): building a heap from an array and repeatedly extracting the min (or max) produces a fully sorted array — a direct, practical application of the two operations built in this module.
Summary
A heap enforces a parent-to-child ordering (min-heap: parent ≤ children; max-heap: parent ≥ children) — a weaker, cheaper-to-maintain invariant than a BST's full left-smaller/right-larger rule.
Completeness — every level full except possibly the last, filled left to right — guarantees O(log n) height unconditionally, with no insertion-order-dependent degeneration, unlike a plain BST.
Because shape is always predictable, a heap is stored as a plain array, with parent/child relationships computed by index arithmetic rather than pointers — no node objects required.
Insert adds at the end (preserving completeness for free) and bubbles up; extract-min swaps the root with the last element (again preserving completeness for free) and bubbles down — both O(log n), guaranteed.
A heap and a BST solve different problems: O(1) access to the minimum/maximum (heap) vs. O(log n) search for an arbitrary value (balanced BST) — knowing which one a problem actually needs is the real decision point.
The next module, Heap Applications: Heap Sort, Kth Largest Element, and Merge K Sorted Lists, puts these two operations to work on three classic problems, each choosing a heap for a different reason.
Knowledge Check
Why does a heap's height stay O(log n) unconditionally, regardless of the order elements are inserted in — unlike a plain BST, which can degenerate to O(n) height on adversarial (e.g., sorted) insertion order?
In extractMin, why is the last element in the array specifically chosen to replace the removed root, rather than, say, one of the root's direct children?
According to the module, what is the key functional difference between what a heap guarantees efficiently versus what a balanced BST guarantees efficiently?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionparentIndex(i:number):number{return Math.floor((i -1)/2);}functionleftChildIndex(i:number):number{return2* i +1;}functionrightChildIndex(i:number):number{return2* i +2;}
classMinHeap{private heap:number[]=[];insert(value:number):void{this.heap.push(value);// add at the very end — the next available slot, keeping completenessthis.bubbleUp(this.heap.length -1);}privatebubbleUp(index:number):void{while(index >0){const parent =parentIndex(index);if(this.heap[parent]<=this.heap[index])break;// heap property already satisfied — stop[this.heap[parent],this.heap[index]]=[this.heap[index],this.heap[parent]];// swap upward index = parent;}}}
classMinHeap{// ...(insert/bubbleUp above)extractMin():number|undefined{if(this.heap.length ===0)returnundefined;const min =this.heap[0];const last =this.heap.pop()!;// Module F-2 — O(1), removing from the endif(this.heap.length >0){this.heap[0]= last;// move the last element to the root...this.bubbleDown(0);// ...then restore the heap property from the top down}return min;}privatebubbleDown(index:number):void{while(true){const left =leftChildIndex(index);const right =rightChildIndex(index);let smallest = index;if(left <this.heap.length &&this.heap[left]<this.heap[smallest]) smallest = left;if(right <this.heap.length &&this.heap[right]<this.heap[smallest]) smallest = right;if(smallest === index)break;// heap property satisfied here — stop[this.heap[index],this.heap[smallest]]=[this.heap[smallest],this.heap[index]]; index = smallest;}}}