永続併合可能ヒープ

data_structure/persistent_heap.hpp · GitHub で見る

共通ページ

過去版を残して要素の追加・最小値の削除・ヒープ同士の併合を行います。既定は最小ヒープです。最大ヒープには PersistentHeap<T, std::greater<T>> を使います。

#include "lib/data_structure/persistent_heap.hpp"
#include <cassert>

int main() {
	PersistentHeap<int> heap;
	auto a = heap.push(heap.initial_root(), 5);
	auto b = heap.push(a, 2);
	auto c = heap.push(a, 8);
	auto d = heap.meld(b, c);
	assert(heap.size(d) == 4 && heap.top(d) == 2);
	assert(heap.top(heap.pop(d)) == 5);
	assert(heap.top(a) == 5 && heap.top(b) == 2);
}

各更新は新しい root_type を返し、引数の版は変わりません。initial_root() が最初の版です。ルートをコピーするだけなら時間・追加領域ともに \(O(1)\) で、任意の過去版から分岐できます。同じオブジェクトから得たルートだけを渡してください。版ごとのノード解放は行いません。オブジェクト自体のコピーは全ノードの複製になります。

操作	内容	計算量
PersistentHeap<T,Compare>(compare = Compare{})	空ヒープ。既定は std::less<T>	\(O(1)\)
size(root) / empty(root)	要素数／空か	\(O(1)\)
top(root)	比較器で最初の値。非空が必要	\(O(1)\)
push(root,x)	x を追加した版	\(O(\log n)\)
pop(root)	先頭の値を 1 個削除した版。非空が必要	\(O(\log n)\)
meld(a,b)	2 つのヒープの全要素を含む版	\(O(\log(n+m))\)

同じオブジェクトの版同士だけを併合してください。重複や共有部分もそれぞれ 1 回ずつ数えるため、同じ版を自分自身と併合すると個数は 2 倍になります。個数は std::int64_t で、併合後も INT64_MAX 以下にしてください。Compare は狭義弱順序、T はコピー可能な型とします。T のデフォルト構築は不要です。

reserve(count) は全版を合わせたノード数を予約します。node_count() は作成済みノード数、memory_usage() は予約済みノード領域のバイト数を返します。ルートは再確保後も有効です。値のコピー・演算は定数時間とします。更新の時間には領域確保の償却計算量を含みます。

push・pop は \(O(\log n)\)、meld は \(O(\log(n+m))\) 時間で、同じオーダーの追加領域を使います。top・size は \(O(1)\) です。空ヒープ・要素 1 個の操作は定数時間です。読み取りはノードを作りません。

検証コード

• test/persistent_heap.test.cpp

コード

#ifndef PERSISTENT_HEAP_HPP
#define PERSISTENT_HEAP_HPP

#include <algorithm>
#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

template <class T, class Compare = std::less<T>>
class PersistentHeap {
  public:
	using value_type = T;
	using root_type = std::uint32_t;
  private:
	using Stored = std::conditional_t<std::is_trivially_default_constructible_v<T> && std::is_trivially_copyable_v<T>, T, std::optional<T>>;
	struct Node { Stored value; root_type left, right; int rank; std::int64_t size; };
	std::vector<Node> nodes{{{}, 0, 0, 0, 0}};
	Compare comp;
	void check([[maybe_unused]] root_type root) const { assert(root < nodes.size()); }
	const T &value_at(root_type root) const {
		if constexpr (std::is_same_v<Stored, T>) return nodes[root].value;
		else return *nodes[root].value;
	}
	root_type make(Node node) {
		assert(nodes.size() < std::numeric_limits<root_type>::max());
		auto result = static_cast<root_type>(nodes.size());
		nodes.push_back(std::move(node));
		return result;
	}
	root_type rebuild(root_type root, root_type right) {
		assert(nodes.size() < std::numeric_limits<root_type>::max());
		auto result = static_cast<root_type>(nodes.size());
		nodes.push_back(nodes[root]);
		auto& node = nodes.back();
		node.right = right;
		if ((nodes[node.left].rank) < nodes[node.right].rank) std::swap(node.left, node.right);
		node.rank = nodes[node.right].rank + 1;
		node.size = 1 + nodes[node.left].size + nodes[node.right].size;
		return result;
	}
  public:
	explicit PersistentHeap(Compare compare = Compare{}) : comp(std::move(compare)) {}
	root_type initial_root() const { return 0; }
	std::int64_t size(root_type root) const { check(root); return nodes[root].size; }
	bool empty(root_type root) const { return size(root) == 0; }
	T top(root_type root) const { check(root); assert(root); return value_at(root); }
	root_type meld(root_type a, root_type b) {
		check(a); check(b);
		if (!a || !b) return a ? a : b;
		assert(size(a) <= std::numeric_limits<std::int64_t>::max() - size(b));
		std::array<root_type, 128> path;
		int depth = 0;
		while (a && b) {
			if (comp(value_at(b), value_at(a))) std::swap(a, b);
			path[depth++] = a;
			a = nodes[a].right;
		}
		auto result = a ? a : b;
		while (depth) result = rebuild(path[--depth], result);
		return result;
	}
	root_type push(root_type root, T value) {
		check(root);
		assert(size(root) < std::numeric_limits<std::int64_t>::max());
		std::array<root_type, 64> path;
		int depth = 0;
		while (root && !comp(value, value_at(root))) {
			path[depth++] = root;
			root = nodes[root].right;
		}
		auto result = make({std::move(value), root, 0, 1, size(root) + 1});
		while (depth) result = rebuild(path[--depth], result);
		return result;
	}
	root_type pop(root_type root) { check(root); assert(root); return meld(nodes[root].left, nodes[root].right); }
	void reserve(std::size_t count) { assert(count < std::numeric_limits<root_type>::max()); nodes.reserve(count + 1); }
	std::size_t node_count() const { return nodes.size() - 1; }
	std::size_t memory_usage() const { return nodes.capacity() * sizeof(Node); }
};

#endif

Back to top page