図4.15のヒープに、insert(9)を実行する。
<問題>
<実行例> 毎回の交換結果のヒープの内容をプリントしている。（この実行例でなくてもよい。交換の様子がわかるものは、もっとよい）
1 2 3 4 5 6 7 8 9 10 11 12 （mainループからの呼び出し。insert前)
4 7 16 32 25 95 18 81 59 38 42 0
4
7 16
32 25 95 18
81 59 38 42 0
----------------------------------- この部分は、どこでプリントするかによります。
1 2 3 4 5 6 7 8 9 10 11 12 (up_heapによる交換。6の95が12へ)
4 7 16 32 25 95 18 81 59 38 42 95
1 2 3 4 5 6 7 8 9 10 11 12 (up_heapによる交換 3の16が6へ)
4 7 16 32 25 16 18 81 59 38 42 95
------------------------------------ 同じにならなくてもよいです。下は同じはず (7.3)
1 2 3 4 5 6 7 8 9 10 11 12
4 7 9 32 25 16 18 81 59 38 42 95 (mainループからの呼び出し。（再構成）後 9は、3に）
4
7 9
32 25 16 18
81 59 38 42 95
<下の未完成プログラムを実行すると>
1 2 3 4 5 6 7 8 9 10 11 12 4 7 16 32 25 95 18 81 59 38 42 0 4 7 16 32 25 95 18 81 59 38 42 0 1 2 3 4 5 6 7 8 9 10 11 12 4 7 16 32 25 95 18 81 59 38 42 9 4 7 16 32 25 95 18 81 59 38 42 9 (up_heapが何もしないので、末尾に9が追加されただけ。ヒープの制約を満たさない。9の親は12/2=6で、95)
解答例
#include <stdio.h>
#define N 12 /* 11 + 1 */
void up_heap(int n); /* 課題です */
void insert(int x);
void print_heap(int n);
void print_tree_heap(int n);
int S[N+1]={0,4,7,16,32,25,95,18,81,59,38,42,0};
void print_heap(int n) {
int i;
for (i=1; i <= n; i++)
printf("%3d", i);
printf("\n");
for (i=1; i <= n; i++)
printf("%3d",S[i]);
printf("\n");
printf("\n");
}
void print_tree_heap(int n){
int i, j;
/* 2の累乗ごとに改行 */
for (i = 1 ; i <= n; i = i*2) {
for (j= i ; (j < i*2 && j <= n) ; j++)
printf("%3d", S[j]);
printf("\n");
}
printf("\n\n");
}
void up_heap(int n) {
int i, j, v;
v = S[n]; /* 最後尾の値 vは最後まで変わらないことに注意 */
i = n; /* 子 i 一番最初は最後尾。下ではiの位置にvがあってよいかをチェック */
j = n/2; /* 親 iが奇数でもOK */
while(j >= 1) {
if(S[j] >= v) { /* 親の方が、vより大きい。親を下げなければ */
S[i] = S[j]; /* 親の値を、子へ */
i=j; /* 親を子に */
j=j/2; /* さらに、その親へ。これら2つの操作が、上に向う */
print_heap(n);
} else {
break; /* 親(i/2)が子(i)より小さい。ここにv */
}
}
S[i]=v; /* ここで、最後尾の値vを、S[i]に代入 */
}
void insert(int x){
static int n = N-1; /* 最初は11個 1-11番目まで */
n++;
S[n] = x; /* 12番目にxを追加して */
up_heap(n); /* ヒープを再構成 */
}
int main(void) {
int i;
print_heap(N); /* 最後尾には0 */
print_tree_heap(N);
insert(9); /* 最後尾に9を追加し、ヒープを上方に再構成 */
print_heap(N);
print_tree_heap(N);
return 0;
}