Radix Heap
(data-structure/radix-heap.hpp)

• View this file on GitHub
• Last update: 2020-12-05 07:59:51+09:00
• Include: #include "data-structure/radix-heap.hpp"

Radix Heap

概要

Radix Heap(基数ヒープ)とは、単調順位ヒープ(追加した値が最後に取り出した値より大きい必要があるヒープ)の一種である。std::priority_queueと比べて定数倍が軽いことからDijkstra法に用いて定数倍高速化に使用される。

使い方

• RadixHeap<Key, Val>(): コンストラクタ。Keyは整数型のみを取る。
• push(Key, Val): ヒープにpushする。
• pop(): ヒープの要素のうち最小のものをpopして返す。
• size(): ヒープ内の要素数を返す。
• empty(): ヒープが空かどうかを返す。

Required by

• ダイクストラ法(定数倍高速化) (shortest-path/dijkstra-fast.hpp)
• ダイクストラ法(Radix Heap) (shortest-path/dijkstra-radix-heap.hpp)
• ダイクストラ法(復元付き) (shortest-path/dijkstra-with-restore.hpp)

Verified with

• verify/verify-aoj-grl/aoj-grl-1-a-fast-dijkstra.test.cpp
• verify/verify-aoj-grl/aoj-grl-1-a-radix-heap.test.cpp
• verify/verify-unit-test/dijkstra.test.cpp
• verify/verify-unit-test/radix-heap.test.cpp
• verify/verify-yosupo-graph/yosupo-shortest-path-2.test.cpp
• verify/verify-yosupo-graph/yosupo-shortest-path-3.test.cpp
• verify/verify-yuki/yuki-1320.test.cpp

Code

#pragma once

template <typename Key, typename Val>
struct RadixHeap {
  using uint = typename make_unsigned<Key>::type;
  static constexpr int bit = sizeof(Key) * 8;
  array<vector<pair<uint, Val> >, bit + 1> vs;
  array<uint, bit + 1> ms;

  int s;
  uint last;

  RadixHeap() : s(0), last(0) { fill(begin(ms), end(ms), uint(-1)); }

  bool empty() const { return s == 0; }

  int size() const { return s; }

  __attribute__((target("lzcnt"))) inline uint64_t getbit(uint a) const {
    return 64 - _lzcnt_u64(a);
  }

  void push(const uint &key, const Val &val) {
    s++;
    uint64_t b = getbit(key ^ last);
    vs[b].emplace_back(key, val);
    ms[b] = min(key, ms[b]);
  }

  pair<uint, Val> pop() {
    if (ms[0] == uint(-1)) {
      int idx = 1;
      while (ms[idx] == uint(-1)) idx++;
      last = ms[idx];
      for (auto &p : vs[idx]) {
        uint64_t b = getbit(p.first ^ last);
        vs[b].emplace_back(p);
        ms[b] = min(p.first, ms[b]);
      }
      vs[idx].clear();
      ms[idx] = uint(-1);
    }
    --s;
    auto res = vs[0].back();
    vs[0].pop_back();
    if (vs[0].empty()) ms[0] = uint(-1);
    return res;
  }
};

/**
 * @brief Radix Heap
 * @docs docs/data-structure/radix-heap.md
 */

#line 2 "data-structure/radix-heap.hpp"

template <typename Key, typename Val>
struct RadixHeap {
  using uint = typename make_unsigned<Key>::type;
  static constexpr int bit = sizeof(Key) * 8;
  array<vector<pair<uint, Val> >, bit + 1> vs;
  array<uint, bit + 1> ms;

  int s;
  uint last;

  RadixHeap() : s(0), last(0) { fill(begin(ms), end(ms), uint(-1)); }

  bool empty() const { return s == 0; }

  int size() const { return s; }

  __attribute__((target("lzcnt"))) inline uint64_t getbit(uint a) const {
    return 64 - _lzcnt_u64(a);
  }

  void push(const uint &key, const Val &val) {
    s++;
    uint64_t b = getbit(key ^ last);
    vs[b].emplace_back(key, val);
    ms[b] = min(key, ms[b]);
  }

  pair<uint, Val> pop() {
    if (ms[0] == uint(-1)) {
      int idx = 1;
      while (ms[idx] == uint(-1)) idx++;
      last = ms[idx];
      for (auto &p : vs[idx]) {
        uint64_t b = getbit(p.first ^ last);
        vs[b].emplace_back(p);
        ms[b] = min(p.first, ms[b]);
      }
      vs[idx].clear();
      ms[idx] = uint(-1);
    }
    --s;
    auto res = vs[0].back();
    vs[0].pop_back();
    if (vs[0].empty()) ms[0] = uint(-1);
    return res;
  }
};

/**
 * @brief Radix Heap
 * @docs docs/data-structure/radix-heap.md
 */

Back to top page