今回は簡単な例題として「ヒープ (heap)」という基本的なデータ構造を作ってみましょう。なお、ここでいう「ヒープ」はメモリの動的割り当てで使用する「ヒープ領域」とは違います。混同しないように注意してください。
「ヒープ (heap)」は「半順序木 (partial ordered tree)」を配列で実現したデータ構造です。一般的な二分木では、親よりも左側の子のほうが小さく、親よりも右側の子が大きいという関係を満たすように作ります。半順序木の場合、親は子より小さいか等しいという関係を満たすように作ります。したがって、木の根（配列の添字 0）には、必ず最小値のデータが格納されます。下図にヒープと配列の関係を示します。
0 1 2 3 4 5 6
TABLE [10 20 30 40 50 60 70]
(root)
10 (0)
／ ＼ 親の添字を k とすると
／ ＼ その子は 2*k+1, 2*k+2 になる。
20 (1) 30 (2) 子の添字を k とすると
／ ＼ ／ ＼ その親は (k - 1) / 2 になる。
40 50 60 70 親の値 <= 子の値 の関係を満たす。
(3) (4) (5) (6)
図 : ヒープと配列の対応関係
ヒープを利用すると、最小値をすぐに見つけることができ、新しくデータを挿入する場合も、高々要素の個数 (N) の対数 (log2 N) に比例する程度の時間で済みます。
TABLE [＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊] 最初は空
[80 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊] 最初のデータをセット
[80 10 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊] 次のデータをセットし親と比較
親 子 親の位置 0 = (1 - 1)/2
[10 80 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊] 順序が違っていたら交換
[10 80 60 ＊ ＊ ＊ ＊ ＊ ＊ ＊] データをセットし比較
親 子 親の位置 0 = (2 - 1)/2
[10 80 60 20 ＊ ＊ ＊ ＊ ＊ ＊] データをセットし比較
親 子 親の位置 1 = (3 - 1)/2
[10 20 60 80 ＊ ＊ ＊ ＊ ＊ ＊] 交換する
・・・・データがなくなるまで繰り返す・・・・
図 : ヒープの構築 (1)
ヒープは、次の手順で作ることができます。まず、データを最後尾に追加します。そして、このデータがヒープの条件を満たしているかチェックします。もしも、条件を満たしていなければ、親と子を入れ換えて、次の親をチェックします。これを木のルート方向 (添字 0 の方向) に向かって繰り返します。条件を満たすか、木のルート (添字 0) まで到達すれば、処理を終了します。これをデータの個数だけ繰り返します。
このアルゴリズムをそのままプログラムすると、次のようになります。
リスト : ヒープの構築
template<class T>
void upheap(vector<T>& buff, int n)
{
while (true) {
int p = (n - 1) / 2;
if (p < 0 || buff[p] <= buff[n]) break;
swap(buff[n], buff[p]);
n = p;
}
}
テンプレート関数 upheap はヒープを満たすように n 番目の要素をルート方向に向かって移動させます。0 から n - 1 番目までの要素はヒープの条件を満たしているとします。n の親を p とすると、p は (n - 1) / 2 で求めることができます。
そして、p が 0 より小さい、または buff[p] <= buff[n] であればヒープの条件を満たすので、break で処理を終了します。そうでなければ、swap で buff[p] と buff[n] を交換して、次の親子関係をチェックします。
swap は STL に定義されている関数で、変数の値を交換します。最近の規格 (C++11) では、swap は次のように定義されています。
リスト : swap の定義例
template<class T>
void swap(T& a, T& b)
{
T temp = std::move(a);
a = std::move(b);
b = std::move(a);
}
ムーブセマンティクスを使っているので、vector などコンテナクラスを交換するときでも効率的に行うことができます。簡単な使用例を示しましょう。
リスト : swap の使用例 (sample3401.cpp)
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int x = 10;
int y = 20;
swap(x, y);
cout << x << ", " << y << endl;
vector<int> a = {1, 2, 3, 4, 5};
swap(a[0], a[4]);
for (auto x : a) cout << x << " ";
cout << endl;
vector<int> b = {6, 7, 8, 9, 10};
swap(a, b);
for (auto x : a) cout << x << " ";
cout << endl;
for (auto x : b) cout << x << " ";
cout << endl;
}
$ clang++ sample3401.cpp $ ./a.out 20, 10 5 2 3 4 1 6 7 8 9 10 5 2 3 4 1
あとは、配列の最後尾にデータを追加して、upheap を呼び出せばいいわけです。また、データが格納されている配列でも、upheap を適用してヒープを構築することができます。
for (int i = 1; i < buff.size(); i++) upheap(buff, i)
ただし、この方法はデータ数を n とすると upheap を n - 1 回呼び出すため、それほど速い方法ではありません。もう少し高速な方法はあとで説明することにしましょう。
次に、最小値を取り出したあとで新しいデータを追加し、ヒープを再構築する手順を説明します。
TABLE [10 20 30 40 50 60 70 80 90 100] ヒープを満たしている
[＊ 20 30 40 50 60 70 80 90 100] 最小値を取り出す
[66 20 30 40 50 60 70 80 90 100] 新しい値をセット
[66 20 30 40 50 60 70 80 90 100] 小さい子と比較する
^ ^ (2*0+1) < (2*0+2)
親 子 子
[20 66 30 40 50 60 70 80 90 100] 交換して次の子と比較
^ ^ (2*1+1) < (2*1+2)
親 子 子
[20 40 30 66 50 60 70 80 90 100] 交換して次の子と比較
^ ^ (2*3+1) < (2*3+2)
親 子 子 親が小さいから終了
図 : ヒープの再構築
最初に、ヒープの最小値である添字 0 の位置にあるデータを取り出します。次に、その位置に新しいデータをセットし、ヒープの条件を満たしているかチェックします。ヒープの構築とは逆に、葉の方向 (添字の大きい方向) に向かってチェックしていきます。
まず、2 つの子の中で小さい方の子を選び、それと挿入したデータを比較します。もしも、ヒープの条件を満たしていなければ、親と子を交換し、その次の子供と比較します。これを、条件を満たすか、子供がなくなるまで繰り返します。このアルゴリズムをそのままプログラムすると次のようになります。
リスト : ヒープの再構築
template<class T>
void downheap(vector<T>& buff, int n)
{
while (true) {
int c = 2 * n + 1;
if (c >= buff.size()) break;
if (c + 1 < buff.size() && buff[c] > buff[c + 1]) c++;
if (buff[n] <= buff[c]) break;
swap(buff[n], buff[c]);
n = c;
}
}
関数 downheap はヒープを満たすように n 番目の要素を葉の方向へ移動させます。n + 1 番目から最後までの要素はヒープを満たしているとします。次に、n の子 c を求めます。これが buff.size() よりも大きければ処理を終了します。そして、もう一つの子 (c + 1) がある場合は、小さい子を選択します。そして、buff[n] <= buff[c] が真であれば、ヒープの条件を満たしているので、break で処理を終了します。そうでなければ、n 番目と c 番目の要素を swap で交換して処理を繰り返します。
最小値を取り出したあと新しいデータを挿入しない場合は、新しいデータの代わりに配列 buff の最後尾のデータを buff[0] にセットしてヒープを再構築します。上図の例でいえば、100 を buff[0] にセットして、ヒープを再構築すればいいわけです。この場合、ヒープに格納されているデータの個数は一つ減ることになります。
ところで、n 個のデータをヒープに構築する場合、n - 1 回 upheap を呼び出さなければいけません。ところが、すべてのデータを配列に格納したあと、ヒープを構築するうまい方法があります。次の図を見てください。
TABLE [100 90 80 70 60|50 40 30 20 10] 後ろ半分が葉に相当
[100 90 80 70|60 50 40 30 20 10] 60 を挿入する
^
[100 90 80 70|60 50 40 30 20 10] 子供と比較する
^ ^ (2*4+1), (2*4+2)
親 子
[100 90 80 70|10 50 40 30 20 60] 交換する
・・・ 70 80 90 を順番に挿入し修正する ・・・
[100|10 40 20 60 50 80 30 70 90] 90 を挿入し修正した
[100 10 40 20 60 50 80 30 70 90] 100 を挿入、比較
^ ^ ^ (2*0+1), (2*0+2)
親 子 子
[10 100 40 20 60 50 80 30 70 90] 小さい子と交換し比較
^ ^ ^ (2*1+1), (2*1+2)
親 子 子
[10 20 40 100 60 50 80 30 70 90] 小さい子と交換し比較
^ ^ ^ (2*3+1), (2*3+2)
親 子 子
[10 20 40 30 60 50 80 100 70 90] 交換して終了
図 : ヒープの構築 (2)
配列を前半と後半の 2 つに分けると、後半部分はこれより下にはデータが繋がっていない葉の部分になります。つまり、後半部分の要素は互いに関係がなく、前半部分の枝にあたる要素と関係しているだけでなのです。したがって、後半部分だけを見れば、それはヒープを満たしていると考えることができます。
あとは、前半部分の要素に対して、葉の方向に向かってヒープの関係を満たすよう修正していけば、配列全体がヒープを満たすことになります。この処理は関数 downheap を使うと次のように簡単にプログラムできます。
for (int i = buff.size() / 2 - 1; i >= 0; i--)
downheap(buff, x, N)
後ろからヒープを再構築していくと考えるとわかりやすいでしょう。この方法の場合、要素 n の配列に対して、n / 2 個の要素の修正を行えばよいので、最初に説明したヒープの構築方法よりも速くなります。
それでは、ヒープを使って「優先度つき待ち行列 (priority queue)」を作ってみましょう。一般に、キューは先入れ先出し (FIFO : first-in, first-out) のデータ構造です。キューからデータを取り出すときは、先に挿入されたデータから取り出されます。これに対し、優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出していきます。
優先度つき待ち行列は、優先度を基準にヒープを構築することで実現できます。名前を Heap としましょう。なお、標準ライブラリ (STL) の <queue> には priority_queue が用意されています。私たちが「優先度つき待ち行列」を作る必要はまったくありませんが、Ｃ++とアルゴリズムのお勉強ということで、実際にプログラムを作ってみましょう。
Heap のメンバ関数を下表に示します。
| メンバ関数 | 機能 |
|---|---|
| Heap(); | ヒープの生成 (コンストラクタ) |
| const T& top() const; | ヒープの先頭データを返す。データはヒープから削除されない。 |
| void push(const T&); | ヒープにデータを追加する。 |
| void push(T&&); | ヒープにデータを追加する。 |
| void pop(); | ヒープの先頭データを削除する。 |
| bool empty(); | ヒープが空の場合は true を、そうでなければ false を返す。 |
| int size(); | ヒープに格納されたデータ数を返す。 |
今回は簡単な例題なので、コンストラクタはデフォルトだけとします。メンバ関数名は enqueue, dequeue としてもよかったのですが、このプログラムでは push, pop としました。また、データを追加する関数を insert とし、最小値を取り出す関数を delete_min としている文献もあります。
プログラムは次のようになります。
リスト : クラス Heap の定義
template<class T> class Heap {
vector<T> buff;
public:
bool empty() const { return buff.size() == 0; }
bool size() const { return buff.size(); }
const T& top() const { return buff.front(); }
void push(const T& x) {
buff.push_back(x);
upheap(buff, buff.size() - 1);
}
void push(T&& x) {
buff.push_back(forward<T>(x));
upheap(buff, buff.size() - 1);
}
void pop() {
swap(buff.front(), buff.back());
buff.pop_back();
downheap(buff, 0);
}
};
メンバ変数 buff にヒープ本体 (vector) を用意します。コンストラクタ、デストラクタ、代入演算子、ムーブコンストラクタ、ムーブ代入演算子はすべてデフォルトのもので大丈夫です。empty と size は buff のメンバ関数を呼び出すだけです。
top は buff.front() の値を返します。値を書き換えるとヒープの構成が崩れるので、返り値の型は const T& とし、top を const 関数に設定します。push は引数を push_back で buff の末尾に追加して、upheap でヒープを再構築します。pop は swap で先頭要素と末尾要素を交換してから、pop_back で末尾要素を取り除きます。そのあと、downheap で先頭要素をヒープに追加します。
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
リスト : 簡単なテスト
int main()
{
Heap<int> a;
vector<int> b = {5,6,4,7,3,8,2,9,1};
for (int x : b) a.push(x);
while (!a.empty()) {
cout << a.top() << " ";
a.pop();
}
cout << endl;
Heap<string> c;
c.push("foo");
c.push("bar");
c.push("baz");
c.push("oops");
while (!c.empty()) {
cout << c.top() << " ";
c.pop();
}
cout << endl;
Heap<array<int, 4>> d;
d.push(array<int, 4>{4,3,2,1});
d.push(array<int, 4>{3,2,1,4});
d.push(array<int, 4>{2,1,4,3});
d.push(array<int, 4>{1,2,3,4});
while (!d.empty()) {
for (auto x : d.top())
cout << x << " ";
cout << endl;
d.pop();
}
}
実行結果は次のようになります。
$ clang++ heap.cpp $ ./a.out 1 2 3 4 5 6 7 8 9 bar baz foo oops 1 2 3 4 2 1 4 3 3 2 1 4 4 3 2 1
小さいデータから順番に取り出されていくことがわかります。
ヒープの応用例として「ヒープソート」を紹介しましょう。ヒープソートは優秀なソートアルゴリズムの一つです。実行時間は N * log2 N に比例しますが、平均するとクイックソートよりも遅くなります。しかし、クイックソートとは違って、データの種類によって性能が劣化することはありません。
プログラムは次のようになります。
リスト : ヒープソート
template<class T>
void heap_sort(vector<T>& buff)
{
for (int i = buff.size() / 2 - 1; i >= 0; i--) {
int c, n = i;
T x = buff[n];
while ((c = 2 * n + 1) < buff.size()) {
if (c + 1 < buff.size() && buff[c] < buff[c + 1]) c++;
if (x >= buff[c]) break;
buff[n] = buff[c];
n = c;
}
buff[n] = x;
}
for (int i = buff.size() - 1; i >= 0; i--) {
int c, n = 0;
T x = buff[i];
buff[i] = buff[0];
while ((c = 2 * n + 1) < i) {
if (c + 1 < i && buff[c] < buff[c + 1]) c++;
if (x >= buff[c]) break;
buff[n] = buff[c];
n = c;
}
buff[n] = x;
}
}
前半部分でヒープを構築します。親子関係がヒープの説明と逆になっていることに注意してください。つまり、親が子より大きいという関係を満たすようにヒープを構築します。したがって、配列の先頭 (buff[0]) が最大値になります。
後半部分で、最大値を取り出してヒープを再構築します。配列の先頭には最大値がセットされているので、これを配列の最後尾のデータと交換します。あとは、そのデータを除いた範囲でヒープを再構築すれば、その次に大きいデータを求めることができます。これを繰り返すことで、大きいデータが配列の後ろから整列していくことになります。
最初の for ループで、配列の前半部分のデータを後ろから順番に取り出します。次の while ループで、親子関係を満たすように修正します。変数 n が親の位置を、変数 c が子の位置を示します。次に、後半の for ループで、最大値 buff[0] と最後尾のデータ buff[i] を交換します。そして、while ループでヒープの再構築を行います。あとはヒープのプログラムとほとんど同じですが、ヒープを再構築する範囲が変数 i で管理されていて、その値は一つずつ減っていくことに注意してください。
それでは実際に試してみましょう。
リスト : 簡単なテスト
int main()
{
vector<int> a = {5,6,7,4,3,8,2,9,1,0};
heap_sort(a);
for (auto x : a) cout << x << " ";
cout << endl;
vector<string> b = {"foo", "bar", "baz", "oops"};
heap_sort(b);
for (auto x : b) cout << x << " ";
cout << endl;
}
$ clang++ heapsort.cpp $ ./a.out 0 1 2 3 4 5 6 7 8 9 bar baz foo oops
正常に動作しているようです。興味のある方はクイックソートと実行速度を比較してみてください。
最後に STL に用意されている priority_queue の使い方を簡単に説明します。priority_queue を使うときはヘッダファイル queue をインクルードしてください。priority_queue には複数のコンストラクタが用意されていて、他のコンテナクラスのイテレータを使って priority_queue を構築することができます。また、vector の emplace_back と同様のメンバ関数 emplace も用意されています。
あとのメンバ関数は今回作成したクラス Heap のメンバ関数とほぼ同じですが、デフォルトの設定では比較関数に less<T> が設定されているため、大きな値から取り出されることに注意してください。小さな値から取り出したい場合は、テンプレート仮引数に greater<T> を指定してください。
簡単な使用例を示します。
リスト : priority_queue の使用例 (sample3402.cpp)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
vector<int> a = {5,6,4,7,3,8,2,9,1,0};
priority_queue<int> b(a.begin(), a.end());
while (!b.empty()) {
cout << b.top() << " ";
b.pop();
}
cout << endl;
priority_queue<string> c;
c.emplace("foo");
c.emplace("bar");
c.emplace("baz");
c.emplace("oops");
while (!c.empty()) {
cout << c.top() << " ";
c.pop();
}
cout << endl;
priority_queue<int, vector<int>, greater<int>> d(a.begin(), a.end());
while (!d.empty()) {
cout << d.top() << " ";
d.pop();
}
cout << endl;
priority_queue<string, vector<string>, greater<string>> e;
e.emplace("foo");
e.emplace("bar");
e.emplace("baz");
e.emplace("oops");
while (!e.empty()) {
cout << e.top() << " ";
e.pop();
}
cout << endl;
}
$ clang++ sample3402.cpp $ ./a.out 9 8 7 6 5 4 3 2 1 0 oops foo baz bar 0 1 2 3 4 5 6 7 8 9 bar baz foo oops
priority_queue は queue と同じくアダプタなので、第 2 引数に使用するコンテナクラス (デフォルトは vector) を指定して、第 3 引数に比較関数を指定してください。
リスト : ヒープ (heap.cpp)
#include <iostream>
#include <vector>
#include <array>
using namespace std;
template<class T>
void upheap(vector<T>& buff, int n)
{
while (true) {
int p = (n - 1) / 2;
if (p < 0 || buff[p] <= buff[n]) break;
swap(buff[n], buff[p]);
n = p;
}
}
template<class T>
void downheap(vector<T>& buff, int n)
{
while (true) {
int c = 2 * n + 1;
if (c >= buff.size()) break;
if (c + 1 < buff.size() && buff[c] > buff[c + 1]) c++;
if (buff[n] <= buff[c]) break;
swap(buff[n], buff[c]);
n = c;
}
}
template<class T> class Heap {
vector<T> buff;
public:
bool empty() const { return buff.size() == 0; }
bool size() const { return buff.size(); }
const T& top() const { return buff.front(); }
void push(const T& x) {
buff.push_back(x);
upheap(buff, buff.size() - 1);
}
void push(T&& x) {
buff.push_back(forward<T>(x));
upheap(buff, buff.size() - 1);
}
void pop() {
swap(buff.front(), buff.back());
buff.pop_back();
downheap(buff, 0);
}
};
int main()
{
Heap<int> a;
vector<int> b = {5,6,4,7,3,8,2,9,1};
for (int x : b) a.push(x);
while (!a.empty()) {
cout << a.top() << " ";
a.pop();
}
cout << endl;
Heap<string> c;
c.push("foo");
c.push("bar");
c.push("baz");
c.push("oops");
while (!c.empty()) {
cout << c.top() << " ";
c.pop();
}
cout << endl;
Heap<array<int, 4>> d;
d.push(array<int, 4>{4,3,2,1});
d.push(array<int, 4>{3,2,1,4});
d.push(array<int, 4>{2,1,4,3});
d.push(array<int, 4>{1,2,3,4});
while (!d.empty()) {
for (auto x : d.top())
cout << x << " ";
cout << endl;
d.pop();
}
}
リスト : ヒープソート (heapsort.cpp)
#include <iostream>
#include <vector>
using namespace std;
template<class T>
void heap_sort(vector<T>& buff)
{
for (int i = buff.size() / 2 - 1; i >= 0; i--) {
int c, n = i;
T x = buff[n];
while ((c = 2 * n + 1) < buff.size()) {
if (c + 1 < buff.size() && buff[c] < buff[c + 1]) c++;
if (x >= buff[c]) break;
buff[n] = buff[c];
n = c;
}
buff[n] = x;
}
for (int i = buff.size() - 1; i >= 0; i--) {
int c, n = 0;
T x = buff[i];
buff[i] = buff[0];
while ((c = 2 * n + 1) < i) {
if (c + 1 < i && buff[c] < buff[c + 1]) c++;
if (x >= buff[c]) break;
buff[n] = buff[c];
n = c;
}
buff[n] = x;
}
}
int main()
{
vector<int> a = {5,6,7,4,3,8,2,9,1,0};
heap_sort(a);
for (auto x : a) cout << x << " ";
cout << endl;
vector<string> b = {"foo", "bar", "baz", "oops"};
heap_sort(b);
for (auto x : b) cout << x << " ";
cout << endl;
}