Decrease-Key & Indexed Heap

Sometimes you need to UPDATE a key's priority while it's in the heap. Critical for Dijkstra's algorithm.

Naive: search the heap (O(n)), then sift-up. Bad.

Indexed heap: maintain a hash map key -> heap_index. Updates are O(1) lookup + O(log n) sift.

Every swap during sift-up/down must update idx[swapped_key].

This is the standard implementation of priority queues for graph algorithms (Dijkstra, Prim) where vertex priorities change as edges relax.

Fibonacci heaps offer amortized O(1) decrease-key but the constants are bad — practical implementations of Dijkstra use plain binary heaps for most graph sizes.