What this module covers: Module A-1 built the two core heap operations. This module puts them to work on three classic problems, each choosing a heap for a genuinely different reason — sorting in place with no extra memory, avoiding a full sort when only a partial answer is needed, and merging many sorted sources at once without paying for repeated pairwise merges.
Build a max-heap from the entire array, then repeatedly extract the maximum and place it at the end of the shrinking unsorted region:
function heapSort(arr: number[]): number[] { const n = arr.length;
// Build a max-heap in place: heapify every non-leaf node, from the last one up to the root for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { siftDown(arr, i, n); }
// Repeatedly move the current max (always at index 0) to the end, then shrink the heap by one for (let end = n - 1; end > 0; end--) { [arr[0], arr[end]] = [arr[end], arr[0]]; siftDown(arr, 0, end); // restore heap property, but only within the shrinking unsorted region [0, end) }
return arr; }
function siftDown(arr: number[], i: number, size: number): void { let largest = i; const left = 2 * i + 1, right = 2 * i + 2;
if (left < size && arr[left] > arr[largest]) largest = left; if (right < size && arr[right] > arr[largest]) largest = right;
Building the max-heap is O(n) (a detail that looks surprising at first — heapifying n/2 nodes at O(log n) each looks like O(n log n), but the math works out to O(n) overall because most nodes are near the bottom of the tree and need very little sifting). The n extractions afterward are each O(log n), for O(n log n) total — matching Modules P-9 and P-10's other O(n log n) sorts, but this one sorts entirely in place, using O(1) extra space (just the swap), unlike merge sort's O(n) auxiliary array requirement. Like quicksort, heap sort is not stable — the swaps involved in sifting can reorder equal elements relative to each other, exactly the same trade-off flagged for quicksort in Module P-10.
Finding the Kth largest element doesn't require fully sorting anything — and a heap makes that explicit, using only a fixed-size min-heap of k elements:
function findKthLargest(nums: number[], k: number): number { const minHeap = new MinHeap(); // Module A-1's MinHeap
for (const num of nums) { minHeap.insert(num); if (minHeap.size() > k) { minHeap.extractMin(); // discard the smallest — it can't be among the k largest } }
return minHeap.peek()!; // the smallest value remaining IS the kth largest overall }
The heap only ever holds the k largest values seen so far — every time it grows past size k, the smallest of those is discarded, since it's now provably too small to be among the true k largest once one more genuinely-larger candidate has been seen. This runs in O(n log k) — n insertions/extractions, each O(log k) since the heap never exceeds size k — which beats a full O(n log n) sort whenever k is meaningfully smaller than n (finding the top 10 out of 10 million items, for instance, is O(n log 10), not O(n log n)). Module P-10's quickselect (using the same partitioning as quicksort, but recursing into only the one side that contains the target rank) solves the same problem in O(n) average time — genuinely faster on average — but without the min-heap version's O(k) space bound or its natural fit for a streaming input, where you don't have the whole array in memory at once to partition.
Module P-2 merged two sorted linked lists in O(n + m). Merging k sorted lists by repeatedly pairwise-merging them (merge list 1 and 2, then merge that result with list 3, and so on) costs O(n × k) in the worst case, where n is the total number of elements — each of the k merge passes touches most of the elements again. A heap does better:
function mergeKLists(lists: (ListNode<number> | null)[]): ListNode<number> | null { const minHeap = new MinHeap<{ node: ListNode<number> }>(/* compare by node.value */);
// Seed the heap with the first node of each non-empty list — at most k entries at any time for (const list of lists) { if (list) minHeap.insert({ node: list }); }
const dummy = new ListNode(0); // Module P-2's dummy-node trick let tail = dummy;
while (!minHeap.isEmpty()) { const { node } = minHeap.extractMin()!; // the smallest head among all k lists, in O(log k) tail.next = node; tail = tail.next;
if (node.next) minHeap.insert({ node: node.next }); // push this list's next candidate back in }
return dummy.next; }
The heap never holds more than k elements at once — one "current candidate" per list — so each extraction and each insertion is O(log k), not O(log n). Across all n total elements being merged (every node is inserted into and extracted from the heap exactly once over the whole run), that's O(n log k) overall — a real, meaningful improvement over the O(n × k) pairwise approach whenever k is large, because the heap is doing in O(log k) what pairwise merging was redundantly re-scanning large portions of the data to achieve.
Heap sort in memory-constrained environments (embedded systems, or any context where merge sort's O(n) auxiliary array genuinely can't be afforded) gets a guaranteed O(n log n) sort with O(1) extra space — a real, practical reason to reach for it over merge sort specifically when memory, not stability, is the binding constraint.
Top-K queries — "top 10 trending posts," "10 slowest database queries in the last hour," "top 100 highest-spending customers" — are exactly findKthLargest's shape, generalized to return the whole top-k set rather than just the boundary value, and are a common analytics pattern precisely because a full sort of potentially millions of rows is wasteful when only a small top slice is ever needed.
Merging sorted log streams from multiple servers (reconstructing a single chronological timeline from k separate, individually-time-ordered log files) is mergeKLists directly — each server's log is one "list," already sorted by timestamp, and the min-heap approach avoids the O(n × k) cost of naively concatenating and re-sorting everything from scratch.
Database engines merging sorted result shards (a distributed query that gathers pre-sorted partial results from several nodes and needs one final globally-sorted result) is the same k-way merge problem, at a different layer of the stack.
Heap sort builds a max-heap, then repeatedly extracts the max into place — O(n log n), in-place with O(1) extra space, but not stable, the same trade-off profile as quicksort (Module P-10).
Finding the Kth largest element only needs a fixed-size (k) min-heap, discarding the smallest candidate whenever the heap exceeds size k — O(n log k), which beats a full sort when k is much smaller than n, and naturally handles streaming input; quickselect (Module P-10) is faster on average (O(n)) but needs the full array available to partition.
Merging k sorted lists with a size-k min-heap (one current candidate per list) costs O(n log k), a real improvement over the O(n × k) cost of naive pairwise merging when k is large.
All three reuse the exact insert/extractMin pair built in Module A-1 — the value here is recognizing which shape of problem calls for a heap in the first place, not new heap mechanics.
The next module, Union-Find: Path Compression and Union by Rank, introduces a structure built for a different question entirely — not "what's the smallest/largest," but "are these two things connected?"
Knowledge Check
Why is heap sort described as "in-place," while merge sort (Module P-9) is not, even though both achieve O(n log n) time?
In findKthLargest, why is it safe to discard the minimum value whenever the heap's size exceeds k, rather than needing to keep every value seen so far?
Why does mergeKLists achieve O(n log k) overall, rather than O(n log n), given that n (total elements across all lists) is generally much larger than k (the number of lists)?
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.
Written by Jatin Jain Saraf · Architect of SupraScan