K-Way Merge, Two Heaps and Scheduling

Heaps & Top-K, lesson 3 of 3

K-Way Merge, Two Heaps and Scheduling

Three heap patterns that show up again and again in interviews.

13 min, 0 of 3 activities solved

Getting Python ready… examples can run in a moment.

1. K-way merge

You have k sorted lists (log files, sorted runs, the rows of a sorted matrix) and want one sorted output. The next output is always the smallest of the k current heads, and a heap finds that in O(log k):

Push (value, list_index, element_index) for each non-empty list's first element.
Pop the smallest, append it to the output.
Push the next element from the same list.

The heap never holds more than k items, so merging N total elements costs O(N log k). The indexes in the tuple tell you where to fetch the successor, and they also break ties.

Example

Merging three sorted lists

Python also has heapq.merge(*lists), a lazy iterator doing exactly this. Know it, but be ready to write the loop (and the linked-list version, LeetCode 23) by hand.

Quiz

What does this print?

[1, 2, 3, 4, 5, 7]

[1, 4, 7, 2, 5, 3]

[[1, 2, 3], [4, 5], [7]]

[7, 5, 4, 3, 2, 1]

2. Two heaps: the running median

Split the numbers seen so far into two halves:

low  (max-heap)    |   high (min-heap)
smaller half       |   larger half
     top = max(low) <= min(high) = top

Keep two invariants: everything in low is <= everything in high, and low has the same size as high or one more. Then the median is either low's top (odd count) or the average of both tops (even count): O(1) to read, O(log n) to add.

Adding x: push it into low, move low's max over to high (this keeps the order invariant), and if high is now bigger, move high's min back. low is a max-heap, so store negated values.

Example

Running median, traced

The halves stay balanced and the boundary sits right at the middle. The same trick answers "median of a sliding window" (with lazy deletion, see below).

Quiz

In the two-heap median, why is the lower half a max-heap?

Because its largest value sits next to the middle and must be read in O(1)

Because Python's heapq only supports max-heaps

So that the lower half stays sorted

It doesn't matter; both halves could be min-heaps

3. Scheduling: "what happens next?"

When you simulate events over time, a heap keyed by time tells you which event comes first:

Meeting rooms: sort meetings by start, keep a min-heap of end times of rooms in use. If the earliest end is <= the new start, reuse that room (pop), then push the new end. The heap size is the number of rooms.
CPU / task schedulers: a max-heap of what's ready (by count or priority) plus a queue or second heap of what's cooling down until a time.
Dijkstra (graphs unit): a min-heap of (distance, node) is just "process the closest thing next".

Example

How many meeting rooms?

Each meeting pushes once and pops at most once: O(n log n) including the sort.

Exercise

Sort a nearly sorted list

Every element of nums is at most k positions away from where it belongs in sorted order. Write sort_k_sorted(nums, k) that returns a new sorted list in O(n log k).

Key idea: the smallest remaining element must be among the next k + 1 candidates, so a heap of size k + 1 is enough.

sort_k_sorted([2, 1, 4, 3, 6, 5], 1)
-> [1, 2, 3, 4, 5, 6]