| 目次 | 索引 |
|---|---|
h2 ヒープソート toc-heapsort
h3 ヒープとは toc-what-is-a-heap
完全二分木で、親節点の値が必ず子節点の値以上であるものを、
index ヒープ heap ひいふ
と呼びます。
ヒープでは、根の値が最大になります。
以下はヒープの例です。
5
|
+-----+-----+
| |
4 1
|
+---+---+
| |
3 2
完全二分木の節点が
index ヒープ条件 heap condition ひいふしようけん
を満たすとは、
その節点を根と見なした木がヒープであることと定義します。
葉は、子がないのでヒープ条件を満たします。
根がヒープ条件を満たせば、その完全二分木はヒープです。
ヒープは完全二分木ですので、
ここでは配列によって表現します。
添字 0 には、番人として正の無限大 ∞ を格納します。
上記の例では、{∞, 5, 4, 1, 3, 2} となります。
h3 節点の挿入と削除 toc-insert-delete
ヒープに節点を挿入したり、ヒープから節点を削除したりしますと、
一般的にはヒープではなくなります。
しかし、ヒープ条件が壊れるのは一部の節点ですので、
うまく値を交換しますと、ヒープが修復できます。
例えば、上記のヒープに節点 6 を挿入します。
5
|
+-----+-----+
| |
4 1
| :
+---+---+ .....
| | :
3 2 6
まず、節点 6 の親 1 でヒープ条件が壊れますので、
1 と 6 を交換します。
5
|
+-----+......
| :
4 6
| |
+---+---+ +---+
| | |
3 2 1
次に、節点 6 の親 5 でヒープ条件が壊れますので、
5 と 6 を交換します。
6
|
+-----+-----+
| |
4 5
| |
+---+---+ +---+
| | |
3 2 1
これで、ヒープが修復されました。
ヒープに新しい葉が挿入された場合、その親、さらにその親と訪ねていき、
親の値が子の値より小さいなら交換することを繰り返しますと、
ヒープが修復できます。
ここで、途中で親の値が子の値以上であれば、
それ以上交換する必要がないことに注意してください。
特に、番人 a[0] = ∞ のおかげで、根より上を訪ねることはありません。
節点の削除は、節点の挿入と似ていますが、やや複雑になります。
例えば、次のヒープの根 6 を削除します。
6
|
+-----+-----+
| |
4 5
| |
+---+---+ +---+
| | |
3 2 1
まず、完全二分木に戻すため、葉 1 を根に移動します。
1
:
.............
: :
4 5
|
+---+---+
| |
3 2
次に、節点 1 でヒープ条件が壊れますので、
子 4 と子 5 を比較して大きい方の 5 を選び、
1 と 5 を交換します。
5
|
+-----+-----+
| |
4 1
|
+---+---+
| |
3 2
これでヒープが修復されました。
ヒープの根が削除された場合、まず最も下の最も右の葉を根に移動します。
そして、その子、さらにその子と訪ねていき、
親の値が子の値より小さいなら交換することを繰り返しますと、
ヒープが修復できます。
ここで、一般的に親子の関係は次のいずれかです。
1. 子が 2 つあり、親の値≧一方の子の値≧他方の子の値。
2. 子が 2 つあり、一方の子の値＞親の値≧他方の子の値。
3. 子が 2 つあり、一方の子の値≧他方の子の値＞親の値。
4. 子が 1 つあり、親の値≧子の値。
5. 子が 1 つあり、子の値＞親の値。
6. 子がない。
場合 1, 4, 6 では、それ以上交換する必要はありません。
場合 2 でも場合 3 でも、2 つ子の値を比較して、
大きい方の値と親の値を交換します。
場合 5 では、単純に親の値と子の値を交換します。
h3 ヒープソートの考え方 toc-heapsort-ideas
index ヒープソート heapsort ひいふそおと
とは、ヒープを利用した整列法です。
ヒープソートは、次の 2 段階で整列します。
1. ヒープに一つずつ要素を挿入してヒープを生成する。
2. ヒープから一つずつ最大要素を削除する。
ここでは例として、
{2, 3, 5, 4, 8, 1, 7, 9, 6} を整列します。
まず、ヒープ生成部分では次のようになります。
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
続いて、最大要素削除部分では次のようになります。
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
h3 ヒープソートのプログラム toc-heapsort-programs
ヒープソートのプログラムは次のようになります。
この中で、メソッド 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] までを完全二分木と見なします。
なお、プログラムでは、実際に値の交換を繰り返すのではなく、
値を一つずつずらすようにしています。
class Heapsort {
public static void main (String[] args) {
int[] a = new int[10];
initial(a);
shuffle(a);
print(a);
heapsort(a);
print(a);
}
static void initial (int[] a) {
int i;
a[0] = Integer.MAX_VALUE;
for (i = 1; i < a.length; i++) {
a[i] = i;
}
}
static void swap (int[] a, int x, int y) {
int temp;
temp = a[x];
a[x] = a[y];
a[y] = temp;
}
static void shuffle (int[] a) {
int i, rand;
for (i = 1; i < a.length; i++) {
rand = (int) (Math.random() * (a.length - 1)) + 1;
swap(a, i, rand);
}
}
static void print (int[] a) {
int i;
for (i = 1; i < a.length; i++) {
System.out.print(" " + a[i]);
}
System.out.println();
}
static void upheap (int[] a, int n) {
int key = a[n];
while (a[n / 2] < key) {
a[n] = a[n / 2];
n = n / 2;
}
a[n] = key;
}
static void downheap (int[] a, int n, int k) {
int key = a[k];
while (2 * k < n && (a[2 * k] > key || a[2 * k + 1] > key)) {
if (a[2 * k] > a[2 * k + 1]) {
a[k] = a[2 * k];
k = 2 * k;
} else {
a[k] = a[2 * k + 1];
k = 2 * k + 1;
}
}
if (2 * k == n && a[2 * k] > key) {
a[k] = a[2 * k];
k = 2 * k;
}
a[k] = key;
}
static void heapsort (int[] a) {
int i;
for (i = 2; i < a.length; i++) {
upheap(a, i);
print(a);
}
for (i = a.length - 1; i > 1; i--) {
swap(a, 1, i);
downheap(a, i - 1, 1);
print(a);
}
}
}
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
1 2 3 4 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%
h2 演習 9 toc-exercises
ヒープ生成部分で、メソッド upheap ではなく downheap を用いる
ヒープソートのプログラムを作成してください。
メソッド downheap(a, n, k) を呼び出すためには、
節点 a[k] の左の子も右の子もヒープ条件を満たす必要があります。
これは、葉以外の節点を下から上への順番で訪ね、
その節点がヒープ条件を満たすようにすればよいです。
すると、最後には根がヒープ条件を満たし、ヒープが生成できます。
b04a001@AsiaA1:~/comp3b% java Heapsort2
4 1 2 6 3 8 9 5 7
4 1 2 7 3 8 9 5 6
4 1 9 7 3 8 2 5 6
4 7 9 6 3 8 2 5 1
9 7 8 6 3 4 2 5 1
8 7 4 6 3 1 2 5 9
7 6 4 5 3 1 2 8 9
6 5 4 2 3 1 7 8 9
5 3 4 2 1 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
1 2 3 4 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%
今日の演習9の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（11月26日）を明記してください。