「みんなのデータ構造」で学ぶデータ構造 〜 BinaryHeap

「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ

「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。

この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。

1. ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
2. 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。

また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。

• 配列: ArrayStack・ArrayQueue・ArrayDeque
• 連結リスト: SLList(Singly-Linked List)・DLList(Doubly-Linked List)
• チェイン法を使ったハッシュテーブル: ChainedHashTable
• 二分木・二分探索木: BinaryTree・BinarySearchTree
• 赤黒木: RedBlackTree
• 二分ヒープ: BinaryHeap 👈 この記事
• ソート: MergeSort・QuickSort
• グラフの探索: 幅優先探索・深さ優先探索

書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。

弁護士ドットコムでは、エンジニア有志で本書の輪読会をしています。この本の内容をマスターして、競技プログラミングに挑戦するぞ！

ヒープ

BinaryHeapは、優先度付きキューの実装方法の1つである。ヒープは特殊な二分木であり、「雑多に積まれたもの」という意味がある。高度に構造化された二分探索木とは対象である。

BinaryHeapは完全二分木をシミュレートするのに配列を使う。このヒープを使って整列アルゴリズムであるヒープソートを実装できる。ヒープソートは、ソートアルゴリズムの中でも最速なもののひとつである。

BinaryHeap: 二分木を間接的に表現する

BinaryHeapは、優先度付きキューのインターフェースを実装する。BinaryHeapはadd(x)とremove()をサポートする。resize()のコストを無視すると、いずれの操作の実行時間も $O(\log n)$ である。

根は配列の添字0、左の子は添字1、右の子は添字2という具合に、木のノードを幅優先順に配列に入れていくことで、完全二分木を表現できる。

そして、木と配列の関係には法則性があり、添字iに対して以下のような関係が成り立つ。

int left(int i) {
	return 2*i + 1;
}
int right(int i) {
	return  2*i + 2;
}
int parent(int i) {
	return  (i-1)/2;
}

対象のノードの添字がわかれば、上記の計算方法で左の子、右の子、親のindexを求めることができる。

BinaryHeapではn個の要素を配列aに格納する。

array<T> a;
int n;

add(x) - $O(\log n)$ 以下

add(x)の実装は簡単。他の配列ベースのデータ構造と同じく、a.length = nかを確認して、そうであればresize()（拡張）する。そして、xをa[n]に入れ、nを1増やす。あとは、xとその親を交換する操作をxが親以上になるまで再帰的に実行することで、ヒープ性を保てば良い。

bool add(T x) {
	if (n + 1 > a.length) resize();
	a[n] = x;
	n++;
	bubbleUp(n-1);
	return true;
}
void bubbleUp(int i) {
	int p = parent(i);
	while (i > 0 && compare(a[i], a[p]) < 0) {
		a.swap(i, p);
		i = p;
		p = parent(i);
	}
}

remove() - $O(\log n)$ 以下

remove()はヒープから最小の値を削除する。最小値は根の値である。

最小値を削除する簡単な方法は、根とa[n-1]を交換し、交換後にa[n-1]にある値（根の値）を削除して、nを1小さくする。次に、ヒープ性を保持するためには、a[0]にある値が隣接するノードの中で最小の値であることが必要である。このため、左右の子と値を比べて、もしa[0]の値が大きいのであればこれをした方向に動かしていく必要がある。

そして、新しくねとなった要素を2つのこと比較し、新しくねとなった要素の値が3つのうちで最小ならば処理を終了する。そうでないなら、2つの子のうち小さいものと入れ替え、同様の処理を繰り返す。

T remove() {
	T x = a[0];
	n--;
	a[0] = a[n];
	trickleDown(0);
	if (3*n < a.length) resize();
	return x;
}
void trickleDown(int i) {
	while (i >= 0) {
		int j = -1; // この関数内でiとjの場所を交換する
		int r = right(i);
		if (r < n && compare(a[r], a[i]) < 0) { // 右の子よりa[i]が大きい場合
			int l = left(i);
			if (compare(a[l], a[r]) < 0) { // 左の子と右の子を比べる
				j = l; // 左の子の方が小さいとき
			} else {
				j = r; // 右の子の方が小さいとき
			}
		} else {
			int l = left(i);
			if (l < n && compare(a[l], a[i]) < 0) {
				j = l;
			}
		}
		if (j >= 0) a.swap(i, j);
		i = j;
	}
}

add(x)、remove()の実行時間が $O(\log n)$ であるのには以下のような理由である。BinaryHeapは完全二分木であるので、木の高さをhとすると、少なくとも2^h個のノードがあるので、n >= 2^hが成り立つ。この両辺の対数を取ると、次の式が成り立つ。