Radix Heap

components/RadixHeap.hpp · GitHub で見る

共通ページ

#include "lib/components/RadixHeap.hpp"

RadixHeap<std::uint64_t, int> heap;
heap.push({10, 3});
auto [key, value] = heap.pop_value();

操作	内容・返り値	計算量
RadixHeap(minimum = 0)	初期下限を指定して空ヒープを構築	\(O(w)\)
push({key,value})	key >= last() を満たす要素を追加	償却 \(O(1)\)
top()	最小要素の const 参照。非空であること。下限も更新	償却 \(O(w)\)
pop() / pop_value()	最小要素を削除／取得して削除。非空であること	償却 \(O(w)\)
last()	現在のキーの下限	\(O(1)\)
size() / empty()	要素数／空判定	\(O(1)\)
clear(minimum = 0)	空に戻し、キーの下限を設定	\(O(n+w)\)

Key は 64 bit 以下の整数型です。push({key, value}) のキーは last() 以上にします。初期下限は RadixHeap(minimum) で指定でき、既定値は 0 です。top() も下限を更新します。

top() は最小要素の参照、pop() は最小要素の削除、pop_value() は取得と削除です。size()・empty()・clear(minimum = 0) も使えます。

キーのビット数を \(w\)、要素数を \(n\) として、push は償却 \(O(1)\)、取り出しは償却 \(O(w)\)、空間は \(O(n+w)\) です。

検証コード

• test/bellman_ford.test.cpp
• test/bellman_ford_path.test.cpp
• test/difference_constraints.test.cpp
• test/difference_constraints.test.cpp
• test/dijkstra.test.cpp
• test/dijkstra_bigint_yuki.test.cpp
• test/dijkstra_path.test.cpp
• test/dijkstra_topological.test.cpp
• test/k_shortest_walk.test.cpp
• test/min_cost_b_flow.test.cpp
• test/min_cost_flow.test.cpp
• test/range_edge_graph.test.cpp
• test/steiner_tree.test.cpp

コード

#ifndef RADIX_HEAP_HPP
#define RADIX_HEAP_HPP

#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

template <class Key = std::uint64_t, class T = int>
class RadixHeap {
	static_assert(std::is_integral_v<Key> && !std::is_same_v<Key, bool> && sizeof(Key) <= 8);
	using U = std::make_unsigned_t<Key>;
	using State = std::pair<Key, T>;
	std::vector<State> bucket[std::numeric_limits<U>::digits + 1];
	Key lower;
	std::size_t count = 0;
	int index(Key key) const { return std::bit_width(U(U(key) ^ U(lower))); }
	void refill() {
		assert(count);
		if (!bucket[0].empty()) return;
		int i = 1;
		while (bucket[i].empty()) ++i;
		lower = bucket[i][0].first;
		for (const auto &s : bucket[i]) lower = std::min(lower, s.first);
		for (auto &s : bucket[i]) bucket[index(s.first)].push_back(std::move(s));
		bucket[i].clear();
	}

  public:
	explicit RadixHeap(Key minimum = 0) : lower(minimum) {}
	RadixHeap(const RadixHeap &) = default;
	RadixHeap &operator=(const RadixHeap &) = default;
	RadixHeap(RadixHeap &&other) noexcept : lower(other.lower), count(std::exchange(other.count, 0)) {
		for (int i = 0; i <= std::numeric_limits<U>::digits; ++i) bucket[i] = std::move(other.bucket[i]);
	}
	RadixHeap &operator=(RadixHeap &&other) noexcept {
		if (this != &other) {
			lower = other.lower;
			count = std::exchange(other.count, 0);
			for (int i = 0; i <= std::numeric_limits<U>::digits; ++i) bucket[i] = std::move(other.bucket[i]);
		}
		return *this;
	}

	bool empty() const { return count == 0; }
	std::size_t size() const { return count; }
	Key last() const { return lower; }
	void clear(Key minimum = 0) {
		for (auto &b : bucket) b.clear();
		lower = minimum;
		count = 0;
	}
	void push(State s) {
		assert(s.first >= lower);
		bucket[index(s.first)].push_back(std::move(s));
		++count;
	}
	const State &top() {
		refill();
		return bucket[0].back();
	}
	void pop() {
		refill();
		bucket[0].pop_back();
		--count;
	}
	State pop_value() {
		refill();
		State s = std::move(bucket[0].back());
		bucket[0].pop_back();
		--count;
		return s;
	}
};

#endif

Back to top page