第 6 章: 木 (tree)

6.0 木とは

6.1 2分探索木の配列表現

6.2 2分探索木の動的表現

6.3 2分探索木の再帰的表現

6.4 2分探索木のトラバーサル

6.5 レベルごとのトラバーサル

6.6 ヒープ

ヒープの作成 (上方移動):

上方移動によりヒープ•データを作成する

ヒープは完全 2 分木で, どの親と子をとっても, (親 < 子) になっている木をヒープという. なお, 左の子と右の子の大小関係は問わない.

ヒープは半順序集合 (partially ordered set) をツリーで表現したデータ構造.

ヒープの配列表現:

左の子: s
右の子: s+1
親:     p=s/2 (インデックスは 1 から)

新しいデータをヒープに追加するには次のように行う. このは空のヒープから始めることができる:

1. 新しいデータをヒープの最後の要素として格納する
2. その要素を子とする親のデータと比較し, 親の方が大きければ子と親と交換する
3. 次に親を子として, その上の親と同じことを繰り返す. 繰り返しの終了条件は, 子の位置が根まで上がるか, 親 <= 子 になるまで.

heap1.c

/*
  ヒープの作成 (親 < 子)
  heap1.c
  プログラムの入力終了は Ctrl+D を使うこと
*/

#include <stdio.h>

int
main(int argc, char *argv[]){

  int heap[100]; /* ヒープを定義する */
  int n; /* インデックス */
  int i; /* インクリメント変数 */
  int s; /* 子 */
  int p; /* 親 */
  int temp; /* 一時変数, 親と子のデータを交換用に */

  n = 1;

  while( scanf("%d", &heap[n]) != EOF ){ /* ヒープの最後にいれる */
    s = n;
    p = s / 2; /* 親の位置, 配列のインデックスは 1 から */
    while (s >= 2 && heap[p] > heap[s] ){ /* 親は追加された子より大きければ, 交換する */
      temp = heap[p];
      heap[p] = heap[s];
      heap[s] = temp;
    }
    n++;

  }

  for(i = 1; i < n; i++){
    printf("%d ", heap[i]);
  }
  printf("\n");
  
  return 0;
}

heap1.c の実行結果は:

6.7 ヒープ•ソート

6.8 式の木

6.9 知的データベース