Indexed heap: a position map makes decrease-key fast

The idea: a heap that knows where everything is

A binary heap stores its items in one array, heap[slot], as a complete tree. It can find the minimum at once, but it cannot tell you where some other item is. An indexed heap (also called an indexed priority queue) adds a second array, the position map pos[item] = slot, and keeps each item's priority in key[item]. The items are small numbers, here the vertices A to H.

The two arrays are inverses of each other: pos[heap[s]] = s for every slot s, and pos[x] = −1 when x is not in the heap. The canvas checks this rule after every step and shows ✓.

Why a plain heap cannot decrease a key

Decrease-key gives an item a smaller key. The item may now be smaller than its parent, so it must sift up: compare with the parent and swap while smaller. That part costs O(log n). The hard part is the first step: where is the item? A plain heap has no index, so it must scan the array, which costs O(n) and wipes out the gain.

step of decrease-key	plain array heap	indexed heap
find the item's slot	scan, up to n reads	1 read of pos[x]
lower the key	1 write	1 write of key[x]
sift up	≤ log₂ n swaps	≤ log₂ n swaps, 2 pos writes each
total	O(n)	O(log n)

In Demo: decrease-key climbs to the root, G sits in slot 6. One read of pos[G] finds it; a plain heap would read 7 slots. G's key drops from 36 to 5, and it climbs past F:19 and D:8 in 2 compares and 2 swaps. Demo: decrease-key that stays put lowers C from 42 to 20: still not below its parent F:19, so 1 compare and no swap.

Keeping pos[] right on every swap

A swap of slots i and j moves two items, so it must rewrite two entries of the position map. Forget one and the map points at the wrong slot; the next decrease-key of that item then sifts the wrong node.

swap(i, j):
    t = heap[i]; heap[i] = heap[j]; heap[j] = t
    pos[heap[i]] = i
    pos[heap[j]] = j

Extract-min and pos = −1

Extract-min takes the item in slot 0 and sets its pos to −1. The last item moves into slot 0 (pos[last] = 0) and sifts down: find the smaller child, swap while it is smaller. Each level costs 2 compares and each swap 2 pos writes. Demo: extract-min updates pos[] takes out D:8 and B:15. After that, pos[D] = −1 answers "is D still in the queue?" in one read, which is what Demo: item already taken out shows.

• insert x, k: heap[n] = x, pos[x] = n, key[x] = k, sift up. O(log n).
• contains x: pos[x] ≠ −1. O(1).
• decrease-key x, k: s = pos[x], key[x] = k, sift up from s. O(log n).
• extract-min: pos[heap[0]] = −1, move the last item up, sift down. O(log n).

Why Dijkstra and Prim need it

Dijkstra's algorithm keeps every unfinished vertex in the queue, keyed by its distance so far. Each extract-min finalizes one vertex. Each edge that gives a shorter path is one decrease-key on the vertex at its far end. Prim's algorithm does the same with "cheapest edge to the tree" as the key. With an indexed heap both run in O((V + E) log V).

In Demo: Dijkstra's frontier every vertex starts in the heap with key ∞ except A (0). The vertices come out in the order A, C, B, D, E. B's key drops twice (∞ → 4 → 3) and D's twice (∞ → 8 → 5): each drop is a decrease-key that a plain heap could only do by scanning.

Many libraries skip the position map and use lazy deletion instead: push a new (distance, vertex) pair on every improvement and ignore stale pairs when they come out. That is simpler but lets the heap grow to E entries. A 4-ary heap makes the many decrease-keys cheaper still, and a Fibonacci heap makes them O(1) amortized.

See also Priority Queues (binary heap).

What the page leaves out

The heap holds at most 8 items with fixed names. It leaves out increase-key and delete of an arbitrary item (both find the slot with pos, then sift down or both ways), building the heap in O(n) bottom-up, items that are not small integers (a hash map then plays the role of pos[]), and the graph side of Dijkstra and Prim, which the linked pages animate.

References

Sedgewick & Wayne, IndexMinPQ.java (Algorithms, 4th ed.)

Algorithms, 4th ed., section 2.4: Priority Queues (index priority queue)

Binary heap: decrease or increase key (Wikipedia)