Lessons from Merge K Lists

What did you learn?

$1.$ Heaps track "frontiers" efficiently. The heap contains one candidate from each source.

$2.$ The heap size is bounded by $k$, not $n$. Bounded size gives you $O(n \log k)$ instead of $O(n \log n)$.

$3.$ Store enough metadata in heap entries to know where the next element comes from. This pattern applies to merging any $k$ sorted streams: files, arrays, iterators.