Array-like radix heap with decrease query（chmin 操作が可能な基数ヒープ）
(data_structure/radix_heap_array.hpp)

View this file on GitHub
Last update: 2022-01-08 20:23:44+09:00
Include: #include "data_structure/radix_heap_array.hpp"

radix_heap.hpp におけるラベルを非負整数に限り，更にラベル $i$ に対応したキーに対する decrease 操作（いわゆる chmin）を $O(1)$ で行えるもの．

使用方法

以下のように，Dijkstra 法を効率的に実行可能なクエリが揃っている．以下，$D$ を UnsignedInt 型のビット数とする．

radix_heap_array<UnsignedInt>(): Radix heap の初期化．各 $i \ge 0$ について $A_i = \infty$ と初期化．計算量は $O(D)$．
bool empty(): $A_i < \infty$ である $i$ が存在しないとき，及びそのときに限り true を返す．$O(1)$
int argmin_pop(): $A_i$ が最小値をとる $i$ を一つとって $A_i = \infty$ と更新し，$i$ を返す．償却 $O(D)$
void chmin(UnsignedInt x, int i): $A_i$ を $\min(A_i, x)$ で更新する．$x$ の値はこれまで pop() や top() の対象となった最大の値以上でなければならない．$O(1)$

以下は既存のライブラリとの互換性のために実装されている．

void pop(): $A_i$ が最小の $i$ の一つについて，$A_i = \infty$ と更新する．償却 $O(D)$
pair<UnsignedInt, int> top(): $A_i$ が最小の $i$ の一つについて，$(A_i, i)$ の組を返す．償却 $O(D)$
void emplace(Uint vnew, int i) （非推奨）: chmin() と同じ効果で，STL における同名の関数とは意味が大きく異なる．既存のライブラリに含まれる priority_queue をコンテスト中に素早くこのライブラリに置き換えることを可能にするためにのみ存在している．$O(1)$

Dijkstra 法による最短 $s$ - $t$ パスの計算は次のように書ける：

vector<unsigned long long> dist(N, numeric_limits<unsigned long long>::max());
vector<int> prv(N, -1);
dist[s] = 0;
radix_heap_array<unsigned long long> pq;
pq.chmin(0, s);
while (!pq.empty()) {
    int now = pq.argmin_pop();
    if (now == t) break;
    for (const auto &nx : to[now]) {
        int nxt = nx.first;
        if (dist[nxt] > dist[now] + nx.second) {
            dist[nxt] = dist[now] + nx.second;
            prv[nxt] = now;
            pq.chmin(dist[nxt], nxt);
        }
    }
}

Verified with

data_structure/test/radix_heap_array.dijkstra.test.cpp

Code

#pragma once
#include <array>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

template <class Uint> class radix_heap_array {
    int sz;
    Uint last;
    std::array<std::vector<std::pair<Uint, int>>, std::numeric_limits<Uint>::digits + 1> v;

    struct smallpii {
        unsigned b : 7;
        int j : 25;
    };
    std::vector<smallpii> i2bj;

    template <class U, typename std::enable_if<sizeof(U) == 4>::type * = nullptr>
    static inline unsigned bucket(U x) noexcept {
        return x ? 32 - __builtin_clz(x) : 0;
    }
    template <class U, typename std::enable_if<sizeof(U) == 8>::type * = nullptr>
    static inline unsigned bucket(U x) noexcept {
        return x ? 64 - __builtin_clzll(x) : 0;
    }

    void pull() {
        if (!v[0].empty()) return;
        int b = 1;
        while (v[b].empty()) ++b;
        last = v[b].back().first;
        for (int j = 0; j < int(v[b].size()); j++) last = std::min(last, v[b][j].first);
        for (int j = 0; j < int(v[b].size()); j++) {
            int i = v[b][j].second;
            auto bnxt = bucket(v[b][j].first ^ last);
            i2bj[i] = {bnxt, int(v[bnxt].size())}, v[bnxt].emplace_back(std::move(v[b][j]));
        }
        v[b].clear();
    }

public:
    radix_heap_array() : sz(0), last(0) {}
    bool empty() const noexcept { return sz == 0; }
    int argmin_pop() {
        pull(), --sz;
        int i = v[0].back().second;
        i2bj[i].j = -1;
        v[0].pop_back();
        return i;
    }
    void chmin(Uint vnew, int i) {
        if (i >= int(i2bj.size())) i2bj.resize(i + 1, {0, -1});
        if (i2bj[i].j < 0) {
            auto b = bucket(vnew ^ last);
            ++sz, i2bj[i] = {b, int(v[b].size())}, v[b].emplace_back(vnew, i);
        } else if (v[i2bj[i].b][i2bj[i].j].first > vnew) {
            auto bold = i2bj[i].b, bnew = bucket(vnew ^ last);
            if (bnew < bold) {
                int ilast = v[bold].back().second, j = i2bj[i].j;
                std::swap(v[bold][j], v[bold].back());
                i2bj[ilast].j = j, i2bj[i] = {bnew, int(v[bnew].size())};
                v[bnew].emplace_back(vnew, i), v[bold].pop_back();
            } else {
                v[bold][i2bj[i].j].first = vnew;
            }
        }
    }

    void pop() { argmin_pop(); }
    std::pair<Uint, int> top() { return pull(), v[0].back(); }
    [[deprecated("NOT usual emplace() opeation!")]] void emplace(Uint vnew, int i) {
        chmin(vnew, i);
    }

    void clear() noexcept { sz = 0, last = 0, i2bj.clear(); }
};

#line 2 "data_structure/radix_heap_array.hpp"
#include <array>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

template <class Uint> class radix_heap_array {
    int sz;
    Uint last;
    std::array<std::vector<std::pair<Uint, int>>, std::numeric_limits<Uint>::digits + 1> v;

    struct smallpii {
        unsigned b : 7;
        int j : 25;
    };
    std::vector<smallpii> i2bj;

    template <class U, typename std::enable_if<sizeof(U) == 4>::type * = nullptr>
    static inline unsigned bucket(U x) noexcept {
        return x ? 32 - __builtin_clz(x) : 0;
    }
    template <class U, typename std::enable_if<sizeof(U) == 8>::type * = nullptr>
    static inline unsigned bucket(U x) noexcept {
        return x ? 64 - __builtin_clzll(x) : 0;
    }

    void pull() {
        if (!v[0].empty()) return;
        int b = 1;
        while (v[b].empty()) ++b;
        last = v[b].back().first;
        for (int j = 0; j < int(v[b].size()); j++) last = std::min(last, v[b][j].first);
        for (int j = 0; j < int(v[b].size()); j++) {
            int i = v[b][j].second;
            auto bnxt = bucket(v[b][j].first ^ last);
            i2bj[i] = {bnxt, int(v[bnxt].size())}, v[bnxt].emplace_back(std::move(v[b][j]));
        }
        v[b].clear();
    }

public:
    radix_heap_array() : sz(0), last(0) {}
    bool empty() const noexcept { return sz == 0; }
    int argmin_pop() {
        pull(), --sz;
        int i = v[0].back().second;
        i2bj[i].j = -1;
        v[0].pop_back();
        return i;
    }
    void chmin(Uint vnew, int i) {
        if (i >= int(i2bj.size())) i2bj.resize(i + 1, {0, -1});
        if (i2bj[i].j < 0) {
            auto b = bucket(vnew ^ last);
            ++sz, i2bj[i] = {b, int(v[b].size())}, v[b].emplace_back(vnew, i);
        } else if (v[i2bj[i].b][i2bj[i].j].first > vnew) {
            auto bold = i2bj[i].b, bnew = bucket(vnew ^ last);
            if (bnew < bold) {
                int ilast = v[bold].back().second, j = i2bj[i].j;
                std::swap(v[bold][j], v[bold].back());
                i2bj[ilast].j = j, i2bj[i] = {bnew, int(v[bnew].size())};
                v[bnew].emplace_back(vnew, i), v[bold].pop_back();
            } else {
                v[bold][i2bj[i].j].first = vnew;
            }
        }
    }

    void pop() { argmin_pop(); }
    std::pair<Uint, int> top() { return pull(), v[0].back(); }
    [[deprecated("NOT usual emplace() opeation!")]] void emplace(Uint vnew, int i) {
        chmin(vnew, i);
    }

    void clear() noexcept { sz = 0, last = 0, i2bj.clear(); }
};

Array-like radix heap with decrease query（chmin 操作が可能な基数ヒープ） (data_structure/radix_heap_array.hpp)

使用方法

Verified with

Code

Array-like radix heap with decrease query（chmin 操作が可能な基数ヒープ）
(data_structure/radix_heap_array.hpp)