[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

コンピュータIIIB(Javaアルゴリズム)第8回

目次
8.1 木(2)
8.1.1 ヒープ
8.1.2 ヒープの操作
8.1.3 ヒープソート
8.2 演習8
8.3 レポート課題
8.4 参考文献
索引
ヒープ   ヒープ条件   ヒープソート  

8.1 木(2)

8.1.1 ヒープ

完全二分木で、親節点の値が必ず子節点の値以上であるものを、 ヒープheap ) と呼びます。 ヒープでは、根の値が最大になります。 以下はヒープの例です。

ヒープの例
図 8.1  ヒープの例

完全二分木の節点が ヒープ条件heap condition ) を満たすとは、その節点を根と見なした木がヒープであることと定義します。 葉は、子がないのでヒープ条件を満たします。 根がヒープ条件を満たせば、その完全二分木はヒープです。

ヒープは完全二分木ですので、ここでは配列によって表現します。 添字0には、番兵として正の無限大 ∞ を格納します。 上記の例では、{∞, 5, 4, 1, 3, 2} となります。

8.1.2 ヒープの操作

ヒープに節点を挿入したり、ヒープから節点を削除したりしますと、一般的にはヒープではなくなります。 しかし、ヒープ条件が壊れるのは一部の節点ですので、うまく値を交換しますと、ヒープが修復できます。

例えば、上記のヒープに節点6を挿入します。

ヒープへの要素の挿入
図 8.2  ヒープへの要素の挿入(1)

まず、節点6の親1でヒープ条件が壊れますので、1と6を交換します。

ヒープへの要素の挿入
図 8.3  ヒープへの要素の挿入(2)

次に、節点6の親5でヒープ条件が壊れますので、5と6を交換します。

ヒープへの要素の挿入
図 8.4  ヒープへの要素の挿入(3)

これで、ヒープが修復されました。

ヒープに新しい葉が挿入された場合、その親、さらにその親と訪ねていき、親の値が子の値より小さいなら交換することを繰り返しますと、ヒープが修復できます。 ここで、途中で親の値が子の値以上であれば、それ以上交換する必要がないことに注意してください。 特に、番兵 a[0] = ∞ のおかげで、根より上を訪ねることはありません。

節点の削除は、節点の挿入と似ていますが、やや複雑になります。 例えば、次のヒープの根6を削除します。

ヒープからの要素の削除
図 8.5  ヒープからの要素の削除(1)

まず、完全二分木に戻すため、葉1を根に移動します。

ヒープからの要素の削除
図 8.6  ヒープからの要素の削除(2)

次に、節点1でヒープ条件が壊れますので、子4と子5を比較して大きい方の5を選び、1と5を交換します。

ヒープからの要素の削除
図 8.7  ヒープからの要素の削除(3)

これでヒープが修復されました。

ヒープの根が削除された場合、まず最も下の最も右の葉を根に移動します。 そして、その子、さらにその子と訪ねていき、親の値が子の値より小さいなら交換することを繰り返しますと、ヒープが修復できます。

一般的に、親子の値の大小関係は次のいずれかです。

表 8.1  親子の値の大小関係
場合 子の数 大小関係
1 2 親の値≧一方の子の値≧他方の子の値
2 2 一方の子の値>親の値≧他方の子の値
3 2 一方の子の値≧他方の子の値>親の値
4 1 親の値≧子の値
5 1 子の値>親の値
6 0

ヒープの修復の際、場合1, 4, 6では、それ以上交換する必要はありません。 場合2でも場合3でも、2つ子の値を比較して、大きい方の値と親の値を交換します。 場合5では、単純に親の値と子の値を交換します。

8.1.3 ヒープソート

ヒープソートheapsort ) とは、ヒープを利用した整列法です。 ヒープソートは、次の2段階で整列します。

  1. ヒープに一つずつ要素を挿入してヒープを生成する。
  2. ヒープから一つずつ最大要素を削除する。

ここでは例として、{2, 3, 5, 4, 8, 1, 7, 9, 6} を整列します。 まず、ヒープ生成部分では次のようになります。

ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ
図 8.8  ヒープソートのイメージ(1)

続いて、最大要素削除部分では次のようになります。

ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ ヒープソートのイメージ
図 8.9  ヒープソートのイメージ(2)

ヒープソートのプログラムは次のようになります。 この中で、メソッド upheapdownheap が重要です。

メソッド 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%

8.2 演習8

ヒープ生成部分で、メソッド 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.3 レポート課題

今日の演習8の答案(Javaプログラム)をメールで提出してください。 メールの差出人は学内のアドレス(b04a001@twcu.ac.jpなど)とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日(12月1日)を明記してください。


8.4 参考文献


[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

2006年12月1日更新
小西 善二郎 konishi@twcu.ac.jp
Copyright (C) 2006 Zenjiro Konishi. All rights reserved.