今回は簡単な例題として「ヒープ (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) まで到達すれば、処理を終了します。これをデータの個数だけ繰り返します。
このアルゴリズムをそのままプログラムすると、次のようになります。
リスト : ヒープの構築
// ヒープの構築
void upheap(double *buff, int n)
{
while (true) {
int p = (n - 1) / 2;
if (p < 0 || buff[p] <= buff[n]) break;
double temp = buff[n];
buff[n] = buff[p];
buff[p] = temp;
n = p;
}
}
関数 upheap はヒープを満たすように n 番目の要素をルート方向に向かって移動させます。0 から n - 1 番目までの要素はヒープの条件を満たしているとします。n の親を p とすると、p は (n - 1) / 2 で求めることができます。そして、p が 0 より小さい、または buff[p] <= buff[n] であればヒープの条件を満たすので、break で処理を終了します。そうでなければ、buff[p] と buff[n] を交換して、次の親子関係をチェックします。
あとは、配列の最後尾にデータを追加して、upheap を呼び出せばいいわけです。また、データが格納されている配列でも、upheap を適用してヒープを構築することができます。
for (int i = 1; i < N; i++) upheap(buff, i)
N は配列の大きさを表すマクロです。ただし、この方法はデータ数を 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 つの子の中で小さい方の子を選び、それと挿入したデータを比較します。もしも、ヒープの条件を満たしていなければ、親と子を交換し、その次の子供と比較します。これを、条件を満たすか、子供がなくなるまで繰り返します。このアルゴリズムをそのままプログラムすると次のようになります。
リスト : ヒープの再構築
void downheap(double *buff, int n, int size)
{
while (true) {
int c = 2 * n + 1;
if (c >= size) break;
if (c + 1 < size && buff[c] > buff[c + 1]) c++;
if (buff[n] <= buff[c]) break;
double temp = buff[n];
buff[n] = buff[c];
buff[c] = temp;
n = c;
}
}
関数 downheap はヒープを満たすように n 番目の要素を葉の方向へ移動させます。n + 1 番目から最後までの要素はヒープを満たしているとします。引数 size は配列の大きさを表します。次に、n の子 c を求めます。これが size よりも大きければ処理を終了します。そして、もう一つの子 (c + 1) がある場合は、小さい子を選択します。そして、buff[n] <= buff[c] が真であれば、ヒープの条件を満たしているので、break で処理を終了します。そうでなければ、n 番目と c 番目の要素を交換して処理を繰り返します。
最小値を取り出したあと新しいデータを挿入しない場合は、新しいデータの代わりに配列 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 = N / 2 - 1; i >= 0; i--)
downheap(buff, x, N)
後ろからヒープを再構築していくと考えるとわかりやすいでしょう。この方法の場合、要素 n の配列に対して、n / 2 個の要素の修正を行えばよいので、最初に説明したヒープの構築方法よりも速くなります。
それでは、ヒープを使って「優先度つき待ち行列 (priority queue)」を作ってみましょう。一般に、キューは先入れ先出し (FIFO : first-in, first-out) のデータ構造です。キューからデータを取り出すときは、先に挿入されたデータから取り出されます。これに対し、優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出していきます。
優先度つき待ち行列は、優先度を基準にヒープを構築することで実現できます。名前を Heap としましょう。今回はプログラムを簡単にするため、格納する要素のデータ型を浮動小数点数 (double) とします。Heap の操作関数を下表に示します。
| 関数名 | 機能 |
|---|---|
| Heap *make_heap(int n); | 大きさ n のヒープを作る。 |
| void delete_heap(Heap *hp); | ヒープを廃棄する。 |
| double pop(Heap *hp, bool *err); | ヒープからデータを取り出す。 |
| bool enqueue(Heap *hp, double x); | ヒープにデータを追加する。 |
| double peek(Heap *hp, bool *err); | ヒープの先頭データを返す。データはヒープから削除されない。 |
| bool is_empty(Heap *hp); | ヒープが空の場合は true を、そうでなければ false を返す。 |
| bool is_full(Heap *hp); | ヒープが満杯の場合は true を、そうでなければ false を返す。 |
| int heap_length(Heap *hp); | ヒープに格納されたデータ数を返す。 |
メソッド名は enqueue, dequeue としてもよかったのですが、このプログラムでは push, pop としました。また、データを追加する関数を insert とし、最小値を取り出す関数を delete_min としている文献もあります。
プログラムは次のようになります。
リスト : ヒープの定義
typedef struct {
int size, limit;
double *buff;
} Heap;
構造体 Heap のメンバ変数 size が格納している要素数、limit が配列の大きさを表します。buff が配列の本体です。Heap を生成する関数 make_heap は次のようになります。
リスト : ヒープの生成と廃棄
Heap *make_heap(int n)
{
Heap *hp = malloc(sizeof(Heap));
if (hp != NULL) {
hp->size = 0;
hp->limit = n;
hp->buff = malloc(sizeof(double) * n);
if (hp->buff == NULL) {
free(hp);
return NULL;
}
}
return hp;
}
void delete_heap(Heap *hp)
{
free(hp->buff);
free(hp);
}
malloc で Heap の本体を確保し、メンバ変数 size を 0 に、limit を n に初期化します。それから配列本体を malloc で取得します。失敗した場合は heap を解放してから NULL を返します。最後に hp を返します。Heap を廃棄する関数 delete_heap も簡単です。配列本体を free で解放してから Heap の本体を解放します。
次はデータを挿入する関数 push を作ります。
リスト : データの挿入
// ヒープは満杯か
bool is_full(Heap *hp)
{
return hp->size == hp->limit;
}
// データの挿入
bool push(Heap *hp, double x)
{
if (is_full(hp)) return false;
hp->buff[hp->size] = x;
upheap(hp->buff, hp->size);
hp->size++;
return true;
}
関数 is_full でヒープが満杯かチェックします。is_heap はメンバ変数 size と limit が等しいかチェックするだけです。データを挿入する場合、buff[hp->size] に x をセットしてから upheap を呼び出します。最後に size をインクリメントしてから true を返します。
次は、最小値を取り出す関数 pop を作ります。
リスト : データの取り出し
// ヒープは空か
bool is_empty(Heap *hp)
{
return hp->size == 0;
}
// データの取り出し
double pop(Heap *hp, bool *err)
{
if (is_empty(hp)) {
*err = false;
return 0;
}
double x = hp->buff[0];
hp->buff[0] = hp->buff[--(hp->size)];
downheap(hp->buff, 0, hp->size);
*err = true;
return x;
}
最初に is_empty でヒープが空かチェックします。is_empty はメンバ変数 size が 0 かチェックするだけです。空の場合は *err に false をセットして 0 を返します。データがある場合、配列の先頭要素を変数 x にセットします。次に、配列の末尾のデータを先頭に移動します。あとは downheap を呼び出してヒープを再構築するだけです。最後に *err に true をセットしてから return で x を返します。
あとのプログラムは簡単なので説明を割愛いたします。詳細はプログラムリストをお読みください。
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
リスト : 簡単なテスト
#define N 10
int main(void)
{
double a[N] = {5,6,4,7,3,8,2,9,1,0};
Heap *hp = make_heap(N);
bool err;
for (int i = 0; i < N; i++) {
push(hp, a[i]);
printf("%.3f ", peek(hp, &err));
}
printf("\n");
printf("%d\n", is_empty(hp));
printf("%d\n", is_full(hp));
printf("%d\n", heap_length(hp));
while (!is_empty(hp))
printf("%.3f\n", pop(hp, &err));
printf("%d\n", is_empty(hp));
printf("%d\n", is_full(hp));
printf("%d\n", heap_length(hp));
delete_heap(hp);
return 0;
}
実行結果は次のようになります。
$ clang heap.c $ ./a.out 5.000 5.000 4.000 4.000 3.000 3.000 2.000 2.000 1.000 0.000 0 1 10 0.000 1.000 2.000 3.000 4.000 5.000 6.000 7.000 8.000 9.000 1 0 0
小さいデータから順番に取り出されていくことがわかります。
今回はここまでです。次回はヒープの応用例として「ヒープソート」と「マージソート」を取り上げる予定です。
リスト : ヒープ (heap.c)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ヒープ
typedef struct {
int size, limit;
double *buff;
} Heap;
// ヒープの生成
Heap *make_heap(int n)
{
Heap *hp = malloc(sizeof(Heap));
if (hp != NULL) {
hp->size = 0;
hp->limit = n;
hp->buff = malloc(sizeof(double) * n);
if (hp->buff == NULL) {
free(hp);
return NULL;
}
}
return hp;
}
// ヒープの廃棄
void delete_heap(Heap *hp)
{
free(hp->buff);
free(hp);
}
// ヒープの構築
void upheap(double *buff, int n)
{
while (true) {
int p = (n - 1) / 2;
if (p < 0 || buff[p] <= buff[n]) break;
double temp = buff[n];
buff[n] = buff[p];
buff[p] = temp;
n = p;
}
}
// ヒープの再構築
void downheap(double *buff, int n, int size)
{
while (true) {
int c = 2 * n + 1;
if (c >= size) break;
if (c + 1 < size && buff[c] > buff[c + 1]) c++;
if (buff[n] <= buff[c]) break;
double temp = buff[n];
buff[n] = buff[c];
buff[c] = temp;
n = c;
}
}
// ヒープは満杯か
bool is_full(Heap *hp)
{
return hp->size == hp->limit;
}
// データの挿入
bool push(Heap *hp, double x)
{
if (is_full(hp)) return false;
hp->buff[hp->size] = x;
upheap(hp->buff, hp->size);
hp->size++;
return true;
}
// ヒープは空か
bool is_empty(Heap *hp)
{
return hp->size == 0;
}
// 要素数
int heap_length(Heap *hp)
{
return hp->size;
}
// データの取り出し
double pop(Heap *hp, bool *err)
{
if (is_empty(hp)) {
*err = false;
return 0;
}
double x = hp->buff[0];
hp->buff[0] = hp->buff[--(hp->size)];
downheap(hp->buff, 0, hp->size);
*err = true;
return x;
}
double peek(Heap *hp, bool *err)
{
if (is_empty(hp)) {
*err = false;
return 0;
}
return hp->buff[0];
}
#define N 10
int main(void)
{
double a[N] = {5,6,4,7,3,8,2,9,1,0};
Heap *hp = make_heap(N);
bool err;
for (int i = 0; i < N; i++) {
push(hp, a[i]);
printf("%.3f ", peek(hp, &err));
}
printf("\n");
printf("%d\n", is_empty(hp));
printf("%d\n", is_full(hp));
printf("%d\n", heap_length(hp));
while (!is_empty(hp))
printf("%.3f\n", pop(hp, &err));
printf("%d\n", is_empty(hp));
printf("%d\n", is_full(hp));
printf("%d\n", heap_length(hp));
delete_heap(hp);
return 0;
}