アルゴリズム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種類のデータ

• rand800k.txt -- 800000個のデータがランダムに並んでいる
• inc800k.txt -- 800000個のデータが昇べきの順に並んでいる
• dec800k.txt -- 800000個のデータが降べきの順に並んでいる

[注意] データは、右クリックで手元に保存してから使って下さい。大きいデータなのでブラウザで閲覧しようとするとブラウザの動作が停止することがあります。