Radix heap （基数ヒープ）
(data_structure/radix_heap.hpp)

• View this file on GitHub
• Last update: 2022-01-08 20:23:44+09:00
• Include: #include "data_structure/radix_heap.hpp"
• Link: https://github.com/iwiwi/radix-heap

std::priroity_queue と同様の機能を提供するヒープだが，「最後に取り出した値以上の値しか追加できない」という制約があり（本実装では更に，top() などのクエリで最後に「見た」以上の値しか追加できないという制約も加わる），また本実装では符号なし整数型に使用が限られる．ヒープがキーとして持つ整数型のビット数を $D$ とおくと，一度追加した要素に対しては演算が高々 $O(D)$ 回しか発生しないため，クエリ毎の計算量は償却 $O(D)$ で，定数倍にも優れているとされる．Dijkstra 法や各種フローアルゴリズムの定数倍高速化などに活用できる．

使用方法

radix_heap<unsigned, string> pq, pq2;

pq.push(5, "a");
pq.emplace(1, "b");
cout << pq.top_key() << ' ' << pq.top_label() << '\n'; // 1 b
cout << pq.top().first << ' ' << pq.top().second << '\n'; // 1 b

pq.push(2, "c");
pq.push(3, "d");

cout << "size=" << pq.size() << '\n'; // size=4

while (pq.size()) {
    cout << pq.top_key() << ' ' << pq.top_label() << '\n';
    // 1 b
    // 2 c
    // 3 d
    // 5 a
    pq.pop();
}

pq.push(50, "heap1");
pq2.push(100, "heap2");
pq.swap(pq2);
cout << pq.top_label() << ' ' << pq2.top_label() << '\n'; // heap2 heap1

問題例

• No.1288 yuki collection - yukicoder 最小費用流の計算中に使用するヒープを std::priority_queue から radix_heap に変更することで定数倍が改善される（2,261 ms → 886 ms）．

リンク

• [1] R. K. Ahuja et al., “Faster algorithms for the shortest path problem,” Journal of the ACM 37(2), 213-223, 1990.
• iwiwi/radix-heap: An implementation of radix heap 本コードはこちらを参考に実装された．こちらは符号付整数型や浮動小数点数型にも対応する．
• 色々なダイクストラ高速化

Verified with

• data_structure/test/radix_heap.dijkstra.test.cpp
• graph/test/shortest_path.test.cpp

Code

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

// Radix heap for unsigned integer
// https://github.com/iwiwi/radix-heap
template <class Uint, class Label, typename std::enable_if<std::is_unsigned<Uint>::value>::type * = nullptr>
class radix_heap {
    int sz;
    Uint last;
    std::array<std::vector<std::pair<Uint, Label>>, std::numeric_limits<Uint>::digits + 1> v;

    template <class U, typename std::enable_if<sizeof(U) == 4>::type * = nullptr>
    static inline int 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 int bucket(U x) noexcept {
        return x ? 64 - __builtin_clzll(x) : 0;
    }

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

public:
    radix_heap() : sz(0), last(0) {
        static_assert(std::numeric_limits<Uint>::digits > 0, "Invalid type.");
    }
    std::size_t size() const noexcept { return sz; }
    bool empty() const noexcept { return sz == 0; }
    void push(Uint x, const Label &val) { ++sz, v[bucket(x ^ last)].emplace_back(x, val); }
    void push(Uint x, Label &&val) { ++sz, v[bucket(x ^ last)].emplace_back(x, std::move(val)); }
    template <class... Args> void emplace(Uint x, Args &&...args) {
        ++sz, v[bucket(x ^ last)].emplace_back(std::piecewise_construct, std::forward_as_tuple(x),
                                               std::forward_as_tuple(args...));
    }
    void pop() { pull(), --sz, v[0].pop_back(); }
    std::pair<Uint, Label> top() { return pull(), v[0].back(); }
    Uint top_key() { return pull(), last; }
    Label &top_label() { return pull(), v[0].back().second; }
    void clear() noexcept {
        sz = 0, last = 0;
        for (auto &vec : v) vec.clear();
    }
    void swap(radix_heap<Uint, Label> &a) {
        std::swap(sz, a.sz), std::swap(last, a.last), v.swap(a.v);
    }
};

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

// Radix heap for unsigned integer
// https://github.com/iwiwi/radix-heap
template <class Uint, class Label, typename std::enable_if<std::is_unsigned<Uint>::value>::type * = nullptr>
class radix_heap {
    int sz;
    Uint last;
    std::array<std::vector<std::pair<Uint, Label>>, std::numeric_limits<Uint>::digits + 1> v;

    template <class U, typename std::enable_if<sizeof(U) == 4>::type * = nullptr>
    static inline int 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 int bucket(U x) noexcept {
        return x ? 64 - __builtin_clzll(x) : 0;
    }

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

public:
    radix_heap() : sz(0), last(0) {
        static_assert(std::numeric_limits<Uint>::digits > 0, "Invalid type.");
    }
    std::size_t size() const noexcept { return sz; }
    bool empty() const noexcept { return sz == 0; }
    void push(Uint x, const Label &val) { ++sz, v[bucket(x ^ last)].emplace_back(x, val); }
    void push(Uint x, Label &&val) { ++sz, v[bucket(x ^ last)].emplace_back(x, std::move(val)); }
    template <class... Args> void emplace(Uint x, Args &&...args) {
        ++sz, v[bucket(x ^ last)].emplace_back(std::piecewise_construct, std::forward_as_tuple(x),
                                               std::forward_as_tuple(args...));
    }
    void pop() { pull(), --sz, v[0].pop_back(); }
    std::pair<Uint, Label> top() { return pull(), v[0].back(); }
    Uint top_key() { return pull(), last; }
    Label &top_label() { return pull(), v[0].back().second; }
    void clear() noexcept {
        sz = 0, last = 0;
        for (auto &vec : v) vec.clear();
    }
    void swap(radix_heap<Uint, Label> &a) {
        std::swap(sz, a.sz), std::swap(last, a.last), v.swap(a.v);
    }
};

Back to top page