アルゴリズムB 第3回


ヒープ

「ヒープ」という用語には2種類の意味があるので注意しましょう。

ヒープを平衡木を利用して実現することも可能ですが、 それだと無駄が多いので通常は半順序木を使って実装します。

半順序木による実装

平衡木の替りに半順序木 (partial ordered tree、「親ノードは子ノードよりも小さいか等しい」 という性質を持つ木)を使う。

「根から葉への距離の差がどの葉に関しても1以内。最下段の葉は左に寄せる」

削除の様子

根を取り除くには、「最下段の最も右の要素」を根の場所に移動して、 あとは2つの子ノードのうち小さいものと入れ替えて行けばよい。

挿入の様子

新しいデータを挿入するには、「最下段の最も右の要素」として挿入した後、 親ノードの方が大きい限り交換してゆく。

配列を用いたヒープの表現

半順序木の実装には「ヒープ」を使う。

親ノード a[i]
子ノード a[2*i] と a[2*i+1]

インデックス 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
データ 未使用 3 8 16 13 15 22 19 17 27 19

Javaのクラスによるヒープの実装

MyHeap.java
授業で配布するプリントを参照して下さい。
RunMyHeap.java
授業で配布するプリントを参照して下さい。
heapdata01.txt
show
insert 7
insert 5
insert 4
insert 6
insert 2
show
insert 3
show
poll
show
poll
show
insert 1
show
poll
show
RunMyHeap.javaの実行例
$ java RunMyHeap < heapdata01.txt
[]
insert 7
insert 5
insert 4
insert 6
insert 2
[2 4 5 7 6 ]
insert 3
[2 4 3 7 6 5 ]
poll 2
[3 4 5 7 6 ]
poll 3
[4 6 5 7 ]
insert 1
[1 4 5 7 6 ]
poll 1
[4 6 5 7 ]

ヒープソート

ヒープソートのアルゴリズム(プログラム風) p.357 List 16.1

ヒープソートのアルゴリズム
[1] 整列すべき配列を受け取る
[2] 木を生成する
[3] 木に要素を繰り返し挿入する ... O(n)回
[4] 木から最小のキーを持つ要素を取り出す操作を繰り返す  ... O(n)

生成する木として平衡木(AVL木やB木)や半順序木を使えば、 1個の要素を木に挿入したり、 木から削除したりする手間は O(log n)

したがって、全体の計算量は O(n log n)

ヒープソート実装の工夫

整列すべきデータの配列の中にヒープを構築する。 p.374 Fig.16.8 のようにして半順序木を生成し、 p.373 Fig.16.6 のようにして半順序木から最も小さいデータを 配列の後ろに取り出していく。

HeapSort.java
授業で配布するプリントを参照して下さい。
HeapSort.javaの実行例
[添字が0の場所は使いません。そのためa[0]は0のままです]
% javac HeapSort.java
% java HeapSort -d
データの個数を入力して下さい  8
4 7 2 1 5 8 6 3
from=4, to=8: 0 4 7 2 1 5 8 6 3 
from=3, to=8: 0 4 7 2 1 5 8 6 3 
from=2, to=8: 0 4 1 2 3 5 8 6 7 
from=1, to=8: 0 1 3 2 4 5 8 6 7 
from=1, to=7: 0 2 3 6 4 5 8 7 1 
from=1, to=6: 0 3 4 6 7 5 8 2 1 
from=1, to=5: 0 4 5 6 7 8 3 2 1 
from=1, to=4: 0 5 7 6 8 4 3 2 1 
from=1, to=3: 0 6 7 8 5 4 3 2 1 
from=1, to=2: 0 7 8 6 5 4 3 2 1 
from=1, to=1: 0 8 7 6 5 4 3 2 1 
0 8 7 6 5 4 3 2 1 


アルゴリズムB 演習


作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。

提出した後は、正しく提出されていることを http://nw.tsuda.ac.jp/class/algoA/local/handin/ で必ず確認しておいて下さい。

提出〆切は次回の講義の開始時刻です。

課題3a: Heapのプログラムを作成しよう

提出ファイルMyHeap.java
コメント欄:heapdata02.txtを入力として与えたときの出力
提出先: 「宿題提出Web:アルゴリズムB:課題3a」 http://nw.tsuda.ac.jp/class/algoB/local/handin/up.php?id=kadai3a

MyHeap.javaの欠けている部分のコードを書きなさい。

heapdata02.txt
insert 9
insert 7
insert 8
insert 5
insert 6
insert 7
insert 6
insert 4
insert 2
insert 8
insert 1
insert 12
insert 6
show
poll
show
poll
show
poll
show
insert 1
show

課題3b: HeapSortのプログラムを動かしてみよう

提出ファイルHeapSort.java
コメント欄:rand400k.txt, inc400k.txt, dec400k.txtそれぞれに対する計算時間
提出先: 「宿題提出Web:アルゴリズムB:課題3b」 http://nw.tsuda.ac.jp/class/algoB/local/handin/up.php?id=kadai3b

HeapSort.java が http://nw.tsuda.ac.jp/class/algoB/sortdata/ の下の 3種類のデータ

を処理するのに必要な時間をそれぞれ計測し、答えなさい。 [注意] データは、右クリックで手元に保存してから使って下さい。大きいデータなのでブラウザで閲覧しようとするとブラウザの動作が停止することがあります。