アルゴリズムとデータ構造 6月2日分

アルゴリズムとデータ構造
第3章ヒープ
6月1０日分（解答編）
情報知能学科
白井英俊
ヒープ
• ヒープ(heap)とは、特殊な二進木
定義3.2 高さkの二進木Tがヒープであるための
必要十分条件は次の(i), (ii)を満たすこと
(i) 深さ0 ～ k-1 の可能な頂点はすべて使われ、
深さkの頂点は左から順に使われている
(ii) 頂点uが頂点vの親なら
uの値( f(u) ) ≧ vの値( f(v) )
親
子
ヒープの特徴
頂点の番号のつけ方：
1
可能な頂点すべてに、
3
2
4
8
5
9
6
上から下、左から右
7
10
この番号の付け方から、高さ n (> k)のヒープでは、
★深さ k の最も左の頂点の番号は 2k
★深さ k の最も右の頂点の番号は 2(k+1) - 1
配列を用いたヒープの表現
このように、ヒープは「配列」を使って簡単に表せる
0
1
①
根
2
深さ１
3
②
③
4
深さ2
⑤ ⑥
5
⑦
④
6
⑨
7
⑧
深さ3 8
9
｛
偶数：
左の子
奇数：
右の子
…
…
二進木による表現
｛
｛
根以外は
配列による表現
ヒープソート(Heap Sort)
ヒープを用いてソート（並び替え）を行う
二分探索木によるソート
手続き：
(1) x1, x2, …, xn からヒープ(木)を作ると比較して「最悪の場合」
でもこれが保証されてい
るのが特長
計算量は O(n * log n)
ヒープ木においては根が最大の値の頂点
(2) 根と『最も深い頂点のうち最も右端の頂点』とを交
換し、『根だった頂点をヒープから切り離し』てから
ヒープを作り直す(remake)。この操作一回ごとの計
算量は O(log n)
(3) (2)を繰り返し、切り離された頂点をすべて並べると
ソート完成(新しく切り離された頂点が最小、古いも
のが最大)
ステップ１：ヒープを作る
入力データ:
8
5
3
1
7
10
20
{ 8 5 7 3 10
9 6 1 20 }
9
6
ヒープ条件(ii)を破っ
ているので、『修正』
が必要
前出の問題: ヒープ条件(ii)が成り立つ
ようにするには、どのように『修正』し
たらよいか？
答えは次のスライド…
ステップ１：ヒープを作る：結果
20
10
8
1
9
5
3
7
6
どの親子の組み合わせにおいても
ヒープ条件(ii)が成り立つ
ヒープソート(第2ステップ
（２）根と『最も深い頂点のうち最も右端の頂点』
とを交換し、『根だった頂点をヒープから切り
離し』てからヒープを作り直す(remake)。
(3) (2)を繰り返し、切り離された頂点をすべて並
べるとソート完成(新しく切り離された頂点が
最小、古いものが最大)
（１）のヒープの修正と紛らわしいので、
ここでは「ヒープの作り直し(remake)」と
呼ぶことにする
ヒープソート(続き)
「根と最後の要素を取り換え、ヒープを作り直す
(remake)」の繰り返し(ヒープソートのステップ(2))
20
10
8 ≧ 5
1
3
≧
9
7
1. 根と『最も深く右側の頂
点』とを交換し、根だった頂
点を切り離す
2. ヒープ条件(ii)を満たすよ
う、ヒープを作り直す
親頂点と、子頂点のう
ち大きいほうを交換。
6
問題：ヒープをどのように作り直すか？
問題：この後ヒープをどのように作り直すか？
ヒープソート(配列版)
①
③
⑤
⑥
⑦
⑧
⑨
≧
④
≧
②
20
10
9
8
5
7
6
1
3
「根と最後の要素を取り換え、ヒープを作り直
す」の繰り返し(ヒープソートのステップ(2))
問題：ヒープをどのように作り直すか？
1. 根と『最も深く右側の頂
点』とを交換し、根だった頂
点を切り離す
2. ヒープ条件(ii)を満たすよ
う、ヒープを作り直す
親頂点と、子頂点のう
ち大きいほうを交換。
問題：この後ヒープをどのように作り
直すか？
ヒープソートの真髄
ヒープを配列で表わす
⇒『木』よりも簡単なデータ構造で実行可能
インデックスによって、根の頂点を簡単に求めることが
できる
また、注目している頂点のインデックスから、その親や
子の頂点が何かが簡単に計算できる
問題：注目している頂点のインデックスをxとすると、
その親と子の頂点のインデックスは？
解答：
親のインデックス: x/2 （の整数部分、 x / 2 と表す）
子のインデックス: 左の子は 2*x、右の子は 2*x+1
ヒープの演習（続）
2. 以下の配列はヒープの条件を満たしているか？満たしていなければ(1)から
演習を行え。満たしているとすれば(2)から演習を行え。
1
3
2
30 25
4
7
8
9
12 10
8
6
5
20 16 24 18
10
15
(1) 1番目の要素から順に10番目までの要素をヒープにする操作を行い、最終
的に得られたヒープを示せ。
解答：これはヒープの条件をみたしているので、（1）は行わない
(2) 次に、1番目の要素と10番目の要素を入れ替え、10番目の要素を除いた
のこりの配列、つまり1～9番目の要素からなる配列に対し「ヒープの作り直
し」をせよ（演習3.7)
解答：出来上がったものは…
1
2
30 25
3
4
5
6
20 16 24 18
7
8
9
12 10
8
10
15
ヒープの演習（続）
(3) これに続けて9番目の要素、8番目の要素、…,2番目の要素を順に１番目
の要素と入れ替えては（２）と同様の「ヒープを作り直す」操作を行い、最終的
に得られた配列を示せ。
1
2
3
4
5
6
7
8
9
10
30 25
20 16 24 18
12 10
8
15
25 24
20 16 15 18
12 10
8
30
24
16
20 10
15 18
12
8
25
30
20 16
18 10
15
8
12
24 25
30
18
12
15
8
20
24 25
30
16
10
ヒープの演習（続）
(3) これに続けて9番目の要素、8番目の要素、…,2番目の要素を順に１番目
の要素と入れ替えては（２）と同様の「ヒープを作り直す」操作を行い、最終的
に得られた配列を示せ。
1
2
3
4
5
6
7
18
16
12
10
15
8
20
24 25
30
16
15
12
10
8
18
20
24 25
30
15
10
12
8
16 18
20
24
25
30
12
10
8
15
16 18
20
24 25
30
10
8
12
15
16
18
20 24
25
30
8
10
12
15
16
18
20 24
25
30
8
9
10

Download Report