Heaps and Priority Queues
Merging many ordered sources
One candidate from each source in a heap, and the answer comes out in order.
Why it works
One candidate each is enough
To merge several already-ordered sources, you never need more than one item from each in play at once. The next item overall must be the best among the current fronts, because everything behind a front is worse than that front.
So the heap holds at most one entry per source. Pop the best, emit it, and push that source's next item to replace it.
Key idea
The entry has to say where it came from
When you pop a value you need to know which source to advance, so the heap entry carries the source identifier and the position within it alongside the ordering key.
This is the derived-key idea again: key first, everything needed to continue after it. Forgetting to carry the source is the most common way this gets stuck after the first pop.
The three moving parts
A common design version of this: several users each have a list of posts in reverse chronological order, and you must produce the newest few across all of them.
Whatever the domain, the same three things have to be right. Seed the heap with one entry per source. Give each entry enough to continue with. Replace what you pop from the source it came from.
Tip
When the sources run the other way
These sources ascend, so the min-heap is already pointing the right way. A feed ordered newest first descends, and the fix is the negation from the first lesson: negate the key going in and negate it coming out.
Nothing else about the merge changes. Recognizing that a reversed ordering is a sign flip rather than a different algorithm saves rewriting the loop backwards.
Tip
Stopping early is most of the benefit
Producing only the first few items means the loop runs that many times rather than over everything. Combining all the sources and sorting would touch every item, which is wasted work when you want ten out of a million.
Cost is O(s) to seed the heap for s sources, then O(log s) per item produced. For a limit of L that is O(s + L log s), independent of how much data sits behind each source.
Key idea
You have solved one of these before
Merging k sorted linked lists appeared in Unit 7, where you solved it by pairing lists and merging two at a time. This heap version is the other standard solution.
Both are O(n k log k) for k lists of n nodes. Divide and conquer allocates nothing extra and processes in rounds; the heap holds k entries and produces output in a single streaming pass. That problem returns below as a review so you can build it the second way.
Cost of the k-way merge
Merging k sorted sources holding n items in total, using a heap with one entry per source. Give the time and the extra space beyond the output.
Time
Space
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Merge K Sorted Lists, with a heap this time
You solved this in Unit 7 by pairing lists and merging two at a time. Build it again with a heap holding one node from each list. Same complexity, completely different shape, and having both is the point.