Two-Heap and Dijkstra

What is this?

Two heap problems, each breaking one of the assumptions the easier versions rely on.

Dijkstra normally accumulates by addition over non-negative weights. Here the weights are probabilities that multiply, and you want the largest product rather than the smallest sum. The algorithm survives — but only because of a property you should be able to state.

The two-heap running median normally only grows. Here it slides, so elements leave — and a binary heap has no way to remove something from its middle.

💡 Fun fact: lazy deletion works because a heap only ever guarantees its top. A stale element buried in the middle is harmless — it cannot affect any query until it reaches the top, and at that moment you discard it instead of returning it. The cost is amortised, since each element is discarded at most once. The catch is that the heap's physical size stops meaning anything, so the balance condition must be maintained against a separately tracked logical count.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: Dijkstra needs only that extending a path cannot improve it — multiplication by factors in [0, 1] satisfies that as surely as adding non-negative weights. And when a heap must forget something it cannot reach, leave it there and skip it on the way out.

1. Dijkstra with a product

best = [0.0] * n
best[start] = 1.0
heap = [(-1.0, start)]                      # max-heap via negation
while heap:
    p, node = heapq.heappop(heap)
    p = -p
    if node == end: return p                # first pop of the target is optimal
    if p < best[node]: continue             # a stale, worse entry
    for nxt, w in adj[node]:
        if p * w > best[nxt]:
            best[nxt] = p * w
            heapq.heappush(heap, (-best[nxt], nxt))
return 0.0

The correctness argument is the part to say aloud: every probability lies in [0, 1], so extending a path can only reduce its value. That is the exact analogue of non-negative edge weights, and it is why the first pop of a node is final. If a weight could exceed 1, the greedy would be unsound and you would need Bellman-Ford.

The if p < best[node]: continue line is the other standard idiom — rather than decreasing a key in place, which a binary heap cannot do, you push a better entry and ignore the outdated one when it surfaces. That is lazy deletion again, in its most common disguise.

2. Two heaps that can forget

lower  = max-heap of the smaller half
upper  = min-heap of the larger half
pending = map from value -> how many copies are logically deleted

on the window sliding:
   add(entering)        push into the correct half, then rebalance
   remove(leaving)      pending[leaving] += 1
                        adjust the LOGICAL size of whichever half owns it
                        if it happens to be on top, prune immediately
   prune(heap)          while heap's top is pending, pop it and decrement
   median               prune both tops, then read

Three rules keep it honest. Prune before reading a top, never after. Rebalance on logical sizes, because the physical ones now include ghosts. And when the leaving element is not on top, do nothing but record it — hunting for it is what you are avoiding.

For integer windows there is a simpler alternative worth mentioning: an ordered multiset or a sorted list with binary-search insertion gives O(n log k) with far less bookkeeping, and in an interview it is a perfectly good first answer before the two-heap version.

3. A 30-second worked example (lazy deletion)

Window [1, 3, 5] sliding to [3, 5, 7] — the 1 leaves, the 7 arrives.

lower (max-heap): [3, 1]        upper (min-heap): [5]
median = 3

remove 1:   pending = {1: 1}
            1 is in lower, so lower's LOGICAL size drops to 1
            1 is not on top (3 is) → leave it buried

add 7:      7 > 3 → push to upper → upper = [5, 7]
            logical sizes: lower 1, upper 2 → rebalance
            move upper's top (5) to lower → lower = [5, 3, 1*], upper = [7]

median:     prune lower's top → 5 is not pending → median = 5   ✓

The 1 is still physically present and never caused a problem, because it never reached the top while it mattered. Sorted, the window is [3, 5, 7] and the median is indeed 5.

4. Where you'll actually meet this

• Network routing over lossy links. Most-reliable path is exactly the multiplicative Dijkstra, used where each hop has a delivery probability.
• Risk and reliability engineering. Chained component reliabilities multiply; finding the most reliable configuration is this search.
• Real-time analytics. Rolling p50 over a sliding window, where old samples must expire.
• Trading systems. Windowed median price, where re-sorting per tick is unaffordable.
• Job schedulers. Lazy deletion is how cancelled jobs are handled without rebuilding the queue.

5. Problems in this chapter

▶ Path with Maximum Probability

Most probable path between two nodes. Dijkstra with a max-heap and multiplication; valid because factors in [0, 1] only shrink a path.
Pattern: Dijkstra with a multiplicative objective. Target: O(E log V) time, O(V) space.

▶ Sliding Window Median

Median of every window of size k. Two heaps straddling the median, with lazy deletion for departing elements and rebalancing on logical sizes.
Pattern: two heaps + lazy deletion. Target: O(n log k) time, O(k) space.

6. Common pitfalls 🚫

• Not stating why multiplicative Dijkstra is valid. The [0, 1] range is the whole justification, and an interviewer will ask.
• Forgetting the negation for a max-heap in Python, or applying it inconsistently between push and pop.
• Rebalancing on physical heap sizes. Ghost elements make those numbers meaningless.
• Pruning after reading the top instead of before, which returns a deleted value.
• Searching the heap for the departing element. That is O(k) and is precisely what lazy deletion exists to avoid.
• Integer division for an even-sized window's median. Average the two middle values as a float.
• Skipping the stale-entry guard in Dijkstra, which reprocesses nodes and inflates the running time.

7. Key takeaways

1. Dijkstra needs "extending cannot improve", not addition. Probabilities in [0, 1] satisfy it.
2. A heap only guarantees its top, which is exactly why burying stale entries is safe.
3. Lazy deletion turns an impossible removal into an amortised skip.
4. Track logical sizes separately once ghosts exist, and rebalance on those.
5. Prune before reading, always.
6. Offer the simpler structure first. A sorted container is a legitimate O(n log k) answer before the two-heap version.
7. Why interviewers like it: both problems look like versions you have seen, and both fail if you apply the remembered solution without checking which assumption changed.

Order: Path with Maximum Probability → Sliding Window Median.