Advanced Heap & Priority Queue

Heaps were “find the k largest” back in Week 5. This week is the patterns that actually show up in harder problems: two heaps, k-way merge, greedy scheduling, and lazy deletion.

⚖️ Two heaps for a running median

Keep a max-heap for the smaller half and a min-heap for the larger half, balanced so their sizes differ by at most one. Then the median sits right at the tops:

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []                 # max-heap, stored as negatives
        self.hi = []                 # min-heap

    def add(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))   # balance by value
        if len(self.hi) > len(self.lo):                    # balance by size
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def median(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Each insert is O(log n), median is O(1). The push-to-one-then-rebalance dance is the part to get right.

🔀 K-way merge

Merging k sorted lists with a heap of each list’s current front is O(N log k), which beats concatenate-then-sort’s O(N log N):

import heapq

def merge_k(lists):
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    out = []
    while heap:
        val, li, idx = heapq.heappop(heap)
        out.append(val)
        if idx + 1 < len(lists[li]):
            heapq.heappush(heap, (lists[li][idx + 1], li, idx + 1))
    return out

The (value, list_index, elem_index) tuple keeps the heap ordered while remembering where each item came from.

🗓️ Greedy scheduling with a priority queue

A lot of interval and scheduling problems are greedy plus a heap: sort by start, then use a min-heap of end times to track how many resources are busy. That’s the Meeting Rooms II pattern, and the heap’s size at any moment is just the number of overlapping intervals. Neat once you see it.

🧹 Lazy deletion

Heaps don’t remove an arbitrary element efficiently, so the trick is to not even try. Mark it stale and skip it when it eventually floats to the top:

while heap and is_stale(heap[0]):
    heapq.heappop(heap)              # drop outdated entries only when they surface

This keeps sliding-window and remove-by-key heap problems at O(log n) amortized, and it’s cleaner than trying to fish something out of the middle.

⚠️ Things that bit me

• Letting the two heaps get unbalanced. Rebalance sizes after every insert.
• Tuples that aren’t comparable, when two priorities tie and the payloads can’t be compared. Add a tie-break index.
• Trying to delete from the middle of a heap. Use lazy deletion instead.

🏋️ Problems I did this week

• Find Median from Data Stream, Hard
• Merge k Sorted Lists, Hard
• Meeting Rooms II, Medium
• Task Scheduler, Medium
• Sliding Window Median, Hard

📝 What I want to remember

Two heaps track a streaming median, and k-way merge beats a full sort when k is small. Priority queues drive greedy scheduling, where heap size equals active overlaps. And when you can’t remove from the middle of a heap, lazy-delete stale entries at the top.