What does an indexed heap's position map buy you when a queued item's priority changes?

## The gap in a plain heap's contract A binary heap supports `insert`, `peek-min` and `extract-min`, all resting on one invariant: every parent is no greater than its children. That invariant deliberately says **nothing** about where any particular key lives. Two elements with unrelated keys can be anywhere relative to each other, so there is no way to navigate to a specific element — the only entry point is the root. That is fine until a queued element's priority changes. Consider a build scheduler holding 50,000 queued jobs keyed by deadline. A release gets promoted, so one queued job's deadline jumps from tomorrow to ten minutes from now. The heap has that job somewhere in its array, and to change its key you must first find it: a linear O(n) scan. The repair itself is cheap — one sift-up — but the search dominates and turns a logarithmic structure into a linear one for the operation that the scheduler performs most often. ## What the indexed variant adds An **indexed heap** (also called an addressable or index-min priority queue) pairs the heap array with a **position map**: `pos[id] = the current index of the element with that id` If the ids are dense small integers — job slots numbered 0..n-1, for example — `pos` is just another array, so lookups are a single indexed read. If ids are opaque tokens, it is a hash-based map with expected O(1) lookup. The heap array itself is unchanged. The operations become: - **insert(id, key)** — append, record `pos[id]`, sift up. - **extract-min** — take index 0, move the last element into it, drop the trailing slot, erase the old id's `pos` entry, sift down. - **decrease-key(id, k)** — `i = pos[id]`; write the smaller key at `a[i]`; `sift_up(i)`. O(log n). - **increase-key(id, k)** — same lookup, but `sift_down(i)`, because a bigger key sinks. - **change-key / delete(id)** — lookup, then repair in whichever direction is needed; a general change may need to try both, and a deletion moves the last element into the hole and then sifts up **or** down depending on how it compares with its parent. - **contains(id)** — O(1), which a plain heap cannot answer at all. ## The invariant that makes it work One sentence governs the whole structure: > For every index `i` in the heap array, `pos[a[i].id] == i`. Every routine that moves an element — swap during a sift, the append in insert, the last-element relocation in extract-min or delete — must re-establish it for **each** element it moved. There is no partial version of this invariant that is still useful. ## What it costs - **Memory**: an extra entry per element, so O(n) additional space, plus whatever overhead the map implementation carries. - **Constant factors**: every swap inside a sift now performs two extra writes. On an extract-heavy loop that is a measurable slowdown of the operations you did not want to slow down. - **Identity**: the heap can no longer hold bare values. Elements need stable, distinct ids — two jobs with the same deadline must still be distinguishable, or one will overwrite the other's map entry. - **Surface area**: more code paths that must all maintain the same invariant, which is exactly where this structure's characteristic bugs come from. ## When you do not need it The honest alternatives, when reprioritization is rare: 1. **Scan and sift.** O(n) per change is fine if the queue holds hundreds of items or changes arrive once a minute. Simplicity has value. 2. **Rebuild.** If a batch of priorities changes at once, discarding and rebuilding bottom-up is Θ(n) for the whole batch — cheaper than n individual O(log n) updates once the batch is large. 3. **Push a revised copy and skip superseded entries on the way out.** No position map at all, at the cost of a heap that holds more entries than there are live jobs, so its size is bounded by total updates rather than by the live set. The indexed heap earns its complexity when reprioritization is a first-class, frequent operation on a large queue — a scheduler whose deadlines move while jobs wait is exactly that shape. Reach for it because a measured operation is on the critical path, not because it appears in the textbook chapter on priority queues.