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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
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
03
12
25
39
48
54
6the 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