アルゴリズムとデータ構造 第3章 ヒープ 6月1０日分 アルゴリズムとデータ構造 第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 6 7 4 5 9 8 10 この番号の付け方から、高さ n (> k)のヒープでは、 ★深さ k の最も左の頂点の番号は 2k ★深さ k の最も右の頂点の番号は 2(k+1) - 1

｛ ｛ 配列を用いたヒープの表現 ｛ 二進木による表現 … … 配列による表現 ① ② ③ ⑤ ⑥ ⑦ ④ ⑨ ⑧ 1 根 2 深さ１ 3 　このように、ヒープは「配列」を使って簡単に表せる ① 1 根 根以外は ｛ 2 偶数： 左の子 深さ１ 3 ② ③ ｛ 4 奇数： 右の子 ⑤ ⑥ 深さ2 ⑦ 5 ④ 6 ⑨ 7 ⑧ ｛ 8 深さ3 9 二進木による表現 … … 配列による表現

ヒープへの要素の追加(挿入)手続き 手続き：以下の2ステップで行う (1) 新たな要素を値とする頂点をヒープに追加 　　⇒　条件(i)を満たすところに追加 (2) 次に、ヒープ条件(ii)を満たすように修正(reform)する

ヒープへの要素の追加(1) ヒープの条件(i)を満たすように要素を追加する ことは、 (b)二進木で表す場合、｢可能な頂点を左から順に使う」 (a) 配列で表す場合は分かりやすい 　　⇒　ヒープの最後の要素のインデックスを x とすれば、x+1 番目に要素を追加すれ 　　　　ばよい（最後尾に付け加える）

ヒープへの要素の追加(1) 8 5 7 3 10 例： に3を追加する… それには、ここしかない さらに、 10を追加する。。。 　　　　　　　　　　　　　　に3を追加する… 8 5 7 ① ② ③ それには、ここしかない ⑤ ④ 3 そして、ヒープ条件(ii)を満たしているのでヒープが完成 10 さらに、 10を追加する。。。 ① 　 8 5 7 ② これは、ヒープ条件(ii)を満たしていないので『修正』が必要 ③ 3 ④ ⑤ 10 上の二進木の配列表現

ヒープへの要素の追加(2)「修正」 追加した頂点を v とする ヒープの条件(ii)は、 親頂点の値≧子頂点の値 　　　　親頂点の値≧子頂点の値 　だから、これが満たされていればOK. 　そうでなければ、上の条件を満たすように、頂点を入れ替えていく（修正する）

ヒープへの要素の追加(2)続き 8 5 7 3 10 ヒープへの要素の追加の完成 条件を破っている 条件を破っている 右の二進木 の配列表現 ① ② ③ 5 7 右の二進木 の配列表現 ⑤ ④ 3 条件を破っている 10 ① 8 ② 5 ③ 7 3 ④ ⑤ 10

ヒープを作る具体例 8 入力データ: { 8 5 7 3 10 5 7 9 6 1 20 } ヒープ条件(ii)を破っているので、『修正』が必要 3 10 9 6 1 20 問題:　ヒープ条件(ii)が成り立つようにするには、どのように『修正』したらよいか？

ヒープを作る具体例（配列版) 8 5 { 8 5 7 3 10 7 9 6 1 20 } 3 10 9 6 1 20 入力データ: ① 5 ② { 8 5 7 3 10 7 ③ 9 6 1 20 } 3 ④ 10 ヒープ条件(ii)を破っているので、『修正』が必要 ⑤ 9 ⑥ 6 ⑦ 1 問題:　ヒープ条件(ii)が成り立つようにするには、どのように『修正』したらよいか？ ⑧ 20 ⑨

ヒープの演習 (a) 右の配列は、1～9番目までの要素はヒープの条件を満たす。そこに10番目の要素として15を入れたとすれば、これはヒープの条件を満たしているか？その理由も述べよ。 　(b) 10番目の要素として15ではなく、40が入っているとする。1～10番目までの要素からなる配列は、ヒープの条件を満たしているか？その理由も述べよ。 (c) (a)と(b)で、｢ヒープになっていないもの」に対し、1～10番目までの要素からなる配列をヒープにする（教科書演習3.6）ことを考える。その結果のヒープを示せ。 1 30 2 25 3 28 4 20 5 24 6 26 7 18 8 19 9 11 10 X 11

ヒープの演習(解答) (a) 右の配列は、1～9番目までの要素はヒープの条件を満たす。 1 30 2 25 3 28 4 20 5 24 6 1 30 ということは、ヒープ条件(1)も(2)も満たしている 2 25 3 28 ヒープ条件(1)は、配列で書いた場合に、要素が 順々に入っているということ。 4 20 5 大 24 ヒープ条件(2)は、どの親の値も子どもの値より大きい、ということ。 6 26 7 18 (a) そこに10番目の要素として15を入れたとすれば、これはヒープの条件を満たしているか？ 8 19 配列の要素を順々にいれているのだから、ヒープ 条件(1)は満たしている。条件(2)を調べればよい 9 11 10 X １５ ４０ 小 (b) 10番目の要素として40が入るとする。1～10番目 までの要素からなる配列は、ヒープの条件を満たすか？ 11

ヒープの演習(解答) (a)と(b)で、｢ヒープになっていないもの」に対し、1～10番目までの要素からなる配列をヒープにする（教科書演習3.6）ことを考える。その結果のヒープを示せ。 1 30 2 25 3 28 4 20 5 24 n番目の要素の｢親」は n/2 番目の要素 6 26 2 3 4 5 6 7 8 9 10 1 7 18 8 19 9 11 10 ４０ 11 親と子を比較して必要なら入れ替える

ヒープソート(Heap Sort) ヒープを用いてソート（並び替え）を行う 手続き： (1) x1, x2, …, xn からヒープ(木)を作る 　　　計算量は O(n * log n) 　　　ヒープ木においては根が最大の値の頂点 (2) 根と『最も深い頂点のうち最も右端の頂点』とを交換し、『根だった頂点をヒープから切り離し』てからヒープを作り直す(remake)。この操作一回ごとの計算量は O(log n) (3) (2)を繰り返し、切り離された頂点をすべて並べるとソート完成(新しく切り離された頂点が最小、古いものが最大) 二分探索木によるソートと比較して「最悪の場合」でもこれが保証されているのが特長

ステップ１：ヒープを作る 8 入力データ: { 8 5 7 3 10 5 7 9 6 1 20 } ヒープ条件(ii)を破っているので、『修正』が必要 3 10 9 6 1 20 前出の問題:　ヒープ条件(ii)が成り立つようにするには、どのように『修正』したらよいか？ 答えは次のスライド…

ステップ１：ヒープを作る：結果 20 9 8 10 7 6 5 3 1 どの親子の組み合わせにおいても ヒープ条件(ii)が成り立つ

ヒープソート(第2ステップ （２）根と『最も深い頂点のうち最も右端の頂点』とを交換し、『根だった頂点をヒープから切り離し』てからヒープを作り直す(remake)。 (3) (2)を繰り返し、切り離された頂点をすべて並べるとソート完成(新しく切り離された頂点が最小、古いものが最大) （１）のヒープの修正と紛らわしいので、 ここでは「ヒープの作り直し(remake)」と 呼ぶことにする

ヒープソート(続き) 「根と最後の要素を取り換え、ヒープを作り直す(remake)」の繰り返し(ヒープソートのステップ(2)) 1. 根と『最も深く右側の頂点』とを交換し、根だった頂点を切り離す 20 10 9 ≧ 2. ヒープ条件(ii)を満たすよう、ヒープを作り直す 親頂点と、子頂点のうち大きいほうを交換。 8 5 7 6 ≧ 1 3 問題：　ヒープをどのように作り直すか？ 問題：　この後ヒープをどのように作り直すか？

ヒープソート(配列版) 20 10 9 8 5 7 6 1 3 ≧ ≧ 問題： ヒープをどのように作り直すか？ 「根と最後の要素を取り換え、ヒープを作り直す」の繰り返し(ヒープソートのステップ(2)) 20 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 10 ≧ 9 問題：　ヒープをどのように作り直すか？ 8 1. 根と『最も深く右側の頂点』とを交換し、根だった頂点を切り離す ≧ 5 7 2. ヒープ条件(ii)を満たすよう、ヒープを作り直す 6 1 親頂点と、子頂点のうち大きいほうを交換。 3 問題：　この後ヒープをどのように作り直すか？

ヒープソートの真髄 ヒープを配列で表わす ⇒『木』よりも簡単なデータ構造で実行可能 インデックスによって、根の頂点を簡単に求めることができる 　　⇒『木』よりも簡単なデータ構造で実行可能 インデックスによって、根の頂点を簡単に求めることができる また、注目している頂点のインデックスから、その親や子の頂点が何かが簡単に計算できる 問題：　注目している頂点のインデックスを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 3 4 5 5 6 7 8 8 9 10 30 25 20 16 24 18 12 10 8 15

プログラミング演習 問題１．1～n番目までの要素を持つ配列が与えられているとする。 　これがヒープの条件を満たしているかどうかを判定するアルゴリズムとプログラムを作ろう。 　条件1は当然成り立っているとすると、条件2が成り立っているかどうかが問題。 1 2 3 4 5 5 6 7 8 8 9 10 30 25 20 16 24 18 12 10 8 15

プログラミング演習（問題１続き) 条件2は、どの頂点に対しても次が成り立てばよい。 親頂点の値≧子頂点の値 条件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 # すべての親頂点が子よりも小さくない場合

プログラミング問題 配列を用いてヒープソートするプログラムを作る。以下は、そのための処理を構成するプログラムである。 注意：これらはクラスメソッドを作る のではなく、関数を作る問題 配列を用いてヒープソートするプログラムを作る。以下は、そのための処理を構成するプログラムである。 以下の条件を満たす関数reform_heapを作れ。入力は、配列xとその最後の要素の番号n。ここで、x[1]～x[n-1]まではヒープの条件を満たしているものとする。そして、ヒープの条件を満たす配列ｘを出力する。 （難易度普通） x[n]と、その親の要素の値とを比較し、ヒープ条件が守られていれば終了。さもなくば条件を守るように修正する。 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を繰り返す。