アルゴリズムb 第4回

ヒープ

• データ構造を表す用語で、親ノードが子ノードよりも小さい木構造のこと。最小値や最大値を求めるのに適している。 ← 今回はこちらの意味
• プログラム実行時に、任意のタイミングで割り当て or 解放できるメモリ

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

半順序木による実装

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

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

削除の様子

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

挿入の様子

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

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

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

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

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

show
insert 7
insert 5
insert 4
insert 6
insert 2
show
insert 3
show
poll
show
poll
show
insert 1
show
poll
show

$ javac 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 のようにして半順序木から最も小さいデータを 配列の後ろに取り出していく。

[添字が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://ynitta.com/class/algoB/local/handin/ で必ず確認しておいて下さい。

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

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

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

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

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

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

• rand400k.txt -- 400000個のデータがランダムに並んでいる
• inc400k.txt -- 400000個のデータが昇べきの順に並んでいる
• dec400k.txt -- 400000個のデータが降べきの順に並んでいる