Radix Heap
(data_structure/radix_heap.cpp)

• View this file on GitHub
• Last update: 2020-03-11 22:42:07+09:00
• Link: https://yosupo.hatenablog.com/entry/2015/04/03/224649

Depends on

• other/bit_width.cpp
• other/countl_zero.cpp
• other/countr_zero.cpp
• other/int_alias.cpp

Verified with

• test/radix_heap.test.cpp

Code

#include "other/bit_width.cpp"
#include "other/int_alias.cpp"

#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>

template <class T> class radix_heap {
  using V = std::pair<u64, T>;

public:
  using key_type = u64;
  using mapped_type = T;
  using value_type = V;

private:
  std::vector<std::vector<V>> u;
  u64 last;

public:
  radix_heap() : u(), last(0) {}

  void push(V x) {
    assert(last <= x.first);

    const usize i = bit_width(x.first ^ last);
    if (u.size() <= i)
      u.resize(i + 1);
    u[i].push_back(std::move(x));
  }

  V pop() {
    if (u[0].empty()) {
      usize i = 1;
      while (u[i].empty())
        i += 1;
      last = std::numeric_limits<u64>::max();
      for (const V &e : u[i])
        last = std::min(last, e.first);
      for (V &e : u[i]) {
        const usize j = bit_width(e.first ^ last);
        u[j].push_back(std::move(e));
      }
      u[i].clear();
    }
    V ret = std::move(u[0].back());
    u[0].pop_back();
    return ret;
  }
};

/**
 * @brief Radix Heap
 * @see https://yosupo.hatenablog.com/entry/2015/04/03/224649
 */

#line 2 "other/bit_width.cpp"

#line 2 "other/countl_zero.cpp"

#line 2 "other/countr_zero.cpp"

#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 4 "other/countr_zero.cpp"

#include <array>

usize countr_zero(u64 x) {
  if (x == 0)
    return 64;
#ifdef __GNUC__
  return __builtin_ctzll(x);
#else
  constexpr std::array<usize, 64> table = {
      0,  1,  2,  7,  3,  13, 8,  27, 4,  33, 14, 36, 9,  49, 28, 19,
      5,  25, 34, 17, 15, 53, 37, 55, 10, 46, 50, 39, 29, 42, 20, 57,
      63, 6,  12, 26, 32, 35, 48, 18, 24, 16, 52, 54, 45, 38, 41, 56,
      62, 11, 31, 47, 23, 51, 44, 40, 61, 30, 22, 43, 60, 21, 59, 58};
  return table[(x & ~x + 1) * 0x218A7A392DD9ABF >> 58 & 0x3F];
#endif
}
#line 5 "other/countl_zero.cpp"

usize countl_zero(u64 x) {
#ifdef __GNUC__
  return x == 0 ? 64 : __builtin_clzll(x);
#else
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x |= x >> 32;
  return 64 - countr_zero(~x);
#endif
}
#line 5 "other/bit_width.cpp"

usize bit_width(const u64 x) { return 64 - countl_zero(x); }
#line 3 "data_structure/radix_heap.cpp"

#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>

template <class T> class radix_heap {
  using V = std::pair<u64, T>;

public:
  using key_type = u64;
  using mapped_type = T;
  using value_type = V;

private:
  std::vector<std::vector<V>> u;
  u64 last;

public:
  radix_heap() : u(), last(0) {}

  void push(V x) {
    assert(last <= x.first);

    const usize i = bit_width(x.first ^ last);
    if (u.size() <= i)
      u.resize(i + 1);
    u[i].push_back(std::move(x));
  }

  V pop() {
    if (u[0].empty()) {
      usize i = 1;
      while (u[i].empty())
        i += 1;
      last = std::numeric_limits<u64>::max();
      for (const V &e : u[i])
        last = std::min(last, e.first);
      for (V &e : u[i]) {
        const usize j = bit_width(e.first ^ last);
        u[j].push_back(std::move(e));
      }
      u[i].clear();
    }
    V ret = std::move(u[0].back());
    u[0].pop_back();
    return ret;
  }
};

/**
 * @brief Radix Heap
 * @see https://yosupo.hatenablog.com/entry/2015/04/03/224649
 */

Back to top page