INTRODUCTION TO ALGORITHMS

20.7.7 関根渓 ( 情報知識ネットワーク研究室 B4) INTRODUCTION TO LGORITHMS 6. Heapsort

CONTENTS 6. ヒープ (Heap) 6.2 ヒープ条件の維持 (Maintaining the heap property) 6.3 ヒープの構成 (Building a heap) 6.4 ヒープソート (The heapsort algorithm) 6.5 優先度付きキュー (Priority queues)

CONTENTS 6. ヒープ (Heap) 6.2 ヒープ条件の維持 (Maintaining the heap property) 6.3 ヒープの構成 (Building a heap) 6.4 ヒープソート (The heapsort algorithm) 6.5 優先度付きキュー (Priority queues)

6. ヒープ (Heap) (2 分木 ) ヒープ ((binary)heap) データ構造とは, 下図に示すようなおおよそ完全 2 分木と見なすことができる配列のこと 木の各節点は, その節点の値を格納している配列の要素に対応 6 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 4 5 6 7 8 9 0 6 4 0 8 7 9 3 2 4

6. ヒープ (Heap) 6 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 ヒープを表す配列が持つ 2 つの属性 length[] 配列 の要素数 heap-size[] 配列 に含まれているヒープの要素数 すなわち,[ length[]] には正しい要素が含まれているが,[heap-size[]] を超える要素はどれもヒープの要素ではない ただし,heap-size[] length[] 4 5 6 7 8 9 0 6 4 0 8 7 9 3 2 4

6. ヒープ (Heap) 6 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 木の根は [] であり, 節点の添字 i が与えられたとき, その親 PRENT(i), 左の子 LEFT(i), 右の子 RIGHT(i) は簡単に計算できる PRENT(i) LEFT(i) return i/2 return 2i 4 5 6 7 8 9 0 6 4 0 8 7 9 3 2 4 RIGHT(i) return 2i +

6. ヒープ (Heap) 6 4 0 4 5 6 7 8 7 9 3 8 9 0 2 4 大抵の計算機では LEFT: i の 2 進表現を ビット左にシフトすることで 2i を計算 RIGHT: i の 2 進表現を ビット左にシフトしたあと, 最下位ビットを にすることで 2i+ を計算 PRENT: i の 2 進表現を ビット右にシフトすることで i/2 を計算 4 5 6 7 8 9 0 6 4 0 8 7 9 3 2 4

6. ヒープ (Heap) 4 6 4 0 8 7 9 3 8 9 0 2 4 5 6 4 0 8 7 9 3 2 4 4 5 6 6 7 7 8 9 0 大抵の計算機では LEFT: i の 2 進表現を ビット左にシフトすることで 2i を計算 RIGHT: i の 2 進表現を ビット左にシフトしたあと, 最下位ビットを にすることで 2i+ を計算 PRENT: i の 2 進表現を ビット右にシフトすることで i/2 を計算 ヒープソートのうまい手続きでは, これら 3 つの手続きはしばしば マクロ または インライン 手続きとして実現される

6. ヒープ (Heap) 2 分木ヒープの種類 どちらもヒープ条件 (heap property) を満たす max- ヒープ 根以外の任意の節点 i が [PRENT(i)] [i] を満たす (max- ヒープ条件 (max-heap property)) 最大の要素は根に格納されており, ある接点を根とする部分木にはその節点自身の値以下の値が含まれている min- ヒープ 根以外の任意の接点 i が [PRENT(i)] [i] を満たす (min-ヒープ条件 (min-heap property)) 最小の要素は根に格納される ヒープソートアルゴリズムでは max- ヒープを用いる min ヒープは優先度付きキューでよく用いられる

6. ヒープ (Heap) ヒープにおける節点の高さ 節点の高さは, その節点からある葉に下る最長の単純路に含まれる辺数 ヒープの高さはその根の高さ (n 要素のヒープは完全 2 分木に基づいているので, その高さは Θ(lgn)) 6 4 0 8 7 9 3 8 9 0 2 4 h=3 h=2 h= h=0 ヒープの基本演算は高々木の高さに比例する時間 (O(lgn)) で実行できることを後で証明する

6. ヒープ (Heap) この章の残りの部分では, いくつかの基本的な手続きを紹介し, それらがソーティングアルゴリズムと優先度付きキューの中でどのように使われるかを示す 手続き MX-HEPIFY: Max ヒープ条件を維持するためのキーとなる役割を果たす O(lgn) 時間で動作する 手続き BUILD-MX-HEP: 順序がついていない入力の配列から max- ヒープを構成する線形時間で動作する 手続き HEPSORT: 配列をその場でソートする O(nlgn) 時間で動作する 手続き MX-HEP-INSERT, HEP-EXTRCT-MX, HEP-INCRESE-KEY, HEP-MXIMUM: ヒープデータ構造を優先度付きキューとして用いる時に使用するいずれも O(lgn) 時間で動作する

6. ヒープ (Heap) EXERCISE 6.- 高さ h のヒープの持つ要素数の最大と最小はいくつか. ( 解答 ) 最大 : h n=0 2 n = 2h+ 2 = 2h+ 最小 : h n=0 2 n + = 2(h )+ 2 = 2 h + = 2 h

6. ヒープ (Heap) EXERCISE 6.-2 要素数が n のヒープの高さが lgn となることを示せ. ( 解答 ) 高さを h とすると,6.- より,n 個の要素からなるヒープは 2 h n 2 h+ 2 h n 2 h+ < 2 h+ を満たす. 対数をとると, h logn h + したがって h = logn

6. ヒープ (Heap) EXERCISE 6.-3 max- ヒープの部分木内の最大要素はその部分木の根になることを示せ. ( 解答 ) max- ヒープにおいては節点の値がその親の値以下である max- ヒープ条件が成立するので自明である.

6. ヒープ (Heap) EXERCISE 6.-4 すべての要素が異なるとき, max- ヒープ内の最小の要素はどこに置かれる可能性があるか. ( 解答 ) 最小の要素は子を持ち得ないので, 必ず葉となる.

6. ヒープ (Heap) EXERCISE 6.-5 既ソート配列は min- ヒープか. ( 解答 ) 既ソート配列の先頭の要素は最小値であるから,min- ヒープの根となる. また, 既ソート配列において, ある要素の値は, その後に続く要素の値より必ず大きくなるので, 先頭以外の全ての要素が min- ヒープ条件を満たす. したがって既ソート配列は min- ヒープである.

6. ヒープ (Heap) EXERCISE 6.-6 数列 23,7,4,6,3,0,,5,7,2 は max- ヒープか. ( 解答 ) [4]=6 [RIGHT(4)]=[9]=7>[4] したがって max-ヒープ条件を満たさないため, この数列は max-ヒープではない 23 7 4 6 3 0 8 9 0 5 7 2

6. ヒープ (Heap) EXERCISE 6.-7 要素数が n のヒープが格納されている配列において, 葉の添字は n/2 +, n/2 +2,,n であることを示せ. ( 解答 ) 以下を証明することで示す. ( 葉の数 ) = 節点の数 + ヒープが完全な二分木 節点の数ヒープの最後の要素の親が右の子を持たない 2 のとき : 節点の数がである時, 左図より ( 節点の数 )= ( 葉の数 )=2 となり, 仮定が成り立つ

6. ヒープ (Heap) EXERCISE 節点の数が k 個のとき仮定が成り立つとすると, 葉の数は k+ である. さらに葉を 2 個追加して, ヒープを再び完全な二分木とすると, 下図より葉が節点となり, その子として葉が 2 個増えることになるので, ( 節点の個数 )= k+ ( 葉の個数 ) = (k+)+ となって仮定が成り立つ.

6. ヒープ (Heap) EXERCISE 2のとき : 節点の数がである時, 右図より ( 節点の数 )= ( 葉の数 )= となり, 仮定が成り立つ 2 節点の数が k 個のとき仮定が成り立つとすると, 葉の数は k である. さらに葉を 2 個追加すると, 図 ( 次ページ ) より葉が節点となり, さらに葉が 2 個増えるので ( 節点と葉が 個ずつ増える ), ( 節点の個数 )= k+ ( 葉の個数 ) = k+ となって仮定が成り立つ. よって,2 より仮定が成り立つことが示され, これは暗に葉の添字が n/2 +, n/2 +2,,n であることを示している.

6. ヒープ (Heap) EXERCISE

CONTENTS 6. ヒープ (Heap) 6.2 ヒープ条件の維持 (Maintaining the heap property) 6.3 ヒープの構成 (Building a heap) 6.4 ヒープソート (The heapsort algorithm) 6.5 優先度付きキュー (Priority queues)

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY 入力は配列 と配列の添字 i 添字 i を根とする部分木が max- ヒープになるように [i] の値を max- ヒープの中に 滑り落とす この手続きが呼ばれるとき,LEFT(i) と RIGHT(i) を根とする二分木が max-ヒープであることを仮定する アルゴリズム MX-HEPIFY(,i) l LEFT(i) 2 r RIGHT(i) 3 if l heap-size[] かつ [l]>[i] 4 then largest l 5 else largest i 6 if r heap-size[] かつ [r] > [largest] 7 then largest r 8 if largest i 9 then exchange [i] [largest] 0 MX-HEPIFY(,largest) Line -2 節点 i の左の子のインデックスを l に, 右の子のインデックスを r に代入

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY 入力は配列 と配列の添字 i 添字 i を根とする部分木が max- ヒープになるように [i] の値を max- ヒープの中に 滑り落とす この手続きが呼ばれるとき,LEFT(i) と RIGHT(i) を根とする二分木 Line 3-5 if 文が max-ヒープであることを仮定する アルゴリズム MX-HEPIFY(,i) l LEFT(i) 2 r RIGHT(i) 3 if l heap-size[] かつ [l]>[i] 4 then largest l 5 else largest i 6 if r heap-size[] かつ [r] > [largest] 7 then largest r 8 if largest i 9 then exchange [i] [largest] 0 MX-HEPIFY(,largest) 節点 i が左の子を持ち, かつ節点 i の値より左の子の値のほうが大きければ, largest に左の子のインデックスを代入するそうでなければ largest に i を代入

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY 入力は配列 と配列の添字 i 添字 iを根とする部分木が max-ヒープになるように [i] の値をmax- ヒープの中に 滑り落とす この手続きが呼ばれるとき節点,LEFT(i) iが右の子を持ちと RIGHT(i), を根とする二分木が max-ヒープであることを仮定する アルゴリズム MX-HEPIFY(,i) l LEFT(i) 2 r RIGHT(i) 3 if l heap-size[] かつ [l]>[i] 4 then largest l 5 else largest i 6 if r heap-size[] かつ [r] > [largest] 7 then largest r 8 if largest i 9 then exchange [i] [largest] 0 MX-HEPIFY(,largest) Line 6-7 if 文 かつインデックスがlargestである節点の値より右の子の値のほうが大きければ, largestに右の子のインデックスを代入する

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY 入力は配列 と配列の添字 i 添字 iを根とする部分木が max-ヒープになるように [i] の値をmax- ヒープの中に 滑り落とす Line 8-0 if 文 この手続きが呼ばれるとき点でなければ,LEFT(i) と, RIGHT(i) を根とする二分木が max-ヒープであることを仮定する アルゴリズム MX-HEPIFY(,i) l LEFT(i) 2 r RIGHT(i) 3 if l heap-size[] かつ [l]>[i] 4 then largest l 5 else largest i 6 if r heap-size[] かつ [r] > [largest] 7 then largest r 8 if largest i 9 then exchange [i] [largest] 0 MX-HEPIFY(,largest) 節点 i が最大値 ( 右の子, 左の子の値と比べたとき ) を持つ節 [i] と [largest] を交換し, 今度は[largest] に対してMX-HEPIFYを実行する

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY ( MX-HEPIFY(,2) の動作 ) 6 4 0 heap-size[]=0 4 7 9 3 8 9 0 2 8

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY ( MX-HEPIFY(,2) の動作 ) [2]=4 [LEFT(2)]=[4]=4 [RIGHT(2)]=[5]=4 最大値は [4]=4 i 6 4 0 heap-size[]=0 4 7 9 3 8 9 0 2 8

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY ( MX-HEPIFY(,2) の動作 ) [2]=4 [LEFT(2)]=[4]=4 [RIGHT(2)]=[5]=4 最大値は [4]=4 [2] と [4] を交換 次は i=4 として MX-HEPIFY を実行 heap-size[]=0 6 4 0 i 4 7 9 3 8 9 0 2 8

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY ( MX-HEPIFY(,2) の動作 ) [4]=4 [LEFT(4)]=[8]=2 [RIGHT(4)]=[9]=8 最大値は [9]=8 6 4 0 heap-size[]=0 i 4 7 9 3 8 9 0 2 8

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY ( MX-HEPIFY(,2) の動作 ) [4]=4 [LEFT(4)]=[8]=2 [RIGHT(4)]=[9]=8 最大値は [9]=8 [4] と [9] を交換 次は i=9 として MX-HEPIFY を実行 heap-size[]=0 6 4 0 8 7 9 3 8 9 0 2 i 4

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY ( MX-HEPIFY(,2) の動作 ) [9]=4 LEFT(9)=8>heap-size[] RIGHT(9)=9>heap-size[] したがって処理が終了 6 4 0 heap-size[]=0 8 7 9 3 8 9 0 2 i 4

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY ( MX-HEPIFY(,2) の動作 ) [9]=4 LEFT(9)=8>heap-size[] RIGHT(9)=9>heap-size[] したがって処理が終了 6 4 0 heap-size[]=0 8 7 9 3 8 9 0 2 4 確かに添字 i=2 を根とする部分木が max- ヒープになっている

6.2 ヒープ条件の維持 (Maintaining the heap property) 手続き MX-HEPIFY 実行時間の吟味 ] MX-HEPIFY の実行時間は, [i],[left(i)],[right(i)] の間の関係を比較するための Θ() 時間と, 節点 i のどちらかの子を根とする部分木に対する MX-HEPIFY の実行時間との合計である i どちらの子の部分木のサイズも高々 2n/3 ( 左図のように木の最下行が半分だけ埋まっている場合 ) だから,MX-HEPIFY の実行時間は漸化式 T(n) T(2n/3) + Θ() で表現できる したがって,T(n) = O(lgn) である 高さ h の節点に対する MX-HEPIFY の実行時間は O(h) であると言える

6.2 ヒープ条件の維持 (Maintaining the heap property) EXERCISE 6.2- 図 6.2 を参考にして, 配列 = 27,7,3,6,3,0,,5,7,2,4,8,9,0 に対する MX- HEPIFY の動作を示せ. ( 解答 ) 希望があればホワイトボードで

6.2 ヒープ条件の維持 (Maintaining the heap property) EXERCISE 6.2-2 手続き MX-HEPIFY を利用して,min- ヒープ上で MX-HEPIFY に対応する操作を実現する手続き MX-HEPIFY の擬似コードを書け. MX-HEPIFY の実行時間を MX-HEPIFY と比較せよ ( 解答 ) MIN-HEPIFY(,i) l LEFT(i) 2 r RIGHT(i) 3 if l heap-size[] ND [l] < [i] 4 then smallest l 5 else smallest i 6 if r heap-size[] ND [r] < [largest] 7 then smallest r 8 if largest i 9 then exchange [i] [smallest] 0 MIN-HEPIFY(,smallest) 実行に要する時間は MX-HEPIFY と変わらない

6.2 ヒープ条件の維持 (Maintaining the heap property) EXERCISE 6.2-3 要素 [i] が両方の子より大きいとき,MX-HEPIFY(,i) の呼び出しはどのような効果があるか. ( 解答 ) 何も行われずに終了する CIRQUE05 は MX-HEPIFY(,) を呼び出した! しかし なにもおこらなかった!

6.2 ヒープ条件の維持 (Maintaining the heap property) EXERCISE 6.2-4 i > heap-size[]/2 のとき,MX-HEPIFY(,) の呼び出しはどのような効果があるか. ( 解答 ) 6.-7 より, 添字が i > heap-size[]/2 となるものは全て葉であるため何も起きない. CIRQUE05 は MX-HEPIFY(,) を呼び出した! しかし なに m(ry

6.2 ヒープ条件の維持 (Maintaining the heap property) EXERCISE 6.2-5 MX-HEPIFY のコードは,Line0 の再帰呼び出しを除けばかなり小さい定数係数を持つ. しかし, あるコンパイラは再帰呼び出しを効率の悪いコードに変換するかもしれない. 再帰の代わりに繰り返し構造子 ( ループ ) を用いて効率のよい MX-HEPIFY を書け ( 解答 ) MX-HEPIFY(,i) while ( 条件式 ) 2 do l LEFT(i) 3 r RIGHT(i) 4 if l heap-size[] ND [l]>[i] 5 then largest l 6 if r heap-size[] ND [r] > [largest] 7 then largest r 8 if largest i 9 then exchange [i] [largest] 0 i largest ( 条件式 )=NOT(([i] が右の子, 左の子両方を持ち, その両方より大きい )OR([i] がどちらか片方の子のみを持ち, それより大きい )OR([i] は葉ではない ))

6.2 ヒープ条件の維持 (Maintaining the heap property) EXERCISE 6.2-6 サイズ n のヒープに対する MX-HEPIFY の最悪実行時間が Ω(lgn) となることを示せ.( ヒント : n 点からなるヒープに対して, 根から葉に下る路上の全ての節点で MX-HEPIFY が再帰的に呼び出されるように節点の値を定めよ.) ( 解答 ) 最悪のケースの場合, 根から葉に至るまで, 全ての節点で MX-HEPIFY が呼び出されるので, 木の高さが h のとき,Θ() が h 回呼び出されるので最悪実行時間は Θ(h) となる. 6.-2 から n 個の節点を持つヒープの高さは lgn であるから, したがって Θ(h) = Θ(lgn) である. 漸近的上界, 外界が一致しているため, 最悪実行時間は Ω(lgn) とも言える.

CONTENTS 6. ヒープ (Heap) 6.2 ヒープ条件の維持 (Maintaining the heap property) 6.3 ヒープの構成 (Building a heap) 6.4 ヒープソート (The heapsort algorithm) 6.5 優先度付きキュー (Priority queues)

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP n=length[] とすると,Exercise 6.-7 より部分配列 [( n/2 +) n] の要素は全て葉 ( つまり最小の max- ヒープ ) 木のそれぞれの節点において, 後ろから順に MX-HEPIFY を繰り返し実行すれば, max- ヒープを構成できる アルゴリズム BUILD-MX-HEP() heap-size[] length[] 2 for i length[]/2 downto 3 do MX-HEPIFY(,i) Line 2-3 for ループヒープの節点全てに 後ろから順に MX-HEPIFY を実行する

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP heap-size[] length[](=0) length[]/2 =5 for ループは i=5 からスタート 4 3 2 6 9 0 8 9 0 4 8 7 8 9 0 4 3 2 6 9 0 4 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=5 4 3 2 i 6 9 0 8 9 0 4 8 7 8 9 0 4 3 2 6 9 0 4 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=5 MX-HEPIFY(,5) を実行交換はしない [5] を根とする部分 max- ヒープを構成 4 4 2 i 8 9 0 8 7 6 9 3 0 8 9 0 4 3 2 6 9 0 4 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=4 4 3 i 2 6 9 0 8 9 0 4 8 7 8 9 0 4 3 2 6 9 0 4 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=4 MX-HEPIFY(,4) を実行 4 3 2 6 9 0 8 9 0 4 8 7 8 9 0 4 3 2 6 9 0 4 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=4 MX-HEPIFY(,4) を実行 [4] と [8] を交換 [4] を根とする部分 max- ヒープを構成 4 6 9 0 8 9 0 2 4 8 7 3 8 9 0 4 3 4 6 9 0 2 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=3 4 i 3 4 6 9 0 8 9 0 2 8 7 8 9 0 4 3 4 6 9 0 2 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=3 MX-HEPIFY(,3) を実行 4 3 4 6 9 0 8 9 0 2 8 7 8 9 0 4 3 4 6 9 0 2 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=3 MX-HEPIFY(,3) を実行 [3] と [7] を交換 [3] を根とする部分 max ヒープを構成 4 0 4 6 9 3 8 9 0 2 8 7 8 9 0 4 0 4 6 9 3 2 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=2 i 4 0 4 6 9 3 8 9 0 2 8 7 8 9 0 4 0 4 6 9 3 2 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=2 MX-HEPIFY(,2) を実行 4 0 4 6 9 3 8 9 0 2 8 7 8 9 0 4 0 4 6 9 3 2 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=2 MX-HEPIFY(,2) を実行 [2] と [5] を交換 4 6 0 4 9 3 8 9 0 2 8 7 8 9 0 4 6 0 4 9 3 2 8 7

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i=2 MX-HEPIFY(,2) を実行 [5] と [0] を交換 [2] を根とする部分 max ヒープを構成 6 4 8 9 0 2 4 8 7 0 9 3 8 9 0 4 6 0 4 7 9 3 2 8

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i= i 4 6 0 4 7 9 3 8 9 0 2 8 8 9 0 4 6 0 4 7 9 3 2 8

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i= MX-HEPIFY(,) を実行 4 6 0 4 7 9 3 8 9 0 2 8 8 9 0 4 6 0 4 7 9 3 2 8

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i= MX-HEPIFY(,) を実行 [] と [2] を交換 6 4 0 4 7 9 3 8 9 0 2 8 8 9 0 6 4 0 4 7 9 3 2 8

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i= MX-HEPIFY(,) を実行 [2] と [4] を交換 6 4 0 4 7 9 3 8 9 0 2 8 8 9 0 6 4 0 4 7 9 3 2 8

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP i= MX-HEPIFY(,) を実行 [4] と [9] を交換 [] を根とする部分 max- ヒープ, 目的の max ヒープが構成された 6 4 0 8 7 9 3 8 9 0 2 4 8 9 0 6 4 0 8 7 9 3 2 4

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP [] を根とする部分 max- ヒープ, 目的の max ヒープが構成された 6 4 0 8 7 9 3 8 9 0 2 4 8 9 0 6 4 0 8 7 9 3 2 4

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP アルゴリズムの正当性次のループ不変式を利用して BUID-MX-HEP の正当性を示す Line 2-3 の for ループの各繰り返しが開始される時点では, 各節点 i+,i+2,,n はある max- ヒープの根である 初期条件 : ループの最初の繰り返しでは,i= n/2 である 各節点 n/2 +, n/2 +2,.,n は葉であり, したがって自明な max- ヒープの根である ループ内条件 : ループの各繰り返しが不変式を維持することを示すために, 節点 i の子は i より大きい番号を持つことに注意する ループ不変式が成り立つとすると, 節点 i の子はいずれも max- ヒープの根となる これは,MX-HEPIFY(,i) が節点 i を max- ヒープの根に修正する時に必要とする条件そのものである さらに, この MX-HEPIFY の呼び出しは節点 i+,i+2,,n が max- ヒープの根であるという性質を保存する

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP アルゴリズムの正当性 i を 減らした時に,for ループのつぎの繰り返しに対するループ不変式が再び成立する これでループの不変式の正当性が示された 終了条件 : 手続きは i=0 で終了する ループ不変式から, 各節点,2,,n が部分 max- ヒープの根である 特に, 節点 は max- ヒープ全体の根であるため, 配列から max- ヒープが正しく構成されたことになる

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP 実行時間の吟味 MX-HEPIFY の各呼び出しに O(lgn) 時間かかり, 呼び出しは O(n) 回起こるので,BUILD-MX-HEP の実行時間は高々 O(nlgn) である しかし, ある節点における MX-HEPIFY の実行時間はその節点の高さに依存すること, そしてほとんどの節点の高さは小さいことに注意すると, よりタイトな上界が導出可能 Exercise 6.-2 より n 個の要素を持つヒープの高さは lgn であり, 高さ h の節点は高々 n/2 h+ 個しかない (Exercise 6.3-3) ことを用いて解析する

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP 実行時間の吟味 MX-HEPIFY が高さ h の節点で呼ばれたときに要する時間は, 前節より O(h) であるしたがって,BUILD-MX-HEP の全コストは上から lgn h=0 n 2 h+ O h = O n lgn h=0 h 2 n で抑えられるここで等比無限級数の収束の公式 ( ホワイトボードにて説明 ) を用いると, 右辺の和は h 2 h h=0 = /2 2 2 = 2 と計算できるので,BUILD-MX-HEP の実行時間の上界は

6.3 ヒープの構成 (Building a heap) 手続き BUILD-MX-HEP 実行時間の吟味 O n lgn h=0 h 2 n = O n h=0 h 2 n = O(n) となる したがって, 未ソートの配列から max- ヒープを線形時間で構成できるということがわかった

CONTENTS 6. ヒープ (Heap) 6.2 ヒープ条件の維持 (Maintaining the heap property) 6.3 ヒープの構成 (Building a heap) 6.4 ヒープソート (The heapsort algorithm) 6.5 優先度付きキュー (Priority queues)

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT BUILD-MX-HEP を用いて入力配列 [..n] 中に max- ヒープを構成する 配列の最大要素は構成された max- ヒープの根, つまり [] に格納されているので,[] を [n] と交換することで, 最大要素を配列の正しい位置に配置できる ここで (heap-size[] を 減らすことによって ) 節点 n をヒープから 取り除く と,[] の子はどちらも max- ヒープの根となっているから,MX-HEPIFY(,) を 回呼び出せば残りの配列は容易に max- ヒープとなる これを繰り返すことで配列を正しくソートすることができる アルゴリズム HEPSORT() BUILD-MX-HEP() 2 for i length[] downto 2 3 do exchange [] [i] 4 heap-size[] heap-size[]- 5 MX-HEPIFY(,) Line 入力配列を BUILD-MX-HEP によって max- ヒープにする

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT BUILD-MX-HEP を用いて入力配列 [..n] 中に max- ヒープを構成する 配列の最大要素は構成された max- ヒープの根, つまり [] に格納されているので,[] を [n] と交換することで, 最大要素を配列の正しい位置に配置できる ここで (heap-size[] を 減らすことによって ) 節点 n をヒープから 取り除く と,[] の子はどちらも max- ヒープの根となっているから,MX-HEPIFY(,) を 回呼び出せば残りの配列は容易に max- ヒープとなる これを繰り返すことで配列を正しくソートすることができる アルゴリズム HEPSORT() BUILD-MX-HEP() 2 for i length[] downto 2 3 do exchange [] [i] 4 heap-size[] heap-size[]- 5 MX-HEPIFY(,) Line 2-5 for ループ配列の後ろから 2 つ目まで繰り返す max- ヒープの根の要素を i 番目の要素を交換し,heap-size[] を 減らすことでヒープから取り除く その後, ヒープが max- ヒープとなるように MX-HEPIFY を 回呼び出して [] を適正位置に滑り落とす

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT BUILD-MX-HEP によって構成された直後の max- ヒープデータ構造 6 4 0 8 7 9 3 8 9 0 2 4 8 9 0 6 4 0 8 7 9 3 2 4

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=0 heap-size[]=0 [] と [0] を交換する 6 4 0 8 7 9 3 8 9 0 2 4 8 9 0 6 4 0 8 7 9 3 2 4

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=0 heap-size[]=0 [] と [0] を交換する 4 0 8 7 9 3 8 9 0 2 4 6 8 9 0 4 0 8 7 9 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=0 heap-size[]=0-=9 [0] をヒープから取り除く 4 0 8 7 9 3 8 9 0 2 4 6 8 9 0 4 0 8 7 9 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=0 heap-size[]=9 MX-HEPIFY(,) を実行 4 0 8 7 9 3 8 9 0 2 4 6 8 9 0 4 0 8 7 9 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=0 heap-size[]=9 MX-HEPIFY(,) を実行 [] と [2] を交換 4 0 8 7 9 3 8 9 0 2 4 6 8 9 0 4 0 8 7 9 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=0 heap-size[]=9 MX-HEPIFY(,) を実行 [2] と [4] を交換 4 8 0 7 9 3 8 9 0 2 4 6 8 9 0 4 8 0 7 9 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=0 heap-size[]=9 MX-HEPIFY(,) を実行 [4] と [9] を交換 4 8 0 4 7 9 3 8 9 0 2 6 8 9 0 4 8 0 4 7 9 3 2 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=0 heap-size[]=9 再び max- ヒープが構成された 4 8 0 4 7 9 3 8 9 0 2 6 8 9 0 4 8 0 4 7 9 3 2 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=9 heap-size[]=9 [] と [9] を交換する 4 8 0 4 7 9 3 8 9 0 2 6 8 9 0 4 8 0 4 7 9 3 2 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=9 heap-size[]=9 [] と [9] を交換する 8 0 4 7 9 3 8 9 0 2 4 6 8 9 0 8 0 4 7 9 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=9 heap-size[]=9-=8 [9] をヒープから取り除く 8 0 4 7 9 3 8 9 0 2 4 6 8 9 0 8 0 4 7 9 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=9 heap-size[]=8 MX-HEPIFY(,) を実行 8 0 4 7 9 3 8 9 0 2 4 6 8 9 0 8 0 4 7 9 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=9 heap-size[]=8 MX-HEPIFY(,) を実行 [] と [3] を交換 0 8 4 7 9 3 8 9 0 2 4 6 8 9 0 0 8 4 7 9 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=9 heap-size[]=8 MX-HEPIFY(,) を実行 [3] と [6] を交換 0 8 9 4 7 3 8 9 0 2 4 6 8 9 0 0 8 9 4 7 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=9 heap-size[]=8 再び max- ヒープが構成された 0 8 9 4 7 3 8 9 0 2 4 6 8 9 0 0 8 9 4 7 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=8 heap-size[]=8 [] と [8] を交換 0 8 9 4 7 3 8 9 0 2 4 6 8 9 0 0 8 9 4 7 3 2 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=8 heap-size[]=8 [] と [8] を交換 2 8 9 4 7 3 8 9 0 0 4 6 8 9 0 2 8 9 4 7 3 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=8 heap-size[]=8-=7 [8] をヒープから取り除く 2 8 9 4 7 3 8 9 0 0 4 6 8 9 0 2 8 9 4 7 3 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=8 heap-size[]=7 MX=HEPIFY(,) を実行 2 8 9 4 7 3 8 9 0 0 4 6 8 9 0 2 8 9 4 7 3 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=8 heap-size[]=7 MX=HEPIFY(,) を実行 [] と [3] を交換 9 8 2 4 7 3 8 9 0 0 4 6 8 9 0 9 8 2 4 7 3 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=8 heap-size[]=7 MX=HEPIFY(,) を実行 [3] と [7] を交換 9 8 3 4 7 2 8 9 0 0 4 6 8 9 0 9 8 3 4 7 2 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=8 heap-size[]=7 再び max- ヒープが構成された 9 8 3 4 7 2 8 9 0 0 4 6 8 9 0 9 8 3 4 7 2 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=7 heap-size[]=7 [] と [7] を交換 9 8 3 4 7 2 8 9 0 0 4 6 8 9 0 9 8 3 4 7 2 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=7 heap-size[]=7 [] と [7] を交換 2 8 3 4 7 9 8 9 0 0 4 6 8 9 0 2 8 3 4 7 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=7 heap-size[]=7-=6 [7] をヒープから取り除く 2 8 3 4 7 9 8 9 0 0 4 6 8 9 0 2 8 3 4 7 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=7 heap-size[]=6 MX-HEPIFY(,) を実行 2 8 3 4 7 9 8 9 0 0 4 6 8 9 0 2 8 3 4 7 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=7 heap-size[]=6 MX-HEPIFY(,) を実行 [] と [2] を交換 8 2 3 4 7 9 8 9 0 0 4 6 8 9 0 8 4 7 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=7 heap-size[]=6 MX-HEPIFY(,) を実行 [2] と [5] を交換 8 7 3 4 2 9 8 9 0 0 4 6 8 9 0 8 7 3 4 2 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=7 heap-size[]=6 再び max- ヒープが構成された 8 7 3 4 2 9 8 9 0 0 4 6 8 9 0 8 7 3 4 2 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=6 heap-size[]=6 [] と [6] を交換 8 7 3 4 2 9 8 9 0 0 4 6 8 9 0 8 7 3 4 2 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=6 heap-size[]=6 [] と [6] を交換 7 3 4 2 8 9 8 9 0 0 4 6 8 9 0 7 3 4 2 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=6 heap-size[]=6-=5 [6] をヒープから取り除く 7 3 4 2 8 9 8 9 0 0 4 6 8 9 0 7 3 4 2 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=6 heap-size[]=5 MX-HEPIFY(,) を実行する 7 3 4 2 8 9 8 9 0 0 4 6 8 9 0 7 3 4 2 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=6 heap-size[]=5 MX-HEPIFY(,) を実行する [] と [2] を交換 7 3 4 2 8 9 8 9 0 0 4 6 8 9 0 7 3 4 2 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=6 heap-size[]=5 MX-HEPIFY(,) を実行する [2] と [4] を交換 7 4 3 2 8 9 8 9 0 0 4 6 8 9 0 7 4 3 2 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=6 heap-size[]=5 再び max- ヒープが構成された 7 4 3 2 8 9 8 9 0 0 4 6 8 9 0 7 4 3 2 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=5 heap-size[]=5 [5] と [] を交換 7 4 3 2 8 9 8 9 0 0 4 6 8 9 0 7 4 3 2 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=5 heap-size[]=5 [5] と [] を交換 2 4 3 7 8 9 8 9 0 0 4 6 8 9 0 2 4 3 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=5 heap-size[]=5-=4 [5] をヒープから取り除く 2 4 3 7 8 9 8 9 0 0 4 6 8 9 0 2 4 3 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=5 heap-size[]=4 MX-HEPIFY(,) を実行 2 4 3 7 8 9 8 9 0 0 4 6 8 9 0 2 4 3 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=5 heap-size[]=4 MX-HEPIFY(,) を実行 [] と [2] を交換 4 2 3 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=5 heap-size[]=4 再び max- ヒープが構成された 4 2 3 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=4 heap-size[]=4 [] と [4] を交換 4 2 3 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=4 heap-size[]=4 [] と [4] を交換 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=4 heap-size[]=4-=3 [4] をヒープから取り除く 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=4 heap-size[]=3 MX-HEPIFY(,) を実行する 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=4 heap-size[]=3 MX-HEPIFY(,) を実行する [] と [3] を交換する 3 2 4 7 8 9 8 9 0 0 4 6 8 9 0 3 2 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=4 heap-size[]=3 再び max- ヒープが構成された 3 2 4 7 8 9 8 9 0 0 4 6 8 9 0 3 2 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=3 heap-size[]=3 [] と [3] を交換 3 2 4 7 8 9 8 9 0 0 4 6 8 9 0 3 2 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=3 heap-size[]=3 [] と [3] を交換 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=3 heap-size[]=3-=2 [3] をヒープから取り除く 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=3 heap-size[]=2 MX-HEPIFY(,) を実行する 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=3 heap-size[]=2 MX-HEPIFY(,) を実行する [] と [2] を交換 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 2 3 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=3 heap-size[]=2 再び max- ヒープが構成された 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 2 3 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=2 heap-size[]=2 [] と [2] を交換 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 2 3 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=2 heap-size[]=2 [] と [2] を交換 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=2 heap-size[]=2-= [2] をヒープから取り除く 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=2 heap-size[]= MX=HEPIFY(,) を実行する 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i=2 heap-size[]= 再び max- ヒープが構成された 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT length[]=0 i= heap-size[]= ループ終了 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT 以上で配列が正しくソートされた 2 3 4 7 8 9 8 9 0 0 4 6 8 9 0 4 7 8 9 0 4 6

6.4 ヒープソート (The heapsort algorithm) 手続き HEPSORT 計算時間の吟味 Line n=length[] とすると BUILD-MX-HEP の呼び出しに O(n) かかる HEPSORT() BUILD-MX-HEP() 2 for i length[] downto 2 3 do exchange [] [i] 4 heap-size[] heap-size[]- 5 MX-HEPIFY(,) Line 2-3 for ループ MX-HEPIFY が n- 回呼び出される MX-HEIFY の 回の呼び出しに O(lgn) かかるので, 全体で O(nlgn) かかる したがって, 手続き HEPSORT 全体では O(nlgn) 時間を要する

6.4 ヒープソート (The heapsort algorithm) EXERCISE 6.4- 図 6.4 を参考にして, 配列 = 5,3,2,25,7,7,20,8,4 に対する HEPSORT の動作を示せ. ( 解答 ) 希望があればホワイトボードで

6.4 ヒープソート (The heapsort algorithm) EXERCISE 6.4-2 つぎのループ不変式を用いて,HEPSORT の正当性を論ぜよ : Line 2-5 の for ループの各繰り返しの直前では以下が成立する. 部分配列 [..i] は [..n] の大きい方から i 個の要素を含む max- ヒープである. また, 部分配列 [i+..n] は [..n] の大きい方から n-i 個の要素をソートされた順序で含む. ( 解答 ) 初期条件 : ループの最初の繰り返しの直前では i=n である. 部分配列 [ i] は配列 そのものであり, 直前の BUILD-MX-HEP の手続きによって max- ヒープになっている. ループ内条件 : [] と [i] を交換し,heap-size[] を 減少させたとき,[i], つまり max- ヒープの根であった節点はヒープから取り除かれ,[] がヒープの新しい根となる. このとき,[] 以外の節点は全て max- ヒープの根となっているため, MX-HEPIFY(,) を 回呼び出すだけで max- ヒープを再構成できる. すなわち, 部分配列 [ i] は [ n] の小さいほうから i 個の要素を含む max- ヒープとなっている

CONTENTS 6. ヒープ (Heap) 6.2 ヒープ条件の維持 (Maintaining the heap property) 6.3 ヒープの構成 (Building a heap) 6.4 ヒープソート (The heapsort algorithm) 6.5 優先度付きキュー (Priority queues)

6.5 優先度付きキュー (Priority queues) 優先度付きキュー (priority queue) 要素の集合 S を保持するためのデータ構造 各要素はキー (key) と呼ばれる値を持つ 優先度付き max-キューと優先度付き min-キューの2 種類がある 優先度付き max- キュー (max-priority-queue) の操作 INSERT(S,x): 集合 S に要素 x を挿入する MXIMUM(S): 最大のキーを持つ S の要素を返す EXTRCT-MX(S): 最大のキーを持つ S の要素を S から削除してその値を返す INCRESE-KEY(S,x,k): 要素 x のキーの値を新しいキー値 kに変更するただし,k は x の現在のキー以上と仮定する

6.5 優先度付きキュー (Priority queues) 優先度付き max- キューの応用 共用計算機上でのジョブのスケジュール 優先度付き max- キューは実行待ちジョブとそれらの相対的な優先度を保持していて, ジョブが終了または割り込みがかかった時に, 一時中断しているジョブの中から EXTRCT-MX を用いて新しいジョブを選ぶ 新しいジョブは INSERT を用いていつでもキューに挿入できる 集合 S の優先度付き max- キュー 6 4 0 所持する値が大きいほど優先度が高いジョブ 8 7 9 3 8 9 0 2 4

6.5 優先度付きキュー (Priority queues) 優先度付き min- キュー INSERT, MINIMUM, EXTRCT-MIN, DECRESE-KEY 操作が可能 事象駆動シミュレータで利用される キューに格納される要素はシミュレートされる事象であり, 対応する生起時刻がそのキーとなる各ステップでは,EXTRCT-MIN を用いて次にシミュレートする事象を選択する新しい事象が発生したとき INSERT を用いて優先度付き min- キューに挿入される 集合 S の優先度付き min- キュー 3 7 9 所持する値 ( 生起時刻 ) が小さいほど先にシミュレートされる 8 0 4

6.5 優先度付きキュー (Priority queues) ハンドル (handle) ジョブのスケジューリングや事象駆動型のシミュレーションのような応用では, その応用に現れるオブジェクトが優先度付きキューに格納される要素である. このとき, 応用のどのオブジェクトが優先度付きキューのどの要素に対応するか, あるいはその逆を決定する必要がしばしば生じる. そこで, ヒープを優先度付きキューの実現に用いるとき, ヒープの各要素の中に対応するオブジェクトへのハンドル (handle) を格納しておく必要がしばしば生じる. ハンドルの正確な構造 ( たとえば, ポインタ, 整数など ) は応用に依存する. ( 例 : 配列の添字 )

6.5 優先度付きキュー (Priority queues) 手続き HEP-MXIMUM MXIMUM を O() 時間で実現する アルゴリズム HEP-MXIMUM() return [] max- ヒープの場合, 集合の最大値が根に格納されているため, 単純に [] を出力するだけでよい

6.5 優先度付きキュー (Priority queues) 手続き HEP-EXTRCT-MX EXTRCT-MX を実現する 手続き HEPSORT の for ループ本体 ( 第 3-5 行 ) に類似している アルゴリズム HEP-EXTRCT-MX() if heap-size[] < 2 then error heap underflow 3 max [] 4 [] [heap-size[]] 5 heap-size[] heap-size[] 6 MX-HEPIFY(,) 7 return max Line -2 if 文 heap-size[] が 未満であれば, エラーメッセージを出力

6.5 優先度付きキュー (Priority queues) 手続き HEP-EXTRCT-MX EXTRCT-MX を実現する 手続き HEPSORT の for ループ本体 ( 第 3-5 行 ) に類似している アルゴリズム HEP-EXTRCT-MX() if heap-size[] < 2 then error heap underflow 3 max [] 4 [] [heap-size[]] 5 heap-size[] heap-size[] 6 MX-HEPIFY(,) 7 return max Line 3-5 最大値 [] を max に代入, さらに [] にヒープの最後尾の要素を代入し,heap-size[] を 減少させて最大値をヒープから取り除く

6.5 優先度付きキュー (Priority queues) 手続き HEP-EXTRCT-MX EXTRCT-MX を実現する 手続き HEPSORT の for ループ本体 ( 第 3-5 行 ) に類似している アルゴリズム HEP-EXTRCT-MX() if heap-size[] < 2 then error heap underflow 3 max [] 4 [] [heap-size[]] 5 heap-size[] heap-size[] 6 MX-HEPIFY(,) 7 return max Line 6 残されたヒープが max- ヒープ条件を満たすようにする

6.5 優先度付きキュー (Priority queues) 手続き HEP-EXTRCT-MX EXTRCT-MX を実現する 手続き HEPSORT の for ループ本体 ( 第 3-5 行 ) に類似している アルゴリズム HEP-EXTRCT-MX() if heap-size[] < 2 then error heap underflow 3 max [] 4 [] [heap-size[]] 5 heap-size[] heap-size[] 6 MX-HEPIFY(,) 7 return max Line 7 ヒープの最大値 max を返す

6.5 優先度付きキュー (Priority queues) 手続き HEP-EXTRCT-MX EXTRCT-MX を実現する 手続き HEPSORT の for ループ本体 ( 第 3-5 行 ) に類似している アルゴリズム HEP-EXTRCT-MX() if heap-size[] < 2 then error heap underflow 3 max [] 4 [] [heap-size[]] 5 heap-size[] heap-size[] 6 MX-HEPIFY(,) 7 return max MX-HEPIFY の呼び出し (O(lgn)) 以外では定数時間しかかからないので, HEP-EXTRCT-MX の実行時間は O(lgn) である

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY INCRESE-KEY を実現する キー値を増やす優先度付きキューの要素配列の添字 i で表す アルゴリズム HEP-INCRESE-KEY(,i,key) if key < [i] 2 then error new key is smaller than current key 3 [i] key 4 while i > ND [PRENT(i)] < [i] 5 do exchange [i] [PRENT(i)] 6 i PRENT(i) Line -2 if 文入力されたキー値が, 増やす対象となるキー値より小さければエラーメッセージを出力

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY INCRESE-KEY を実現する キー値を増やす優先度付きキューの要素配列の添字 i で表す アルゴリズム HEP-INCRESE-KEY(,i,key) if key < [i] 2 then error new key is smaller than current key 3 [i] key 4 while i > ND [PRENT(i)] < [i] 5 do exchange [i] [PRENT(i)] 6 i PRENT(i) Line 3 入力で指定された添字のキー値を, 入力で与えられたキー値に変更

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY INCRESE-KEY を実現する キー値を増やす優先度付きキューの要素配列の添字 i で表す アルゴリズム HEP-INCRESE-KEY(,i,key) if key < [i] 2 then error new key is smaller than current key 3 [i] key 4 while i > ND [PRENT(i)] < [i] 5 do exchange [i] [PRENT(i)] 6 i PRENT(i) Line 4-6 while ループキー値が増加したので,max- ヒープ条件が成立しなくなった可能性がある [i] が max- ヒープ条件を満たすような位置に来るように, その親と交換していく

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY INCRESE-KEY を実現する キー値を増やす優先度付きキューの要素配列の添字 i で表す アルゴリズム HEP-INCRESE-KEY(,i,key) if key < [i] 2 then error new key is smaller than current key 3 [i] key 4 while i > ND [PRENT(i)] < [i] 5 do exchange [i] [PRENT(i)] 6 i PRENT(i) Line 3 で値が更新される節点から根に至る経路の長さが O(lgn) だから, n 個の要素を持つヒープにおける HEP-INCRESE-KEY の実行時間は O(lgn)

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY 実行例 (HEP-INCRESE-KEY(,9,5) の動作 ) 6 4 0 8 7 9 3 8 9 0 2 4

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY 実行例 (HEP-INCRESE-KEY(,9,5) の動作 ) [9] に 5 を代入 6 4 0 8 7 9 3 8 9 0 2 4

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY 実行例 (HEP-INCRESE-KEY(,9,5) の動作 ) [9] に 5 を代入 6 4 0 8 7 9 3 8 9 0 2 5

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY 実行例 (HEP-INCRESE-KEY(,9,5) の動作 ) i=9 [PRENT(9)]=[4]=8<[9] [9] と [4] を交換 6 4 0 8 7 9 3 8 9 0 2 5

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY 実行例 (HEP-INCRESE-KEY(,9,5) の動作 ) i=9 [PRENT(9)]=[4]=8<[9] [9] と [4] を交換 6 4 0 5 7 9 3 8 9 0 2 8

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY 実行例 (HEP-INCRESE-KEY(,9,5) の動作 ) i=4 [PRENT(4)]=[2]=4<[4] [4] と [2] を交換 6 4 0 5 7 9 3 8 9 0 2 8

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY 実行例 (HEP-INCRESE-KEY(,9,5) の動作 ) i=4 [PRENT(4)]=[2]=4<[4] [4] と [2] を交換 6 5 0 4 7 9 3 8 9 0 2 8

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY 実行例 (HEP-INCRESE-KEY(,9,5) の動作 ) i=2 [PRENT(2)]=[]=6>[4] 処理が終了 6 5 0 4 7 9 3 8 9 0 2 8

6.5 優先度付きキュー (Priority queues) 手続き HEP-INCRESE-KEY 実行例 (HEP-INCRESE-KEY(,9,5) の動作 ) max- ヒープが再構成された 6 5 0 4 7 9 3 8 9 0 2 8

6.5 優先度付きキュー (Priority queues) 手続き MX-HEP-INSERT INSERT を実現する 入力は max- ヒープ に挿入される新しい要素のキー 木にキー値 - を持つ新しい葉を加えることで max- ヒープを拡大する HEP-INCRESE-KEY を呼び出し, 新しい節点のキー値を正しい値に設定し,max- ヒープ条件を維持する アルゴリズム Line heap-size[] を 増加させる MX-HEP-INSERT(,key) heap-size[] heap-size[] + 2 [heap-size[]] - 3 HEP-INCRESE-KEY(,heap-size[],key)

6.5 優先度付きキュー (Priority queues) 手続き MX-HEP-INSERT INSERT を実現する 入力は max- ヒープ に挿入される新しい要素のキー 木にキー値 - を持つ新しい葉を加えることで max- ヒープを拡大する HEP-INCRESE-KEY を呼び出し, 新しい節点のキー値を正しい値に設定し,max- ヒープ条件を維持する アルゴリズム MX-HEP-INSERT(,key) heap-size[] heap-size[] + 2 [heap-size[]] - 3 HEP-INCRESE-KEY(,heap-size[],key) Line 2 増やした葉にキー値 - を代入

6.5 優先度付きキュー (Priority queues) 手続き MX-HEP-INSERT INSERT を実現する 入力は max- ヒープ に挿入される新しい要素のキー 木にキー値 - を持つ新しい葉を加えることで max- ヒープを拡大する HEP-INCRESE-KEY を呼び出し, 新しい節点のキー値を正しい値に設定し,max- ヒープ条件を維持する アルゴリズム MX-HEP-INSERT(,key) heap-size[] heap-size[] + 2 [heap-size[]] - 3 HEP-INCRESE-KEY(,heap-size[],key) Line 3 HEP-INCRESE-KEY を実行して, キー値 - を key に置き換え, さらに max- ヒープ条件を満たすようにする n 個の要素を持つヒープに対する MX-HEP-INSERT の実行時間は O(lgn) したがって, ヒープを用いるとサイズ n の集合上の優先度付きキューの全ての操作を O(nlgn) 時間で実現できる