0
Challenge · 59Heaps & Top-K

Merge k sorted lists

Heapsused in ~70% of apps

Merging two sorted lists is easy: compare two fronts and take the smaller. Merging five thousand is the same idea with one problem, which is that finding the smallest of five thousand fronts is now the expensive part. A heap is exactly the tool for that.

Core idea. Put the front value of every list into a heap, so the heap holds one candidate per list and never more. Take the smallest, write it down, and immediately refill from the list it came from. Repeat until the heap is empty.
Playground, this isn't a screenshot
taking the smallest, repaired downwards
1
3
2
5
9
8
4
the same thing, as an array
1
0
3
1
2
2
5
3
9
4
8
5
4
6
the smallest value is always at slot 0. Reading it costs nothing at all
step 1 of 7

Swapping with the smaller child is the whole correctness argument. Swap with the larger one and the rule breaks immediately.

↑ play a little first, then dig in