はじめての C

lang

C programming note*1

ヒープは 二分木の 一種で、上の方ほど 値が より大きく (または 小さく) なるように 積み重ねた 二分木だ。 整列二分木とも よばれる。

2つの 子の 間の 大小関係には 順序は なく、親が その子より 大きいという 関係だけが 成り立つ (上の方ほど 小さくなる場合は その逆に なる)。

データの 追加や 削除に 関しては、この大小関係を くずさないよう 行なうわけだ。

最初に ヒープを つくるときには、1つの 要素ごとに 追加の処理を 行なえばよい。

ヒープという データ構造は、「要素の 追加や 削除は 任意の タイミングで 起きるが、参照したいのは いつも 一番 大きな (または 小さな) 値だけ」 という 用途に 向いている。

ヒープの 実現方法としては、以下のように 配列に 入れる 方法が 最も 一般的だ。

子の数は 最大 2つで、上から、また 左から ぎっしり 詰める。 a[1] は ルート (root: 木の根っこ ほどの 意味) を 入れる。 a[2], a[3] に lebel 1 の 要素を ... のように 順に 格納していく。 このようにすれば、
a[i] の子は a[i * 2] と a[i * 2 + 1] である。
という 関係が (すべての 要素について) 成り立つ。

C の 配列の 添字は 1 からではなく 0 からだが、この場合は あえて 0 を 使わないで 1 から 使うのが コツだ。 その方が 添字の 計算式が すっきりする (からだ)。(p210-211)

heap の 説明は これで すべてです。
サンプルコードを 見ていくと、いろいろ 気がつく 点が あります。
・ 他の 二分木と 異なって 配列が 使われている。
・ そのため malloc を 使った メモリ確保の 必要が ない。
・ データの 追加は tree の 末尾から 行ない、逆に データを 取り出す (参照する) ときは root からである。
・ 他の 二分木と 同じく 再帰が 効果的に 使われている。
・ 多次元配列が 内部的に 用いられている ← これは 後まわしに して ... と。
まず 元になる 関数 heap() から、
heap() の 仮引数 i は 入力データの 配列の 添字、n は それと 比較する 配列の 添字です。

/* heap.c */

static void heap(int i, int n)

{

    int child;
    if (i <= n / 2) {

        if (2 * i + 1 > n)

            child = 2 * i;

        else {

            if (i_comp(2 * i, 2 * i + 1) > 0)

                child = 2 * i;

            else

                child = 2 * i + 1;

        }

        if (i_comp(i, child) < 0) {

            i_swap(i, child);

            heap(child, n);

        }

    }

}

/* sub.c*/

#include <string.h>
#define MAX_S 8

#define MAX_ITEMS 1024
static char array[MAX_ITEMS][MAX_S];
int i_comp(int a, int b)

{

    return (strcmp(array[a], array[b]));

}
void i_swap(int a, int b)

{

    char tmp_str[MAX_S];
    strcpy(tmp_str, array[a]);

    strcpy(array[a], array[b]);

    strcpy(array[b], tmp_str);

}
sub.c で はじめに 外部宣言してある 多次元配列 array には static が ついています。 これは sub.c という コード内でしか 使われない 変数だからです。
同じく、heap.c で 関数 heap() に static が ついているのも、heap.c 以外の プログラムからは 参照できないように するためです。
i_comp() では 関数 strcmp() を 使って、配列の中身 (要素) を 比べています。 array[a] が array[b] より 大きければ 正の値を、小さいときは 負の値を 返します。
i_swap() では 添字は そのままで、その配列の中身 (要素) を strcpy() と 変数 tmp_str を 使って 交換します。
まず 関数 heap() は、i 番目の 配列は 必ず n 番目の 配列の 親である、という 仮定で 始まっています。
if (i <= n / 2)
実際は、i の 要素は ずっと 上の line に ある 可能性が 多いのですが、まず n の 親であるとして、それが 2つの子の どちらに あるかを 決めていきます。
そして、親に 子が ないか、あるいは 子が あっても その子の中身 (要素) が 左側の 要素より 小さいときは その子に 代わって 1つめの 要素に なり、それ以外なら 2つめの 子に なります。
さらに、 i と child の 要素を 比較して、もし child より データが 小さいときには、それぞれの中身 (要素) を 交換して、もう一度 再帰的に heap() を 実行させていきます。 これを くり返すわけです。 結果的に、(入力した) データの中身 = 要素 ではなく、配列の 添字を 変えていくことで tree に 組み込んでいってるのです。
以上の 説明は 単純化した イメージに すぎないので、当然 正確とは いえませんね。

*1:「作ってわかる Cプログラミング」