スライド タイトルなし

ヒープソートの復習
1
ヒープソート(heap sort)(p.94) ※



ヒープを用いてデータの整列を行うアルゴリズム
計算量 O (n log n)
ヒープ : 配列により半順序木を実現したもの
常に子が親より
大きい木の例
常に子が親より
小さい木の例
3
5
6
9
8
10 18 9
9
10
8
10
6
4 1
9
3
2
7
6
2
ヒープソートの原理 ※
1.ヒープ(半順序木)を作る(優先度つき待ち行列
に入れる)
2.以下の処理を繰り返して並べかえる
1. ヒープの先頭の要素と末尾の要素を交換
2. [先頭]~[末尾-1]の部分の半順序を回復させる
優先度つき
リストL
2,9,5,6,… 待ち行列
9
6
5
2
3
1.ヒープを作る
部分木の根の要素を適切な位置まで下げる操作を
繰り返すことで,半順序木をボトムアップに構築する
10
← a[0]
6
9
5
3
15
18
要素数 n = 15
9
15
8
11
12
9
20
← a[n/2-1]
(=a[6])
a[n-1]
(=a[14])
10 ←
4
2.並べかえ
2-1 半順序木の根と右端の葉を交換
3
12
5
6
5
9
8
9
10
10 18 9 15 11 15 20 12
[0]
a
6
9
8
9
10
10 18 9 15 11 15 20 3
[n-1]
12 5 9 6 8 9 10 10 18 9 15 11 15 20 3
5
2.並べかえ(つづき)
2-1 残りの部分の半順序の回復
子が親より小さい間,
2つの子のうち
小さい方の子
と親を交換していく
この部分のヒープを再構成
[0] [1][2] [3] [4]
a 12
5 12
65 9 10
6 8
この部分の
半順序を
回復させる
12
5
6
9
8
9
10
10 18 9 15 11 15 20 3
[7] [8]
[n-2][n-1]
9 10 10 18 9 15 11 15 20
着目する節点の左の子は2*i+1、右の子はそのひとつ後ろにある
3
6
プログラムの概要
begin
heapsort
heapify
1.ヒープ(半順序木)を作る

downMin
deleteMin
2.以下の処理を繰り返す
1.
downMin
2.
end
ボトムアップに節点[2/n - 1]
~[0]をしらべ、半順序を満
足するように木を作る
ヒープの先頭の要素と末尾
の要素を交換
トップダウンに[先頭]~[末尾
-1]の部分の半順序を回復
させる
7