完全二分木で、親節点の値が必ず子節点の値以上であるものを、 ヒープ （ heap ） と呼びます。 ヒープでは、根の値が最大になります。 以下はヒープの例です。
完全二分木の節点が ヒープ条件 （ heap condition ） を満たすとは、その節点を根と見なした木がヒープであることと定義します。 葉は、子がないのでヒープ条件を満たします。 根がヒープ条件を満たせば、その完全二分木はヒープです。
ヒープは完全二分木ですので、ここでは配列によって表現します。 添字0には、番兵として正の無限大 ∞ を格納します。 上記の例では、{∞, 5, 4, 1, 3, 2} となります。
ヒープに節点を挿入したり、ヒープから節点を削除したりしますと、一般的にはヒープではなくなります。 しかし、ヒープ条件が壊れるのは一部の節点ですので、うまく値を交換しますと、ヒープが修復できます。
例えば、上記のヒープに節点6を挿入します。
まず、節点6の親1でヒープ条件が壊れますので、1と6を交換します。
次に、節点6の親5でヒープ条件が壊れますので、5と6を交換します。
これで、ヒープが修復されました。
ヒープに新しい葉が挿入された場合、その親、さらにその親と訪ねていき、親の値が子の値より小さいなら交換することを繰り返しますと、ヒープが修復できます。 ここで、途中で親の値が子の値以上であれば、それ以上交換する必要がないことに注意してください。 特に、番兵 a[0] = ∞ のおかげで、根より上を訪ねることはありません。
節点の削除は、節点の挿入と似ていますが、やや複雑になります。 例えば、次のヒープの根6を削除します。
まず、完全二分木に戻すため、葉1を根に移動します。
次に、節点1でヒープ条件が壊れますので、子4と子5を比較して大きい方の5を選び、1と5を交換します。
これでヒープが修復されました。
ヒープの根が削除された場合、まず最も下の最も右の葉を根に移動します。 そして、その子、さらにその子と訪ねていき、親の値が子の値より小さいなら交換することを繰り返しますと、ヒープが修復できます。
一般的に、親子の値の大小関係は次のいずれかです。
| 場合 | 子の数 | 大小関係 |
|---|---|---|
| 1 | 2 | 親の値≧一方の子の値≧他方の子の値 |
| 2 | 2 | 一方の子の値＞親の値≧他方の子の値 |
| 3 | 2 | 一方の子の値≧他方の子の値＞親の値 |
| 4 | 1 | 親の値≧子の値 |
| 5 | 1 | 子の値＞親の値 |
| 6 | 0 |
ヒープの修復の際、場合1, 4, 6では、それ以上交換する必要はありません。 場合2でも場合3でも、2つ子の値を比較して、大きい方の値と親の値を交換します。 場合5では、単純に親の値と子の値を交換します。
ヒープソート （ heapsort ） とは、ヒープを利用した整列法です。 ヒープソートは、次の2段階で整列します。
ここでは例として、{2, 3, 5, 4, 8, 1, 7, 9, 6} を整列します。 まず、ヒープ生成部分では次のようになります。
続いて、最大要素削除部分では次のようになります。
ヒープソートのプログラムは次のようになります。 この中で、メソッド upheap と downheap が重要です。
メソッド upheap ( a , n ) は、 a [1] から a [ n - 1] までがヒープであるとき、 a [1] から a [ n ] までもヒープになるように、 a [ n ] から上に向かって値を交換するものです。
メソッド downheap ( a , n , k ) は、 a [ k ] の左の子も右の子もヒープ条件を満たすとき、 a [ k ] もヒープ条件を満たすように、 a [ k ] から下に向かって値を交換するものです。 ただし、 a [1] から a [ n ] までを完全二分木と見なします。
なお、プログラムでは、実際に値の交換を繰り返すのではなく、値を一つずつずらすようにしています。
/* 1*/ class Heapsort { /* 2*/ public static void main (String[] args) { /* 3*/ int i, temp, SENTINEL = 9999; /* 4*/ int[] a = {SENTINEL, 2, 3, 5, 4, 8, 1, 7, 9, 6}; /* 5*/ for (i = 1; i < a.length; i++) { /* 6*/ System.out.print(" " + a[i]); /* 7*/ } /* 8*/ System.out.println(); /* 9*/ for (i = 2; i < a.length; i++) { /* 10*/ upheap(a, i); /* 11*/ } /* 12*/ for (i = a.length - 1; i >= 2; i--) { /* 13*/ temp = a[i]; /* 14*/ a[i] = a[1]; /* 15*/ a[1] = temp; /* 16*/ downheap(a, i - 1, 1); /* 17*/ } /* 18*/ } /* 19*/ static void upheap (int[] a, int n) { /* 20*/ int i, v = a[n]; /* 21*/ while (a[n / 2] <= v) { /* 22*/ a[n] = a[n / 2]; /* 23*/ n = n / 2; /* 24*/ } /* 25*/ a[n] = v; /* 26*/ for (i = 1; i < a.length; i++) { /* 27*/ System.out.print(" " + a[i]); /* 28*/ } /* 29*/ System.out.println(); /* 30*/ } /* 31*/ static void downheap (int[] a, int n, int k) { /* 32*/ int i, j, v = a[k]; /* 33*/ while (k <= n / 2) { /* 34*/ j = 2 * k; /* 35*/ if (j < n && a[j] < a[j + 1]) { /* 36*/ j++; /* 37*/ } /* 38*/ if (a[j] <= v) { /* 39*/ break; /* 40*/ } /* 41*/ a[k] = a[j]; /* 42*/ k = j; /* 43*/ } /* 44*/ a[k] = v; /* 45*/ for (i = 1; i < a.length; i++) { /* 46*/ System.out.print(" " + a[i]); /* 47*/ } /* 48*/ System.out.println(); /* 49*/ } /* 50*/ }
b04a001@AsiaA1:~/comp3b% java Heapsort 2 3 5 4 8 1 7 9 6 3 2 5 4 8 1 7 9 6 5 2 3 4 8 1 7 9 6 5 4 3 2 8 1 7 9 6 8 5 3 2 4 1 7 9 6 8 5 3 2 4 1 7 9 6 8 5 7 2 4 1 3 9 6 9 8 7 5 4 1 3 2 6 9 8 7 6 4 1 3 2 5 8 6 7 5 4 1 3 2 9 7 6 3 5 4 1 2 8 9 6 5 3 2 4 1 7 8 9 5 4 3 2 1 6 7 8 9 4 2 3 1 5 6 7 8 9 3 2 1 4 5 6 7 8 9 2 1 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 b04a001@AsiaA1:~/comp3b%
ヒープ生成部分で、メソッド upheap ではなく downheap を用いるヒープソートのプログラムを作成してください。
メソッド downheap ( a , n , k ) を呼び出すためには、節点 a [ k ] の左の子も右の子もヒープ条件を満たす必要があります。 したがって、葉以外の節点を下から上への順番で訪ねることにします。 訪ねた節点に対しては、メソッド downheap を呼び出し、その節点がヒープ条件を満たすようにします。 すると、最後には根がヒープ条件を満たし、ヒープが生成できます。
b04a001@AsiaA1:~/comp3b% java Heapsort2 2 3 5 4 8 1 7 9 6 2 3 5 9 8 1 7 4 6 2 3 7 9 8 1 5 4 6 2 9 7 6 8 1 5 4 3 9 8 7 6 2 1 5 4 3 8 6 7 4 2 1 5 3 9 7 6 5 4 2 1 3 8 9 6 4 5 3 2 1 7 8 9 5 4 1 3 2 6 7 8 9 4 3 1 2 5 6 7 8 9 3 2 1 4 5 6 7 8 9 2 1 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 b04a001@AsiaA1:~/comp3b%
今日の演習8の答案（Javaプログラム）をメールで提出してください。 メールの差出人は学内のアドレス（b04a001@twcu.ac.jpなど）とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（11月25日）を明記してください。