アルゴリズムとデータ構造
第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
｛
偶数：
左の子
奇数：
右の子
…
…
二進木による表現
｛
｛
根以外は
配列による表現
ヒープへの要素の追加(挿入)手続き
手続き：以下の2ステップで行う
(1) 新たな要素を値とする頂点をヒープに追加
⇒ 条件(i)を満たすところに追加
(2) 次に、ヒープ条件(ii)を満たすように修
正(reform)する
ヒープへの要素の追加(1)
ヒープの条件(i)を満たすように要素を追加する
ことは、
(b)二進木で表す場合、｢可能な頂点を左から順
に使う」
(a) 配列で表す場合は分かりやすい
⇒ ヒープの最後の要素のインデックスを
x とすれば、x+1 番目に要素を追加すれ
ばよい（最後尾に付け加える）
ヒープへの要素の追加(1)
例：
②
④
8
①
3
①
8
②
5
③
④
7
3
⑤
10
に3を追加する…
③
5
7
⑤
10
それには、ここしかない
そして、ヒープ条件(ii)を満たし
ているのでヒープが完成
さらに、 10を追加する。。。
これは、ヒープ条件(ii)を満たして
いないので『修正』が必要
上の二進木の配列表現
ヒープへの要素の追加(2)「修正」
• 追加した頂点を v とする
• ヒープの条件(ii)は、
親頂点の値≧子頂点の値
だから、これが満たされていればOK.
そうでなければ、上の条件を満たすように、頂
点を入れ替えていく（修正する）
ヒープへの要素の追加(2)続き
ヒープへの要素の追加の完成
②
右の二進木
の配列表現
④
①
8
②
5
③
7
④
3
⑤
10
3
条件を破っ
ている
8
①
③
5
7
⑤
10
条件を破っ
ている
ヒープを作る具体例
入力データ:
8
5
3
1
7
10
20
{ 8 5 7 3 10
9 6 1 20 }
9
6
ヒープ条件(ii)を破っ
ているので、『修正』
が必要
問題: ヒープ条件(ii)が成り立つ
ようにするには、どのように『修
正』したらよいか？
ヒープを作る具体例（配列版)
①
②
③
④
⑤
⑥
⑦
⑧
⑨
8
5
7
3
10
9
6
1
20
入力データ:
{ 8 5 7 3 10
9 6 1 20 }
ヒープ条件(ii)を破っ
ているので、『修正』
が必要
問題: ヒープ条件(ii)が成り立つ
ようにするには、どのように『修
正』したらよいか？
ヒープの演習
1. (a) 右の配列は、1～9番目までの要素は 0
ヒープの条件を満たす。そこに10番目の 1
要素として15を入れたとすれば、これは
ヒープの条件を満たしているか？その理 2
3
由も述べよ。
4
(b) 10番目の要素として15ではなく、
40が入っているとする。1～10番目ま 5
での要素からなる配列は、ヒープの
6
条件を満たしているか？その理由も
7
述べよ。
8
(c) (a)と(b)で、｢ヒープになっていな
いもの」に対し、1～10番目までの要 9
10
素からなる配列をヒープにする（教
科書演習3.6）ことを考える。その結 11
果のヒープを示せ。
30
25
28
20
24
26
18
19
11
X
ヒープの演習(解答)
1. (a) 右の配列は、1～9番目まで
0
の要素はヒープの条件を満たす。 1
ということは、ヒープ条件(1)も(2)も満たしている
2
3
ヒープ条件(1)は、配列で書いた場合に、要素が
順々に入っているということ。
4
5
ヒープ条件(2)は、どの親の値も子どもの値より大
きい、ということ。
6
(a) そこに10番目の要素として15を入れたとすれば、
7
これはヒープの条件を満たしているか？
8
配列の要素を順々にいれているのだから、ヒープ
9
条件(1)は満たしている。条件(2)を調べればよい
10
(b) 10番目の要素として40が入るとする。1～10番目
までの要素からなる配列は、ヒープの条件を満たすか？ 11
30
25
28
20
24
26
18
19
11
X１５
４０
大
小
ヒープの演習(解答)
(a)と(b)で、｢ヒープになっていな
いもの」に対し、1～10番目まで
の要素からなる配列をヒープにす
る（教科書演習3.6）ことを考え
る。その結果のヒープを示せ。
0
1
30
2
25
28
3
4
20
5
24
n番目の要素の｢親」は n/2 番目の要素
6
26
1
7
18
8
19
3
2
11
9
４０
7
10
4
5 6
11
9 10
8
親と子を比較して必要なら入れ替える
ヒープソート(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とすると、
その親と子の頂点のインデックスは？
ヒープの演習（続）
2. 以下の配列はヒープの条件を満たしているか？満たしていなければ(1)から
演習を行え。満たしているとすれば(2)から演習を行え。
(1) 1番目の要素から順に10番目までの要素をヒープにする操作を行い、最終
的に得られたヒープを示せ。
(2) 次に、1番目の要素と10番目の要素を入れ替え、10番目の要素を除いた
のこりの配列、つまり1～9番目の要素からなる配列に対し「ヒープの作り直
し」をせよ（演習3.7)
(3) これに続けて9番目の要素、8番目の要素、…,2番目の要素を順に１番目
の要素と入れ替えては（２）と同様の「ヒープを作り直す」操作を行い、最終的
に得られた配列を示せ。
(4) n 個の要素を持つ配列（1～n番目に要素があるとする）に対し、(1)の操作
でヒープを作る計算量のオーダーはどのくらいか、また(2)の手順で最終の
配列を得るための計算量のオーダーはどのくらいか？
1
2
30 25
3
4
5
6
20 16 24 18
7
8
9
12 10
8
10
15
プログラミング演習
• 問題１．1～n番目までの要素を持つ配列が与
えられているとする。
これがヒープの条件を満たしているかどうかを
判定するアルゴリズムとプログラムを作ろう。
条件1は当然成り立っているとすると、条件2が
成り立っているかどうかが問題。
1
2
30 25
3
4
5
6
20 16 24 18
7
8
9
12 10
8
10
15
プログラミング演習（問題１続き)
• 条件2は、どの頂点に対しても次が成り立てばよい。
親頂点の値≧子頂点の値
ここでn個の頂点があるヒープならば、「親頂点」で
あるのは、1(根）～n/2番目の頂点まで。
配列をxとすると：
for i in 1..n/2 # 親頂点を一つ一つ調べる
return false if (x[i] < x[i*2]) # 親頂点の値が子より小さい
return false if (i*2+1 <= n) && (x[i] < x[i*2+1])
end
return true # すべての親頂点が子よりも小さくない場合
プログラミング演習（問題１答)
def heapCheck(x)
n = x.size-1 # x.size は(n+1)を返すため
for i in 1..n/2 # 親頂点を一つ一つ調べる
return false if (x[i] < x[i*2]) # 親頂点の値が子より小さい
return false if (i*2+1 <= n) && (x[i] < x[i*2+1])
end
return true # すべての親頂点が子よりも小さくない場合
end
プログラミング問題
注意：これらはクラスメソッドを作る
のではなく、関数を作る問題
配列を用いてヒープソートするプログラムを作る。以下
は、そのための処理を構成するプログラムである。
(1)以下の条件を満たす関数reform_heapを作れ。入力は、
配列xとその最後の要素の番号n。ここで、x[1]～x[n-1]まで
はヒープの条件を満たしているものとする。そして、ヒープ
の条件を満たす配列ｘを出力する。 （難易度普通）
x[n]と、その親の要素の値とを比較し、ヒープ条件が守られて
いれば終了。さもなくば条件を守るように修正する。
(2)reform_heapを用いて、入力データ(数を要素とする配列）
からヒープ(配列で表現)を作る関数(makeHeap)を作れ。
（普通）
例：[8,5,7,3,10,9,6,1,20] という配列が入力として与えられた
時、 [nil, 20,10,9,5,8,7,6,1,3]というヒープ条件を満たす配列を
出力する
プログラミング問題（続き)
(3) ヒープ(配列で表現)において、根と最後の要素とを
交換する関数(swapNodes)を書け。（簡単）
swapNodesの入力(引数)を、配列ｘと、最後の要素
の番号nの二つとする。根はｘ[1]だから…
(4) 配列ｘ、整数iとｊを入力として、x[i] > x[j]ならばiを、
そうでなければjを返す関数（bigger)を作れ。 （簡
単）
これは次のremakeHeapで使う
プログラミング問題（続き)
(5) 配列ｘがヒープ条件を満たしており、その最後の要素の
インデックスを nとする。そして、 swapNodesによってx[1]
とx[n]の値を入れ替えたとする。そのような配列ｘとnを入
力(引数)とし、 x [1]～x[n-1] までの要素をヒープに作り
直した配列xを返す関数remakeHeapを書け。（やや難）
根とその子はヒープ条件を破っているはず。大きな値を持つ
子の要素と根の要素を入れ替える。入れ替えた要素とその
子もまたヒープ条件が成り立たないことがある。その時は、入
れ替えを繰り返す。こうしてヒープを作り直す。
(6) 以上を組み合わせて、ヒープソートを行う関数(heapSort)
を書け。（普通）
まずmakeHeapした後、swapNodesとremakeHeapを繰り返す。
© Copyright 2024 ExpyDoc
