Indexed Heaps, decrease-key & Lazy Deletion

August 2026 · 22 min read

Everything so far assumed you only ever touch the root. Real workloads want more: Dijkstra wants to lower a vertex's tentative distance; a scheduler wants to cancel a queued job; a sliding window wants to evict the element leaving it. All three need to reach an arbitrary element, and a plain heap cannot — finding it is O(n).

There are two answers. One is exact and adds a layer of bookkeeping; the other is approximate, far simpler, and what almost everyone actually ships.

Lazy Deletion: The Practical Answer

Do not delete. Mark, and skip on the way out.

The insight is that a stale entry is only a problem when it reaches the root. Buried in the interior it harms nothing. So instead of removing it, push the corrected entry and discard the obsolete one when it surfaces:

// Dijkstra, again: push the improved distance and let the old entry rot
if (nd < dist[v]) {
    dist[v] = nd;
    pq.push({nd, v});
}
...
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;              // stale: the authoritative value moved on

The pattern generalises whenever you have an authoritative record outside the heap — here dist[]. The heap becomes a set of hints: possibly outdated, always verifiable in O(1) against the source of truth.

When there is no natural authority, use an explicit tombstone map:

#include <unordered_map>
#include <queue>

template <class T>
class LazyHeap {
    std::priority_queue<T, std::vector<T>, std::greater<T>> heap;
    std::unordered_map<T, int> pending;      // value -> copies awaiting deletion
    std::size_t live = 0;                    // real element count

    void prune() {
        while (!heap.empty()) {
            auto it = pending.find(heap.top());
            if (it == pending.end() || it->second == 0) break;
            if (--it->second == 0) pending.erase(it);
            heap.pop();
        }
    }

public:
    void push(const T& x)   { heap.push(x); ++live; }
    void erase(const T& x)  { ++pending[x]; --live; }        // O(1), no search
    std::size_t size() const { return live; }
    bool empty()       const { return live == 0; }

    const T& top() { prune(); return heap.top(); }
    void     pop() { prune(); heap.pop(); --live; }
};

Three points that are easy to get wrong. live must be tracked separately, because heap.size() counts ghosts. Pruning happens only at the root and only on access — scanning for tombstones would defeat the purpose. And erase is O(1) precisely because it never touches the heap.

The Indexed Heap: The Exact Answer

To genuinely mutate an arbitrary element you need to know where it is. Add a map from element identity to array position, and maintain it inside every swap:

#include <vector>
#include <unordered_map>
#include <functional>

template <class Key, class Priority, class Compare = std::less<Priority>>
class IndexedHeap {
    struct Entry { Key key; Priority prio; };

    std::vector<Entry> a;
    std::unordered_map<Key, std::size_t> where;    // key -> index in a
    Compare less;

    void place(std::size_t i, Entry e) {           // single choke point for writes
        a[i] = std::move(e);
        where[a[i].key] = i;                       // index map stays in sync
    }

    void sift_up(std::size_t i) {
        Entry e = std::move(a[i]);
        while (i > 0) {
            std::size_t p = (i - 1) / 2;
            if (!less(e.prio, a[p].prio)) break;
            place(i, std::move(a[p]));
            i = p;
        }
        place(i, std::move(e));
    }

    void sift_down(std::size_t i) {
        Entry e = std::move(a[i]);
        std::size_t n = a.size();
        for (;;) {
            std::size_t l = 2 * i + 1;
            if (l >= n) break;
            std::size_t c = (l + 1 < n && less(a[l+1].prio, a[l].prio)) ? l + 1 : l;
            if (!less(a[c].prio, e.prio)) break;
            place(i, std::move(a[c]));
            i = c;
        }
        place(i, std::move(e));
    }

public:
    bool contains(const Key& k) const { return where.count(k) != 0; }

    void push(const Key& k, const Priority& p) {
        a.push_back({k, p});
        where[k] = a.size() - 1;
        sift_up(a.size() - 1);
    }

    // The operation std::priority_queue cannot do.
    void update(const Key& k, const Priority& p) {
        auto it = where.find(k);
        if (it == where.end()) { push(k, p); return; }
        std::size_t i = it->second;
        Priority old = a[i].prio;
        a[i].prio = p;
        if (less(p, old)) sift_up(i);              // priority improved: move up
        else              sift_down(i);            // priority worsened: move down
    }

    void erase(const Key& k) {
        auto it = where.find(k);
        if (it == where.end()) return;
        std::size_t i = it->second;
        where.erase(it);

        if (i == a.size() - 1) { a.pop_back(); return; }   // it was the last slot

        place(i, std::move(a.back()));             // last element fills the hole
        a.pop_back();
        sift_down(i);                              // may need to go either way
        sift_up(i);
    }

    const Key& top() const { return a[0].key; }
    bool     empty() const { return a.empty(); }
};

Two subtleties worth flagging. Every write to the array goes through place, which is the only way the index map stays correct — a single raw a[i] = ... anywhere else silently corrupts it and the bug surfaces much later. And erase calls both sift directions, because the element promoted from the back may be smaller or larger than what it replaced; only one of the two calls will do anything.

Which One to Use

Use lazy deletion by default. It is what competitive programmers and most production Dijkstra implementations use, and the reason is the arithmetic: log E <= 2 log V, so the exact version buys a constant factor at the cost of a hash map lookup on every operation — which frequently makes it slower in wall-clock terms despite the better bound.

Use an indexed heap when: memory is bounded and deletions are frequent; you must query “is this key queued, and at what priority”; or you are implementing a long-lived structure (an event simulator, an OS scheduler) where unbounded ghost accumulation is unacceptable.

Practice

• Network Delay Time medium — implement lazy deletion, then the indexed version, and measure both.
• Sliding Window Maximum hard — heap with lazy deletion; compare against the monotonic deque, which is O(n).
• Design Twitter medium — k-way merge of feeds with deletions.
• Sliding Window Median hard — two heaps plus lazy deletion, from Part 9.
• Seat Reservation Manager medium — a clean case for a plain min-heap with reinsertion.