Build Lab: Indexed 4-Ary Min/Max Priority Queue with O(log_d N) decreaseKey

Architecture Specification: Bidirectional Permutation Invariant (heap[] $\leftrightarrow$ pos[])

In this Build Lab, you will engineer a cache-aligned Indexed 4-Ary Min-Priority Queue capable of driving production Dijkstra shortest-path solvers, A* pathfinders, and cancelable timer subsystems. The data structure maintains three flat arrays indexed over external IDs $u \in [0, M)$ and heap positions $i \in [0, N)$:

• keys[u]: Stores the current priority key associated with external handle $u$.
• heap[i] ($0 \le i < N$): The 4-ary heap array storing external handles $u$, ordered by keys[heap[i]]. For slot $i$, its parent is $(i - 1) \gg 2$ and its 4 children are $(i \ll 2) + 1 \dots (i \ll 2) + 4$.
• pos[u] ($0 \le u < M$): Stores the current heap index $i$ of handle $u$, or $-1$ if $u$ is not currently in the priority queue.

Production Reference Implementation: Complete Indexed 4-Ary Min-PQ

// C++20: Production Indexed 4-Ary Min-Priority Queue with Hole-Sinking & O(log_4 N) Updates
#include <vector>
#include <cassert>
#include <utility>

template <typename Key, int D = 4>
class IndexedDAryMinPQ {
    std::vector<int> heap; // heap[i] = external handle u at heap slot i
    std::vector<int> pos;  // pos[u]  = heap slot i of external handle u (-1 if absent)
    std::vector<Key> keys; // keys[u] = priority key of handle u

    void siftUp(int i) noexcept {
        int u = heap[i];
        const Key& k = keys[u];
        while (i > 0) {
            int p = (i - 1) / D;
            int parentHandle = heap[p];
            if (!(k < keys[parentHandle])) break;
            heap[i] = parentHandle;
            pos[parentHandle] = i;
            i = p;
        }
        heap[i] = u;
        pos[u] = i;
    }

    void siftDown(int i) noexcept {
        int u = heap[i];
        const Key& k = keys[u];
        const int n = static_cast<int>(heap.size());
        while (true) {
            int firstChild = D * i + 1;
            if (firstChild >= n) break;
            int lastChild = std::min(n - 1, firstChild + D - 1);
            int bestChild = firstChild;
            for (int c = firstChild + 1; c <= lastChild; ++c) {
                if (keys[heap[c]] < keys[heap[bestChild]]) {
                    bestChild = c;
                }
            }
            if (!(keys[heap[bestChild]] < k)) break;
            heap[i] = heap[bestChild];
            pos[heap[i]] = i;
            i = bestChild;
        }
        heap[i] = u;
        pos[u] = i;
    }

public:
    explicit IndexedDAryMinPQ(int maxHandles) : pos(maxHandles, -1), keys(maxHandles) {
        heap.reserve(maxHandles);
    }

    bool empty() const noexcept { return heap.empty(); }
    int size() const noexcept { return static_cast<int>(heap.size()); }
    bool contains(int u) const noexcept { return pos[u] != -1; }
    int peekMinHandle() const noexcept { return heap[0]; }
    const Key& peekMinKey() const noexcept { return keys[heap[0]]; }
    const Key& keyOf(int u) const noexcept { return keys[u]; }

    void insert(int u, Key key) {
        assert(!contains(u));
        int idx = static_cast<int>(heap.size());
        heap.push_back(u);
        pos[u] = idx;
        keys[u] = std::move(key);
        siftUp(idx);
    }

    void decreaseKey(int u, Key newKey) {
        assert(contains(u) && !(keys[u] < newKey));
        keys[u] = std::move(newKey);
        siftUp(pos[u]);
    }

    void changeKey(int u, Key newKey) {
        assert(contains(u));
        bool smaller = (newKey < keys[u]);
        keys[u] = std::move(newKey);
        if (smaller) siftUp(pos[u]);
        else siftDown(pos[u]);
    }

    void erase(int u) {
        int i = pos[u];
        assert(i != -1);
        int lastHandle = heap.back();
        heap.pop_back();
        pos[u] = -1;
        if (i < static_cast<int>(heap.size())) {
            heap[i] = lastHandle;
            pos[lastHandle] = i;
            siftUp(i);
            siftDown(i);
        }
    }

    std::pair<int, Key> popMin() {
        int minHandle = heap[0];
        Key minKey = std::move(keys[minHandle]);
        erase(minHandle);
        return {minHandle, std::move(minKey)};
    }
};