D-ary Heap

components/d_ary_heap.hpp · GitHub で見る

共通ページ

#include "lib/components/d_ary_heap.hpp"

DaryHeap<int> heap;
heap.push(3);
heap.push(1);
auto x = heap.pop_value();

操作	内容・返り値	計算量
DaryHeap() / DaryHeap(compare) / DaryHeap(a,compare = {})	空／比較関数指定／配列から構築	空: \(O(1)\)、配列: \(O(n)\)
push(x)	要素を追加	償却 \(O(\log n)\)
top()	先頭要素の const 参照。非空であること	\(O(1)\)
pop() / pop_value()	先頭を削除／取得して削除。非空であること	\(O(\log n)\)
replace_top(x)	先頭を置換し、元の値を返す。非空であること	\(O(\log n)\)
push_pop(x)	x を追加した場合の先頭を返し、残りを保持	\(O(\log n)\)
size() / empty()	要素数／空判定	\(O(1)\)
values()	内部配列の const 参照	\(O(1)\)
reserve(n) / clear()	領域予約／容量を残して空にする	reserve: \(O(n)\)、clear: 自明な型 \(O(1)\)、その他 \(O(n)\)
swap(other)	内容と比較関数を交換	\(O(1)\)

DaryHeap<T, Compare = std::less<T>, D = 2> は最大ヒープです。最小ヒープは Compare に std::greater<T> を指定します。D は 2 以上です。std::vector<T> からも構築できます。

top() は先頭の要素、pop() は削除、pop_value() は取得と削除です。replace_top(x) は先頭を x に置き換え、元の値を返します。push_pop(x) は挿入後の先頭を取り出します。

values() は内部配列の const 参照です。size()・empty()・reserve(n)・clear() も使えます。

要素数を \(n\)、\(D\) を定数として、配列からの構築・コピー・予約は \(O(n)\)、push は償却 \(O(\log n)\)、削除・置換は \(O(\log n)\)、clear は自明に破棄可能な型なら \(O(1)\)、それ以外は \(O(n)\)、その他は \(O(1)\) です。空間は \(O(n)\)、比較・要素の移動・破棄は \(O(1)\) とします。

検証コード

• test/kd_tree.test.cpp
• test/min_cost_b_flow.test.cpp
• test/min_cost_flow.test.cpp
• test/slope_trick.test.cpp

コード

#ifndef D_ARY_HEAP_HPP
#define D_ARY_HEAP_HPP

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <utility>
#include <vector>

template <class T, class Compare = std::less<T>, std::size_t D = 2>
class DaryHeap {
	static_assert(D >= 2);
	std::vector<T> data;
	[[no_unique_address]] Compare compare{};
	void up(std::size_t i, T value) {
		while (i) {
			std::size_t p = (i - 1) / D;
			if (!compare(data[p], value)) break;
			data[i] = std::move(data[p]);
			i = p;
		}
		data[i] = std::move(value);
	}
	void down(std::size_t i, T value) {
		std::size_t n = data.size();
		while (i < n / D + (n % D > 1)) {
			std::size_t best = i * D + 1, end = n;
			if constexpr (D <= std::size_t(-1) / 2) end = std::min(best + D, n);
			for (std::size_t j = best + 1; j < end; ++j)
				if (compare(data[best], data[j])) best = j;
			if (!compare(value, data[best])) break;
			data[i] = std::move(data[best]);
			i = best;
		}
		data[i] = std::move(value);
	}

  public:
	DaryHeap() = default;
	explicit DaryHeap(Compare compare) : compare(std::move(compare)) {}
	explicit DaryHeap(std::vector<T> values, Compare compare = {}) : data(std::move(values)), compare(std::move(compare)) {
		for (std::size_t i = data.size() / D + (data.size() % D > 1); i--;) down(i, std::move(data[i]));
	}
	bool empty() const { return data.empty(); }
	std::size_t size() const { return data.size(); }
	void reserve(std::size_t n) { data.reserve(n); }
	void clear() { data.clear(); }
	const std::vector<T> &values() const { return data; }
	decltype(auto) top() const {
		assert(!empty());
		return data.front();
	}
	void push(T value) {
		data.push_back(std::move(value));
		up(data.size() - 1, std::move(data.back()));
	}
	T replace_top(T value) {
		assert(!empty());
		T result = std::move(data.front());
		down(0, std::move(value));
		return result;
	}
	T push_pop(T value) {
		if (empty() || !compare(value, data.front())) return value;
		return replace_top(std::move(value));
	}
	T pop_value() {
		assert(!empty());
		T result = std::move(data.front());
		if (data.size() == 1) data.pop_back();
		else {
			T value = std::move(data.back());
			data.pop_back();
			down(0, std::move(value));
		}
		return result;
	}
	void pop() { pop_value(); }
	void swap(DaryHeap &other) noexcept(noexcept(std::swap(compare, other.compare))) {
		data.swap(other.data);
		std::swap(compare, other.compare);
	}
};

#endif

Back to top page