Indexed Binary Heaps and the Cost of Decrease-Key

A heap that supports only insert and extract-min needs nothing but the array. A heap that must also lower the priority of an element already inside it — the operation a graph search performs when it discovers a cheaper route to a node it has already queued — needs a way to find that element’s slot. Scanning for it costs O(n), which erases the advantage of the heap in the very algorithms that use it. The fix is a side table mapping each element’s identity to its current array index, and keeping that table correct is the whole difficulty.

The operation that has no path

Consider what the heap layout provides. From a slot, the parent and children are reachable by arithmetic. From a key, nothing is reachable: the partial order records only ancestor-descendant relations, so a key buried in one subtree cannot be located from the root without visiting both subtrees. There is no search path to follow because the structure never recorded one.

Insertion avoids the problem by construction — the new key is placed at a known index, the end of the array, and sifts from there. Extraction avoids it too, since it removes the root, whose index is always zero. Decrease-key is the first operation whose input is an arbitrary element, and it has no index to start from.

The naive responses are both poor. Scanning the array to find the element costs Θ(n) per call, so a sequence of n such operations costs Θ(n²). Removing the element and reinserting it costs two logarithmic operations and, more importantly, requires locating it first, which is the same scan. A balanced search tree over the heap would provide lookup in O(log n) but reintroduces the pointers and rotation machinery the array layout was chosen to avoid.

A map from element to slot

The standard solution keeps the array as it is and adds an integer array pos of length equal to the number of distinct elements, where pos[v] is the index at which element v currently sits, or a sentinel such as −1 when v is not in the heap. Every routine that moves an element updates both sides of the mapping.

The invariant is simple to state and easy to violate: after every operation, for every element v in the heap, heap[pos[v]] == v. Swaps are the only place elements move, so the swap is where the bookkeeping belongs.

/* Heap over the elements 0 .. n-1; an element may be absent, marked by pos[v] == -1. */
typedef struct {
    int  *key;    /* key[element] */
    int  *heap;   /* heap[slot] = element */
    int  *pos;    /* pos[element] = slot, or -1 */
    size_t n;
} iheap;

static void swap_slots(iheap *h, size_t i, size_t j) {
    int a = h->heap[i], b = h->heap[j];
    h->heap[i] = b; h->heap[j] = a;
    h->pos[b] = (int)i; h->pos[a] = (int)j;
}

With that in place, decrease-key becomes a direct translation: read i = pos[v], lower key[v], then sift up from i. Sift-up moves the element toward the root only, so it terminates in at most ⌊log₂ n⌋ swaps. Each swap writes four integers instead of the two a plain heap index array writes — two slots of heap and the two matching entries of pos — which is the concrete price of the mapping.

The same handle supports three further operations at the same cost. Increasing a key is the mirror image and sifts down. Deleting an arbitrary element forces it to the root by swapping it upward unconditionally, then calls extract-min; each swap updates pos for both elements, so the map stays consistent. And “contains” becomes an O(1) test of pos[v] != -1, which is useful in graph code that must avoid re-queuing a settled vertex.

Which structures need the map, and which refuse it

Not every priority queue is designed around a fixed element universe. A general-purpose container that accepts arbitrary values has no integer identity to index by, and the position map would have to be a hash table keyed on the value, adding a hash computation and a probe to every comparison-adjacent operation. This is why the C++ standard’s std::priority_queue exposes no decrease-key or erase: it is a container adaptor over a sequence, and it never learns which element is which. Boost’s heap library takes the other position: it exposes handles to individual nodes and an update routine that accepts one, with the caller responsible for keeping the handle valid.

The alternative for general containers is lazy deletion. Instead of modifying an element in place, insert a second copy with the new key and mark the old entry as dead, or simply accept duplicates and discard a popped entry whose key disagrees with the current best-known value for that element. The graph-search idiom does exactly this: push (new_dist, v) on every improvement, and on popping check whether the stored distance still matches the array of best distances, skipping the entry if not.

Lazy deletion costs no extra bookkeeping per element and no position array, and the heap operations remain O(log n). It pays in memory and in heap size: with m edges relaxed, the heap can hold up to m entries instead of n, so each operation costs O(log m) rather than O(log n), and the array occupies m slots. The two logs differ by at most a factor of two in exponent, since m ≤ n² for a simple graph; the extra slots are the larger cost. The position map wins when the element universe is small, dense, and integer-valued; lazy deletion wins when the caller cannot supply stable identities.

Failure modes that the invariant does not catch

Stale handles are the characteristic defect. If an element is removed from the heap and later reinserted, an old handle that was not invalidated points at whatever now occupies that slot. With a position map the slot check heap[pos[v]] == v detects this, but only if it is written; without it, a decrease-key on a stale handle silently corrupts some unrelated element’s key.

Duplicate elements expose a second problem. If the same element is inserted twice without the map noticing, two slots claim the same pos value, and a sift in one subtree invalidates the other. The map therefore assumes at most one live copy per element, which is precisely the assumption that lazy deletion violates on purpose. Mixing the two strategies in one structure produces exactly this corruption.

Index width is a quieter issue. A position map of 32-bit indices caps the heap at about 2.1 billion elements, and the map adds one more array as large as the payload. For a heap of a few thousand elements both arrays fit in cache and the map costs little; for a heap of hundreds of millions of four-byte keys, the map is several hundred megabytes of its own, and each swap writes to two arrays whose lines may evict each other. Implementations that care often store the position inside the element record rather than in a parallel array, trading one indirection for locality.

There is also a correctness subtlety worth stating explicitly, because it explains why deletion is done by unconditional swaps. Since key is indexed by element, the “overwrite the key with −∞ and sift up” shortcut is not available: it would destroy the element’s real priority, and if that element is later re-inserted it carries a falsified key. Sifting upward by swapping with the parent avoids the problem entirely, because it never reads or writes key.

What the handle buys elsewhere

The position map is not specific to binary heaps; it is the general mechanism by which any array-backed heap becomes an addressable priority queue, and the same idea reappears in structures chosen for different asymptotics. Fibonacci heaps achieve their O(1) amortised decrease-key not by a position map but by cutting a node loose from its parent rather than sifting it, as Fibonacci heaps and the decrease-key argument explains: the caller holds the node itself, and the cut is O(1) because the tree is allowed to become a forest. Pairing heaps keep both the parent pointer and the two-pass merge instead, in pairing heaps and self-adjusting merges. Both replace the index arithmetic with explicit links, and both pay for O(1) decrease-key with worse constants on extraction.

For the array-backed heap, the trade is settled: a position map adds one array of integers and four writes per swap, and in exchange an entire class of algorithms — anything that relaxes edge weights — becomes implementable without a linear scan. The structures that follow in this cluster exist largely to remove the remaining logarithmic factor from that operation.