One head per list
You have K already-sorted lists and want one merged sorted output. The naive concat-then-sort is O(N log N) and throws away the fact that each list is sorted. The heap way keeps only K candidates at a time: the current front of each list.
A min-heap of those K heads always exposes the global smallest. Pop it, append to the output, then push the next element from whichever list it came from. Repeat until the heap drains. Only K items live in the heap at once, so each of the N pops costs O(log K).
// seed with each list's head
for i in 0..K: heap.push(list[i][0], i, 0)
while heap:
(v, i, j) = heap.pop() # global min
out.append(v)
if j+1 < len(list[i]):
heap.push(list[i][j+1], i, j+1)
for i in 0..K: heap.push(list[i][0], i, 0)
while heap:
(v, i, j) = heap.pop() # global min
out.append(v)
if j+1 < len(list[i]):
heap.push(list[i][j+1], i, j+1)
Time Complexity
O(N log K)
N total elements, each pushed and popped once from a heap of size ≤ K.
Space Complexity
O(K)
The heap holds at most one head per list, so K entries.
Live Visualization
rows separated by | , values by commas
Current head (in heap)
Popped this step
Written to output
Consumed
Sorted lists (heads highlighted)
Heap of heads min-heap by value
Merged output
popped = –
from list = –
heap size = 0
written = 0
Step 0 / 0
Popped min
–
smallest head
From list
–
pull its next
Heap size
0
≤ K heads
Written
0
of N
Set lists and hit Play to merge them with a min-heap of heads.
✓ Done
Speed
Step-by-step trace
| # | Action | Popped | From | Pushed next | Heap (val·list) | Output |
|---|
C++ — Merge k Sorted Lists (LC 23)