seekworser's Library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by seekworser Hosted on GitHub Pages — Theme by mattgraham

Radix Heap
(competitive/data_structure/radix_heap.hpp)

• View this file on GitHub
• Last update: 2023-03-29 18:12:07+09:00
• Include: #include "competitive/data_structure/radix_heap.hpp"

Required by

• fast_dijkstra.hpp (competitive/graph/fast_dijkstra.hpp)

Verified with

• online_test/library-checker/shortest_path_fast_dijkstra.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; }

  inline uint64_t getbit(uint a) const {
    return 64 - __builtin_clzll(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 "competitive/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; }

  inline uint64_t getbit(uint a) const {
    return 64 - __builtin_clzll(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