Stage 1 · Code
Heaps & Priority Queues
Merge K Sorted Lists
Optimal merge using min heap vs divide and conquer.
7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Min Heap Approach
Push head of each non-empty list into min-heap (by node value). Pop min, add to result, push its next node. Repeat until heap empty. O(N log K) where N = total nodes.
Gomerge-k-lists-with-heap.go
41 linesLn 1, Col 1Go
Heap stores (node, value) pairs. Always extract smallest current head. Add its next to heap. Dummy head simplifies list building.
Divide and Conquer
Recursively merge pairs of lists: merge lists[0] with lists[1], lists[2] with lists[3], etc. Reduce K by half each round. O(N log K) same as heap but no heap overhead.
Gomerge-k-lists-divide-and-conquer.go
31 linesLn 1, Col 1Go
Recursively merge pairs. Bottom-up: each level processes all N nodes. log K levels. O(N log K). Often faster in practice than heap due to less overhead.
Comparison
| Aspect | Min Heap | Divide & Conquer |
|---|---|---|
| Time | O(N log K) | O(N log K) |
| Space | O(K) heap | O(log K) recursion |
| Constants | Higher (heap ops) | Lower (simple merge) |
| Stability | Stable | Stable if mergeTwo stable |
| Parallelizable | Harder | Easier (independent merges) |
| Code complexity | More | Less |
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.