• 検索結果がありません。

INTRODUCTION TO ALGORITHMS

N/A
N/A
Protected

Academic year: 2021

シェア "INTRODUCTION TO ALGORITHMS"

Copied!
161
0
0

読み込み中.... (全文を見る)

全文

(1)

INTRODUCTION TO ALGORITHMS

6. Heapsort

2011.7.7

(2)

CONTENTS

6.1 ヒープ (Heap)

6.2 ヒープ条件の維持

(Maintaining the heap property)

6.3 ヒープの構成 (Building a heap)

6.4 ヒープソート (The heapsort algorithm)

(3)

CONTENTS

6.1 ヒープ (Heap)

6.2 ヒープ条件の維持

(Maintaining the heap property)

6.3 ヒープの構成 (Building a heap)

6.4 ヒープソート (The heapsort algorithm)

(4)

6.1 ヒープ (Heap)

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

(5)

 ヒープを表す配列が持つ2つの属性  length[A] ・・・配列Aの要素数  heap-size[A] ・・・配列Aに含まれているヒープの要素数 すなわち,A[1…length[A]]には正しい要素が 含まれているが,A[heap-size[A]]を超える要素 はどれもヒープの要素ではない ただし,heap-size[A]≦length[A]

6.1 ヒープ (Heap)

16 14 10 8 7 9 3 2 4 1 16 14 10 8 7 9 3 2 4 1 1 2 3 4 6 5 7 8 9 10 1 2 3 4 5 6 7 8 9 10

(6)

木の根はA[1]であり,節点の添字iが与えら れたとき, その親 PARENT(i), 左の子 LEFT(i), 右の子 RIGHT(i) は簡単に計算できる PARENT(i) return 𝑖/2 LEFT(i) return 2𝑖 RIGHT(i) return 2𝑖 + 1

6.1 ヒープ (Heap)

16 14 10 8 7 9 3 2 4 1 16 14 10 8 7 9 3 2 4 1 1 2 3 4 6 5 7 8 9 10 1 2 3 4 5 6 7 8 9 10

(7)

大抵の計算機では・・・ LEFT: i の2進表現を1ビット左にシフトすることで 2i を計算 RIGHT: i の2進表現を1ビット左にシフトしたあと,最 下位ビットを1にすることで2i+1を計算 PARENT: i の2進表現を1ビット右にシフトすることで 𝑖/2 を計算

6.1 ヒープ (Heap)

16 14 10 8 7 9 3 2 4 1 16 14 10 8 7 9 3 2 4 1 1 2 3 4 6 5 7 8 9 10 1 2 3 4 5 6 7 8 9 10

(8)

大抵の計算機では・・・ LEFT: i の2進表現を1ビット左にシフトすることで 2i を計算 RIGHT: i の2進表現を1ビット左にシフトしたあと,最 下位ビットを1にすることで2i+1を計算 PARENT: i の2進表現を1ビット右にシフトすることで 𝑖/2 を計算 ヒープソートのうまい手続きでは, これら3つの手続きはしばしば「マクロ」また は「インライン」手続きとして実現される

6.1 ヒープ (Heap)

16 14 10 8 7 9 3 2 4 1 16 14 10 8 7 9 3 2 4 1 1 2 3 4 6 5 7 8 9 10 1 2 3 4 5 6 7 8 9 10

(9)

2分木ヒープの種類

どちらもヒープ条件 (heap property) を満たす

 max-ヒープ

 根以外の任意の節点i が A[PARENT(i)]≧A[i] を満たす (max-ヒープ条件 (max-heap property))

 最大の要素は根に格納されており,ある接点を根とする部分木にはその節 点自身の値以下の値が含まれている

 min-ヒープ

 根以外の任意の接点i が A[PARENT(i)]≦A[i] を満たす (min-ヒープ条件 (min-heap property))

 最小の要素は根に格納される

ヒープソートアルゴリズムではmax-ヒープを用いる minヒープは優先度付きキューでよく用いられる

(10)

ヒープにおける節点の高さ

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

6.1 ヒープ (Heap)

16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 ・・h=3 ・・h=2 ・・h=1 ・・h=0

(11)

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

手続き MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, HEAP-MAXIMUM:

ヒープデータ構造を優先度付きキューとして用いる時に使用する いずれもO(lgn)時間で動作する

(12)

EXERCISE

6.1-1 高さ h のヒープの持つ要素数の最大と最小はいくつか. (解答) 最大: 2𝑛 ℎ 𝑛=0 = 2ℎ+1 − 1 2 − 1 = 2ℎ+1 − 1 最小: 2𝑛 + 1 ℎ−1 𝑛=0 = 2 (ℎ−1)+1 − 1 2 − 1 = 2ℎ − 1 + 1 = 2ℎ

6.1 ヒープ (Heap)

(13)

EXERCISE

6.1-2 要素数が n のヒープの高さが ⌊𝑙𝑔𝑛⌋ となることを示せ. (解答) 高さを h とすると,6.1-1 より,n 個の要素からなるヒープは 2ℎ ≤ 𝑛 ≤ 2ℎ+1 − 1 → 2ℎ ≤ 𝑛 ≤ 2ℎ+1 − 1 < 2ℎ+1 を満たす. 対数をとると, ℎ ≤ 𝑙𝑜𝑔𝑛 ≤ ℎ + 1 したがって ℎ = ⌊𝑙𝑜𝑔𝑛⌋

6.1 ヒープ (Heap)

(14)

EXERCISE

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

6.1 ヒープ (Heap)

(15)

EXERCISE

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

6.1 ヒープ (Heap)

(16)

EXERCISE

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

6.1 ヒープ (Heap)

(17)

EXERCISE

6.1-6 数列 〈23,17,14,6,13,10,1,5,7,12〉 は max-ヒープか. (解答) A[4]=6 A[RIGHT(4)]=A[9]=7>A[4] したがって max-ヒープ条件を満たさないため, この数列は max-ヒープではない

6.1 ヒープ (Heap)

23 6 14 7 13 10 1 5 17 12 5 1 2 3 4 6 7 8 9 10

(18)

EXERCISE

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

6.1 ヒープ (Heap)

1 2 3

(19)

EXERCISE

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

6.1 ヒープ (Heap)

(20)

EXERCISE

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

6.1 ヒープ (Heap)

1 2

(21)

EXERCISE

(22)

CONTENTS

6.1 ヒープ (Heap)

6.2 ヒープ条件の維持

(Maintaining the heap property)

6.3 ヒープの構成 (Building a heap)

6.4 ヒープソート (The heapsort algorithm)

(23)

手続き M

AX

-H

EAPIFY

 入力は配列A と配列の添字i

 添字iを根とする部分木が max-ヒープになるように A[i]

の値をmax-ヒープの中に「滑り落とす」

 この手続きが呼ばれるとき,LEFT(i) と RIGHT(i) を根とする二分木

が max-ヒープであることを仮定する

アルゴリズム

6.2 ヒープ条件の維持 (Maintaining the heap property)

MAX-HEAPIFY(A,i) 1 l ← LEFT(i) 2 r ← RIGHT(i) 3 if l ≦ heap-size[A] かつ A[l]>A[i] 4 then largest ← l 5 else largest ← i

6 if r ≦heap-size[A] かつ A[r] > A[largest] 7 then largest ← r

8 if largest ≠ i

9 then exchange A[i] ↔ A[largest] 10 MAX-HEAPIFY(A,largest)

Line 1-2

節点iの左の子のインデックスを l に, 右の子のインデックスを r に代入

(24)

手続き M

AX

-H

EAPIFY

 入力は配列A と配列の添字i

 添字iを根とする部分木が max-ヒープになるように A[i]

の値をmax-ヒープの中に「滑り落とす」

 この手続きが呼ばれるとき,LEFT(i) と RIGHT(i) を根とする二分木

が max-ヒープであることを仮定する

アルゴリズム

6.2 ヒープ条件の維持 (Maintaining the heap property)

MAX-HEAPIFY(A,i) 1 l ← LEFT(i) 2 r ← RIGHT(i) 3 if l ≦ heap-size[A] かつ A[l]>A[i] 4 then largest ← l 5 else largest ← i

6 if r ≦heap-size[A] かつ A[r] > A[largest] 7 then largest ← r

8 if largest ≠ i

9 then exchange A[i] ↔ A[largest] 10 MAX-HEAPIFY(A,largest) Line 3-5 if 文 節点iが左の子を持ち, かつ節点iの値より左の子の値のほうが大きければ, largestに左の子のインデックスを代入する そうでなければlargestにiを代入

(25)

手続き M

AX

-H

EAPIFY

 入力は配列A と配列の添字i

 添字iを根とする部分木が max-ヒープになるように A[i]

の値をmax-ヒープの中に「滑り落とす」

 この手続きが呼ばれるとき,LEFT(i) と RIGHT(i) を根とする二分木

が max-ヒープであることを仮定する

アルゴリズム

6.2 ヒープ条件の維持 (Maintaining the heap property)

MAX-HEAPIFY(A,i) 1 l ← LEFT(i) 2 r ← RIGHT(i) 3 if l ≦ heap-size[A] かつ A[l]>A[i] 4 then largest ← l 5 else largest ← i

6 if r ≦heap-size[A] かつ A[r] > A[largest] 7 then largest ← r

8 if largest ≠ i

9 then exchange A[i] ↔ A[largest] 10 MAX-HEAPIFY(A,largest) Line 6-7 if 文 節点iが右の子を持ち, かつインデックスがlargestである節点の値より右の子の値の ほうが大きければ, largestに右の子のインデックスを代入する

(26)

手続き M

AX

-H

EAPIFY

 入力は配列A と配列の添字i

 添字iを根とする部分木が max-ヒープになるように A[i]

の値をmax-ヒープの中に「滑り落とす」

 この手続きが呼ばれるとき,LEFT(i) と RIGHT(i) を根とする二分木

が max-ヒープであることを仮定する

アルゴリズム

6.2 ヒープ条件の維持 (Maintaining the heap property)

MAX-HEAPIFY(A,i) 1 l ← LEFT(i) 2 r ← RIGHT(i) 3 if l ≦ heap-size[A] かつ A[l]>A[i] 4 then largest ← l 5 else largest ← i

6 if r ≦heap-size[A] かつ A[r] > A[largest] 7 then largest ← r

8 if largest ≠ i

9 then exchange A[i] ↔ A[largest] 10 MAX-HEAPIFY(A,largest) Line 8-10 if 文 節点iが最大値(右の子,左の子の値と比べたとき)を持つ節 点でなければ, A[i] と A[largest] を交換し, 今度はA[largest]に対してMAX-HEAPIFYを実行する

(27)

手続き M

AX

-H

EAPIFY

 動作例( MAX-HEAPIFY(A,2) の動作)

6.2 ヒープ条件の維持 (Maintaining the heap property)

16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 heap-size[A]=10

(28)

手続き M

AX

-H

EAPIFY

 動作例( MAX-HEAPIFY(A,2) の動作)

6.2 ヒープ条件の維持 (Maintaining the heap property)

16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 A[2]=4 A[LEFT(2)]=A[4]=14 A[RIGHT(2)]=A[5]=4 最大値はA[4]=14 i heap-size[A]=10

(29)

手続き M

AX

-H

EAPIFY

 動作例( MAX-HEAPIFY(A,2) の動作)

6.2 ヒープ条件の維持 (Maintaining the heap property)

16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 A[2]=4 A[LEFT(2)]=A[4]=14 A[RIGHT(2)]=A[5]=4 最大値はA[4]=14 A[2]とA[4]を交換 次はi=4として MAX-HEAPIFYを実行 i heap-size[A]=10

(30)

手続き M

AX

-H

EAPIFY

 動作例( MAX-HEAPIFY(A,2) の動作)

6.2 ヒープ条件の維持 (Maintaining the heap property)

16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 A[4]=4 A[LEFT(4)]=A[8]=2 A[RIGHT(4)]=A[9]=8 最大値はA[9]=8 i heap-size[A]=10

(31)

手続き M

AX

-H

EAPIFY

 動作例( MAX-HEAPIFY(A,2) の動作)

6.2 ヒープ条件の維持 (Maintaining the heap property)

16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 A[4]=4 A[LEFT(4)]=A[8]=2 A[RIGHT(4)]=A[9]=8 最大値はA[9]=8 A[4]とA[9]を交換 次はi=9として MAX-HEAPIFYを実行 i heap-size[A]=10

(32)

手続き M

AX

-H

EAPIFY

 動作例( MAX-HEAPIFY(A,2) の動作)

6.2 ヒープ条件の維持 (Maintaining the heap property)

16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 A[9]=4 LEFT(9)=18>heap-size[A] RIGHT(9)=19>heap-size[A] したがって処理が終了 i heap-size[A]=10

(33)

手続き M

AX

-H

EAPIFY

 動作例( MAX-HEAPIFY(A,2) の動作)

6.2 ヒープ条件の維持 (Maintaining the heap property)

16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 A[9]=4 LEFT(9)=18>heap-size[A] RIGHT(9)=19>heap-size[A] したがって処理が終了 heap-size[A]=10 確かに添字i=2を根とする部分木が max-ヒープになっている

(34)

手続き M

AX

-H

EAPIFY  実行時間の吟味] MAX-HEAPIFYの実行時間は, A[i],A[LEFT(i)],A[RIGHT(i)] の間の関係を比較するための Θ(1) 時間と, 節点 i のどちらかの子を 根とする部分木に対する MAX-HEAPIFY の実行時間 との合計である

6.2 ヒープ条件の維持 (Maintaining the heap property)

i どちらの子の部分木のサイズも高々2n/3 (左図のように木の最下行が半分だけ埋まっている場合) だから,MAX-HEAPIFYの実行時間は漸化式 T(n) ≦ T(2n/3) + Θ(1) で表現できる したがって,T(n) = O(lgn) である 高さhの節点に対するMAX-HEAPIFYの実行時間はO(h)であると言える

(35)

EXERCISE

6.2-1 図6.2 を参考にして,配列 A= 〈27,17,3,16,13,10,1,5,7,12,4,8,9,0〉に対するMAX-HEAPIFY の動作を示せ. (解答) 希望があればホワイトボードで

(36)

EXERCISE

6.2-2 手続きMAX-HEAPIFYを利用して,min-ヒープ上で MAX-HEAPIFY に対応する操作 を実現する手続き MAX-HEAPIFY の擬似コードを書け. MAX-HEAPIFY の実行時間 を MAX-HEAPIFY と比較せよ (解答) 実行に要する時間は MAX-HEAPIFY と変わらない

6.2 ヒープ条件の維持 (Maintaining the heap property)

MIN-HEAPIFY(A,i) 1 l ← LEFT(i) 2 r ← RIGHT(i)

3 if l ≦ heap-size[A] AND A[l] < A[i] 4 then smallest ← l

5 else smallest ← i

6 if r ≦ heap-size[A] AND A[r] < A[largest] 7 then smallest ← r

8 if largest ≠ i

9 then exchange A[i] ↔ A[smallest] 10 MIN-HEAPIFY(A,smallest)

(37)

EXERCISE

6.2-3 要素 A[i] が両方の子より大きいとき,MAX-HEAPIFY(A,i) の呼び出しはどのような効 果があるか. (解答) 何も行われずに終了する CIRQUE1015 MAX-HEAPIFY(A,1) を呼び出した! しかし、なにもおこらなかった!

(38)

EXERCISE

6.2-4 i > heap-size[A]/2 のとき,MAX-HEAPIFY(A,1) の呼び出しはどのような効果があるか. (解答) 6.1-7 より,添字が i > heap-size[A]/2 となるものは全て葉であるため何も起きない. CIRQUE1015 MAX-HEAPIFY(A,1) を呼び出した! しかし、なにm(ry

(39)

EXERCISE

6.2-5 MAX-HEAPIFY の コードは,Line10 の再帰呼び出しを除けばかなり小さい定数係 数を持つ.しかし,あるコンパイラは再帰呼び出しを効率の悪いコードに変換するかもし れない.再帰の代わりに繰り返し構造子(ループ)を用いて効率のよい MAX-HEAPIFY を書け。 (解答) (条件式)=NOT((A[i]が右の子,左の子両方を持ち,その両方より大きい)OR(A[i]が どちらか片方の子のみを持ち,それより大きい)OR(A[i]は葉ではない))

6.2 ヒープ条件の維持 (Maintaining the heap property)

MAX-HEAPIFY(A,i) 1 while (条件式) 2 do l ← LEFT(i) 3 r ← RIGHT(i)

4 if l ≦ heap-size[A] AND A[l]>A[i] 5 then largest ← l

6 if r ≦heap-size[A] AND A[r] > A[largest] 7 then largest ← r

8 if largest ≠ i

9 then exchange A[i] ↔ A[largest] 10 i ← largest

(40)

EXERCISE

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

(41)

CONTENTS

6.1 ヒープ (Heap)

6.2 ヒープ条件の維持

(Maintaining the heap property)

6.3 ヒープの構成 (Building a heap)

6.4 ヒープソート (The heapsort algorithm)

(42)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP

 n=length[A] とすると,Exercise 6.1-7より部分配列 A[( 𝑛/2 +1)…n] の要素 は全て葉(つまり最小のmax-ヒープ)

→木のそれぞれの節点において,後ろから順にMAX-HEAPIFYを繰り返し実行すれば,

max-ヒープを構成できる

アルゴリズム

BUILD-MAX-HEAP(A)

1 heap-size[A] ← length[A] 2 for i ← 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴]/2 downto 1 3 do MAX-HEAPIFY(A,i) Line 2-3 forループ ヒープの節点全てに、後ろから順に MAX-HEAPIFY を実行する

(43)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 heap-size[A]←length[A](=10) 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴]/2 =5 for ループは i=5 からスタート 4 1 3 2 16 9 10 14 8 7 1 2 3 4 5 6 7 8 9 10 A

(44)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=5 4 1 3 2 16 9 10 14 8 7 1 2 3 4 5 6 7 8 9 10 A i

(45)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=5 MAX-HEAPIFY(A,5) を実行 交換はしない A[5]を根とする部分max-ヒープを構成 4 1 3 2 16 9 10 14 8 7 1 2 3 4 5 6 7 8 9 10 A i

(46)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=4 4 1 3 2 16 9 10 14 8 7 1 2 3 4 5 6 7 8 9 10 A i

(47)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=4 MAX-HEAPIFY(A,4) を実行 4 1 3 2 16 9 10 14 8 7 1 2 3 4 5 6 7 8 9 10 A

(48)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=4 MAX-HEAPIFY(A,4) を実行 A[4]とA[8]を交換 A[4]を根とする部分max-ヒープを構成 4 1 3 14 16 9 10 2 8 7 1 2 3 4 5 6 7 8 9 10 A

(49)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=3 4 1 3 14 16 9 10 2 8 7 1 2 3 4 5 6 7 8 9 10 A i

(50)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=3 MAX-HEAPIFY(A,3) を実行 4 1 3 14 16 9 10 2 8 7 1 2 3 4 5 6 7 8 9 10 A

(51)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=3 MAX-HEAPIFY(A,3) を実行 A[3]とA[7]を交換 A[3]を根とする部分maxヒープを構成 4 1 10 14 16 9 3 2 8 7 1 2 3 4 5 6 7 8 9 10 A

(52)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=2 4 1 10 14 16 9 3 2 8 7 1 2 3 4 5 6 7 8 9 10 A i

(53)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=2 MAX-HEAPIFY(A,2) を実行 4 1 10 14 16 9 3 2 8 7 1 2 3 4 5 6 7 8 9 10 A

(54)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 7 9 3 2 4 1 5 1 2 3 4 6 7 8 9 10 i=2 MAX-HEAPIFY(A,2) を実行 A[2]とA[5]を交換 4 16 10 14 1 9 3 2 8 7 1 2 3 4 5 6 7 8 9 10 A

(55)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 1 9 3 2 4 7 5 1 2 3 4 6 7 8 9 10 i=2 MAX-HEAPIFY(A,2) を実行 A[5]とA[10]を交換 A[2]を根とする部分maxヒープを構成 4 16 10 14 7 9 3 2 8 1 1 2 3 4 5 6 7 8 9 10 A

(56)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 1 9 3 2 4 7 5 1 2 3 4 6 7 8 9 10 i=1 4 16 10 14 7 9 3 2 8 1 1 2 3 4 5 6 7 8 9 10 A i

(57)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 16 14 10 8 1 9 3 2 4 7 5 1 2 3 4 6 7 8 9 10 i=1 MAX-HEAPIFY(A,1) を実行 4 16 10 14 7 9 3 2 8 1 1 2 3 4 5 6 7 8 9 10 A

(58)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 4 14 10 8 1 9 3 2 16 7 5 1 2 3 4 6 7 8 9 10 i=1 MAX-HEAPIFY(A,1) を実行 A[1]とA[2]を交換 16 4 10 14 7 9 3 2 8 1 1 2 3 4 5 6 7 8 9 10 A

(59)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 14 4 10 8 1 9 3 2 16 7 5 1 2 3 4 6 7 8 9 10 i=1 MAX-HEAPIFY(A,1) を実行 A[2]とA[4]を交換 16 14 10 4 7 9 3 2 8 1 1 2 3 4 5 6 7 8 9 10 A

(60)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 14 8 10 4 1 9 3 2 16 7 5 1 2 3 4 6 7 8 9 10 i=1 MAX-HEAPIFY(A,1) を実行 A[4]とA[9]を交換 A[1]を根とする部分max-ヒープ, 目的のmaxヒープが構成された 16 14 10 8 7 9 3 2 4 1 1 2 3 4 5 6 7 8 9 10 A

(61)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  動作例 14 8 10 4 1 9 3 2 16 7 5 1 2 3 4 6 7 8 9 10 A[1]を根とする部分max-ヒープ, 目的のmaxヒープが構成された 16 14 10 8 7 9 3 2 4 1 1 2 3 4 5 6 7 8 9 10 A

(62)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  アルゴリズムの正当性 次のループ不変式を利用して BUID-MAX-HEAP の正当性を示す 初期条件: ループの最初の繰り返しでは,i= 𝑛/2 である 各節点 𝑛/2 +1, 𝑛/2 +2,….,n は葉であり,したがって自明な max-ヒープの根 である ループ内条件: ループの各繰り返しが不変式を維持することを示すために,節点iの子はiより大 きい番号を持つことに注意する ループ不変式が成り立つとすると,節点i の子はいずれも max-ヒープの根となる これは,MAX-HEAPIFY(A,i)が節点i を max-ヒープの根に修正する時に必要と する条件そのものである

さらに,この MAX-HEAPIFY の呼び出しは節点 i+1,i+2,…,n が max-ヒープの 根であるという性質を保存する

(63)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

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

(64)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP

 実行時間の吟味

MAX-HEAPIFYの各呼び出しに O(lgn) 時間かかり,呼び出しは O(n) 回起こ るので,BUILD-MAX-HEAPの実行時間は高々 O(nlgn) である しかし,ある節点におけるMAX-HEAPIFYの実行時間はその節点の高さに依 存すること,そしてほとんどの節点の高さは小さいことに注意すると,よりタイトな 上界が導出可能 Exercise 6.1-2 より n個の要素を持つヒープの高さは 𝑙𝑔𝑛 であり, 高さ h の節点は高々 𝑛/2ℎ+1 個しかない (Exercise 6.3-3) ことを用いて解析 する

(65)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  実行時間の吟味 MAX-HEAPIFYが高さhの節点で呼ばれたときに要する時間は, 前節よりO(h)である したがって,BUILD-MAX-HEAPの全コストは上から 𝑛 2ℎ+1 𝑙𝑔𝑛 ℎ=0 𝑂 ℎ = 𝑂 𝑛 ℎ 2𝑛 𝑙𝑔𝑛 ℎ=0 で抑えられる ここで等比無限級数の収束の公式(ホワイトボードにて説明)を用いると, 右辺の和は ℎ 2ℎ ∞ ℎ=0 = 1/2 1 −12 2 = 2 と計算できるので,BUILD-MAX-HEAP の実行時間の上界は

(66)

6.3 ヒープの構成 (Building a heap)

手続き B

UILD

-M

AX

-H

EAP  実行時間の吟味 𝑂 𝑛 ℎ 2𝑛 𝑙𝑔𝑛 ℎ=0 = 𝑂 𝑛 ℎ 2𝑛 ℎ=0 = 𝑂(𝑛) となる したがって,未ソートの配列からmax-ヒープを線形時間で構成できるということが わかった ∞

(67)

CONTENTS

6.1 ヒープ (Heap)

6.2 ヒープ条件の維持

(Maintaining the heap property)

6.3 ヒープの構成 (Building a heap)

6.4 ヒープソート (The heapsort algorithm)

(68)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT

BUILD-MAX-HEAPを用いて入力配列 A[1..n] 中に max-ヒープを構成する 配列の最大要素は構成された max-ヒープの根,つまり A[1] に格納されているの で,A[1] を A[n] と交換することで,最大要素を配列の正しい位置に配置できる ここで(heap-size[A]を1減らすことによって)節点nをヒープから「取り除く」と,A[1] の子はどちらも max-ヒープの根となっているから,MAX-HEAPIFY(A,1) を1回呼び 出せば残りの配列は容易にmax-ヒープとなる これを繰り返すことで配列を正しくソートすることができる

アルゴリズム

HEAPSORT(A) 1 BUILD-MAX-HEAP(A)

2 for i ← length[A] downto 2 3 do exchange A[1] ↔ A[i]

4 heap-size[A] ← heap-size[A]-1 5 MAX-HEAPIFY(A,1)

Line 1

入力配列をBUILD-MAX-HEAPに よってmax-ヒープにする

(69)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT

BUILD-MAX-HEAPを用いて入力配列 A[1..n] 中に max-ヒープを構成する 配列の最大要素は構成された max-ヒープの根,つまり A[1] に格納されているの で,A[1] を A[n] と交換することで,最大要素を配列の正しい位置に配置できる ここで(heap-size[A]を1減らすことによって)節点nをヒープから「取り除く」と,A[1] の子はどちらも max-ヒープの根となっているから,MAX-HEAPIFY(A,1) を1回呼び 出せば残りの配列は容易にmax-ヒープとなる これを繰り返すことで配列を正しくソートすることができる

アルゴリズム

HEAPSORT(A) 1 BUILD-MAX-HEAP(A)

2 for i ← length[A] downto 2 3 do exchange A[1] ↔ A[i]

4 heap-size[A] ← heap-size[A]-1 5 MAX-HEAPIFY(A,1) Line 2-5 forループ 配列の後ろから2つ目まで繰り返す max-ヒープの根の要素を i 番目の要 素を交換し,heap-size[A] を1減らすこ とでヒープから取り除く その後,ヒープが max-ヒープとなるよ うにMAX-HEAPIFY を1回呼び出して A[1] を 適正位置に滑り落とす

(70)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 8 10 4 1 9 3 2 16 7 5 1 2 3 4 6 7 8 9 10 16 14 10 8 7 9 3 2 4 1 1 2 3 4 5 6 7 8 9 10 A BUILD-MAX-HEAP によって構成された直後の max-ヒープデータ構造

(71)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 8 10 4 1 9 3 2 16 7 5 1 2 3 4 6 7 8 9 10 16 14 10 8 7 9 3 2 4 1 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=10 heap-size[A]=10 A[1]とA[10]を交換する

(72)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 8 10 4 16 9 3 2 1 7 5 1 2 3 4 6 7 8 9 10 1 14 10 8 7 9 3 2 4 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=10 heap-size[A]=10 A[1]とA[10]を交換する

(73)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 8 10 4 16 9 3 2 1 7 5 1 2 3 4 6 7 8 9 10 1 14 10 8 7 9 3 2 4 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=10 heap-size[A]=10-1=9 A[10]をヒープから取り除く

(74)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 8 10 4 16 9 3 2 1 7 5 1 2 3 4 6 7 8 9 10 1 14 10 8 7 9 3 2 4 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=10 heap-size[A]=9 MAX-HEAPIFY(A,1)を実行

(75)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 8 10 4 16 9 3 2 1 7 5 1 2 3 4 6 7 8 9 10 14 1 10 8 7 9 3 2 4 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=10 heap-size[A]=9 MAX-HEAPIFY(A,1)を実行 A[1]とA[2]を交換

(76)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 1 10 4 16 9 3 2 8 7 5 1 2 3 4 6 7 8 9 10 14 8 10 1 7 9 3 2 4 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=10 heap-size[A]=9 MAX-HEAPIFY(A,1)を実行 A[2]とA[4]を交換

(77)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 1 16 9 3 2 8 7 5 1 2 3 4 6 7 8 9 10 14 8 10 4 7 9 3 2 1 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=10 heap-size[A]=9 MAX-HEAPIFY(A,1)を実行 A[4]とA[9]を交換

(78)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 1 16 9 3 2 8 7 5 1 2 3 4 6 7 8 9 10 14 8 10 4 7 9 3 2 1 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=10 heap-size[A]=9 再びmax-ヒープが構成された

(79)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 1 16 9 3 2 8 7 5 1 2 3 4 6 7 8 9 10 14 8 10 4 7 9 3 2 1 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=9 heap-size[A]=9 A[1]とA[9]を交換する

(80)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 1 16 9 3 2 8 7 5 1 2 3 4 6 7 8 9 10 1 8 10 4 7 9 3 2 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=9 heap-size[A]=9 A[1]とA[9]を交換する

(81)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 1 16 9 3 2 8 7 5 1 2 3 4 6 7 8 9 10 1 8 10 4 7 9 3 2 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=9 heap-size[A]=9-1=8 A[9]をヒープから取り除く

(82)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 1 16 9 3 2 8 7 5 1 2 3 4 6 7 8 9 10 1 8 10 4 7 9 3 2 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=9 heap-size[A]=8 MAX-HEAPIFY(A,1)を実行

(83)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 1 16 9 3 2 8 7 5 1 2 3 4 6 7 8 9 10 10 8 1 4 7 9 3 2 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=9 heap-size[A]=8 MAX-HEAPIFY(A,1)を実行 A[1]とA[3]を交換

(84)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 9 16 1 3 2 8 7 5 1 2 3 4 6 7 8 9 10 10 8 9 4 7 1 3 2 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=9 heap-size[A]=8 MAX-HEAPIFY(A,1)を実行 A[3]とA[6]を交換

(85)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 9 16 1 3 2 8 7 5 1 2 3 4 6 7 8 9 10 10 8 9 4 7 1 3 2 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=9 heap-size[A]=8 再びmax-ヒープが構成された

(86)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 9 16 1 3 2 8 7 5 1 2 3 4 6 7 8 9 10 10 8 9 4 7 1 3 2 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=8 heap-size[A]=8 A[1]とA[8]を交換

(87)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 9 16 1 3 2 8 7 5 1 2 3 4 6 7 8 9 10 2 8 9 4 7 1 3 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=8 heap-size[A]=8 A[1]とA[8]を交換

(88)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 9 16 1 3 2 8 7 5 1 2 3 4 6 7 8 9 10 2 8 9 4 7 1 3 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=8 heap-size[A]=8-1=7 A[8]をヒープから取り除く

(89)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 9 16 1 3 2 8 7 5 1 2 3 4 6 7 8 9 10 2 8 9 4 7 1 3 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=8 heap-size[A]=7 MAX=HEAPIFY(A,1)を実行

(90)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 2 16 1 3 9 8 7 5 1 2 3 4 6 7 8 9 10 9 8 2 4 7 1 3 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=8 heap-size[A]=7 MAX=HEAPIFY(A,1)を実行 A[1]とA[3]を交換

(91)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 1 2 9 8 7 5 1 2 3 4 6 7 8 9 10 9 8 3 4 7 1 2 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=8 heap-size[A]=7 MAX=HEAPIFY(A,1)を実行 A[3]とA[7]を交換

(92)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 1 2 9 8 7 5 1 2 3 4 6 7 8 9 10 9 8 3 4 7 1 2 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=8 heap-size[A]=7 再びmax-ヒープが構成された

(93)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 1 2 9 8 7 5 1 2 3 4 6 7 8 9 10 9 8 3 4 7 1 2 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=7 heap-size[A]=7 A[1]とA[7]を交換

(94)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 1 9 2 8 7 5 1 2 3 4 6 7 8 9 10 2 8 3 4 7 1 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=7 heap-size[A]=7 A[1]とA[7]を交換

(95)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 1 9 2 8 7 5 1 2 3 4 6 7 8 9 10 2 8 3 4 7 1 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=7 heap-size[A]=7-1=6 A[7]をヒープから取り除く

(96)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 1 9 2 8 7 5 1 2 3 4 6 7 8 9 10 2 8 3 4 7 1 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=7 heap-size[A]=6 MAX-HEAPIFY(A,1)を実行

(97)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 1 9 8 2 7 5 1 2 3 4 6 7 8 9 10 8 2 3 4 7 1 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=7 heap-size[A]=6 MAX-HEAPIFY(A,1)を実行 A[1]とA[2]を交換

(98)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 1 9 8 7 2 5 1 2 3 4 6 7 8 9 10 8 7 3 4 2 1 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=7 heap-size[A]=6 MAX-HEAPIFY(A,1)を実行 A[2]とA[5]を交換

(99)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 1 9 8 7 2 5 1 2 3 4 6 7 8 9 10 8 7 3 4 2 1 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=7 heap-size[A]=6 再びmax-ヒープが構成された

(100)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 1 9 8 7 2 5 1 2 3 4 6 7 8 9 10 8 7 3 4 2 1 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=6 heap-size[A]=6 A[1]とA[6]を交換

(101)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 7 2 5 1 2 3 4 6 7 8 9 10 1 7 3 4 2 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=6 heap-size[A]=6 A[1]とA[6]を交換

(102)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 7 2 5 1 2 3 4 6 7 8 9 10 1 7 3 4 2 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=6 heap-size[A]=6-1=5 A[6]をヒープから取り除く

(103)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 7 2 5 1 2 3 4 6 7 8 9 10 1 7 3 4 2 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=6 heap-size[A]=5 MAX-HEAPIFY(A,1)を実行する

(104)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 7 1 2 5 1 2 3 4 6 7 8 9 10 7 1 3 4 2 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=6 heap-size[A]=5 MAX-HEAPIFY(A,1)を実行する A[1]とA[2]を交換

(105)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 1 10 3 16 8 9 7 4 2 5 1 2 3 4 6 7 8 9 10 7 4 3 1 2 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=6 heap-size[A]=5 MAX-HEAPIFY(A,1)を実行する A[2]とA[4]を交換

(106)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 1 10 3 16 8 9 7 4 2 5 1 2 3 4 6 7 8 9 10 7 4 3 1 2 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=6 heap-size[A]=5 再びmax-ヒープが構成された

(107)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 1 10 3 16 8 9 7 4 2 5 1 2 3 4 6 7 8 9 10 7 4 3 1 2 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=5 heap-size[A]=5 A[5]とA[1]を交換

(108)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 1 10 3 16 8 9 2 4 7 5 1 2 3 4 6 7 8 9 10 2 4 3 1 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=5 heap-size[A]=5 A[5]とA[1]を交換

(109)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 1 10 3 16 8 9 2 4 7 5 1 2 3 4 6 7 8 9 10 2 4 3 1 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=5 heap-size[A]=5-1=4 A[5]をヒープから取り除く

(110)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 1 10 3 16 8 9 2 4 7 5 1 2 3 4 6 7 8 9 10 2 4 3 1 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=5 heap-size[A]=4 MAX-HEAPIFY(A,1)を実行

(111)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 1 10 3 16 8 9 4 2 7 5 1 2 3 4 6 7 8 9 10 4 2 3 1 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=5 heap-size[A]=4 MAX-HEAPIFY(A,1)を実行 A[1]とA[2]を交換

(112)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 1 10 3 16 8 9 4 2 7 5 1 2 3 4 6 7 8 9 10 4 2 3 1 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=5 heap-size[A]=4 再びmax-ヒープが構成された

(113)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 1 10 3 16 8 9 4 2 7 5 1 2 3 4 6 7 8 9 10 4 2 3 1 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=4 heap-size[A]=4 A[1]とA[4]を交換

(114)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=4 heap-size[A]=4 A[1]とA[4]を交換

(115)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=4 heap-size[A]=4-1=3 A[4]をヒープから取り除く

(116)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=4 heap-size[A]=3 MAX-HEAPIFY(A,1)を実行する

(117)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 1 16 8 9 3 2 7 5 1 2 3 4 6 7 8 9 10 3 2 1 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=4 heap-size[A]=3 MAX-HEAPIFY(A,1)を実行する A[1]とA[3]を交換する

(118)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 1 16 8 9 3 2 7 5 1 2 3 4 6 7 8 9 10 3 2 1 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=4 heap-size[A]=3 再びmax-ヒープが構成された

(119)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 1 16 8 9 3 2 7 5 1 2 3 4 6 7 8 9 10 3 2 1 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=3 heap-size[A]=3 A[1]とA[3]を交換

(120)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=3 heap-size[A]=3 A[1]とA[3]を交換

(121)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=3 heap-size[A]=3-1=2 A[3]をヒープから取り除く

(122)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=3 heap-size[A]=2 MAX-HEAPIFY(A,1)を実行する

(123)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 2 1 7 5 1 2 3 4 6 7 8 9 10 2 1 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=3 heap-size[A]=2 MAX-HEAPIFY(A,1)を実行する A[1]とA[2]を交換

(124)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 2 1 7 5 1 2 3 4 6 7 8 9 10 2 1 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=3 heap-size[A]=2 再びmax-ヒープが構成された

(125)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 2 1 7 5 1 2 3 4 6 7 8 9 10 2 1 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=2 heap-size[A]=2 A[1]とA[2]を交換

(126)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=2 heap-size[A]=2 A[1]とA[2]を交換

(127)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=2 heap-size[A]=2-1=1 A[2]をヒープから取り除く

(128)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=2 heap-size[A]=1 MAX=HEAPIFY(A,1)を実行する

(129)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=2 heap-size[A]=1 再びmax-ヒープが構成された

(130)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A length[A]=10 i=1 heap-size[A]=1 ループ終了

(131)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  動作例 14 4 10 3 16 8 9 1 2 7 5 1 2 3 4 6 7 8 9 10 1 2 3 4 7 8 9 10 14 16 1 2 3 4 5 6 7 8 9 10 A 以上で配列が正しくソートされた

(132)

6.4 ヒープソート (The heapsort algorithm)

手続き H

EAPSORT  計算時間の吟味 したがって,手続き HEAPSORT 全体では O(nlgn) 時間を要する HEAPSORT(A) 1 BUILD-MAX-HEAP(A)

2 for i ← length[A] downto 2 3 do exchange A[1] ↔ A[i]

4 heap-size[A] ← heap-size[A]-1 5 MAX-HEAPIFY(A,1) Line 1 n=length[A] とすると BUILD-MAX-HEAP の呼び出しに O(n) かかる Line 2-3 for ループ MAX-HEAPIFY が n-1回呼び出される MAX-HEAIFY の 1回の呼び出しにO(lgn) かか るので,全体でO(nlgn)かかる

(133)

EXERCISE

6.4-1 図 6.4を参考にして,配列 A =〈5,13,2,25,7,17,20,8,4〉に対する HEAPSORT の動作 を示せ. (解答) 希望があればホワイトボードで

(134)

 EXERCISE

6.4-2

つぎのループ不変式を用いて,HEAPSORT の正当性を論ぜよ: Line 2-5 の for ループの各繰り返しの直前では以下が成立する.

部分配列 A[1..i] は A[1..n] の大きい方からi 個の要素を含む max-ヒープである.また,部分 配列 A[i+1..n] は A[1..n]の大きい方から n-i 個の要素をソートされた順序で含む.

(解答) 初期条件: ループの最初の繰り返しの直前では i=n である. 部分配列 A[1…i] は 配列 A そのものであり,直前の BUILD-MAX-HEAP の手続きによって max-ヒープになっている. ループ内条件:

A[1] と A[i] を交換し,heap-size[A] を1減少させたとき,A[i],つまり max-ヒープの根であっ た節点はヒープから取り除かれ,A[1] がヒープの新しい根となる.

このとき,A[1] 以外の節点は全て max-ヒープの根となっているため,

MAX-HEAPIFY(A,1) を1回呼び出すだけで max-ヒープ を再構成できる.

すなわち,部分配列 A[1…i] は A[1…n] の小さいほうから i 個の要素を含むmax-ヒープと

なっている

(135)

CONTENTS

6.1 ヒープ (Heap)

6.2 ヒープ条件の維持

(Maintaining the heap property)

6.3 ヒープの構成 (Building a heap)

6.4 ヒープソート (The heapsort algorithm)

(136)

6.5 優先度付きキュー (Priority queues)

優先度付きキュー (priority queue)

 要素の集合 S を保持するためのデータ構造  各要素はキー (key) と呼ばれる値を持つ  優先度付き max-キュー と 優先度付き min-キュー の2種類がある

優先度付き max-キュー (max-priority-queue) の操作

 INSERT(S,x): 集合 S に要素 x を挿入する  MAXIMUM(S): 最大のキーを持つ S の要素を返す  EXTRACT-MAX(S): 最大のキーを持つ S の要素を S から削除してその値を返す  INCREASE-KEY(S,x,k): 要素 x のキーの値を新しいキー値kに変更する ただし,k は x の現在のキー以上と仮定する

(137)

6.5 優先度付きキュー (Priority queues)

優先度付き max-キューの応用

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

(138)

6.5 優先度付きキュー (Priority queues)

優先度付き min-キュー

 INSERT, MINIMUM, EXTRACT-MIN, DECREASE-KEY 操作が可能

 事象駆動シミュレータで利用される キューに格納される要素はシミュレートされる事象であり,対応する 生起時刻がそのキーとなる 各ステップでは,EXTRACT-MINを用いて 次にシミュレートする事象を選択する 新しい事象が発生したとき INSERTを用いて優先度付き min-キューに挿入される 7 8 9 10 14 3 11 5 1 2 3 4 6 7 集合 S の優先度付き min-キュー 所持する値(生起時刻)が小さいほど 先にシミュレートされる

(139)

6.5 優先度付きキュー (Priority queues)

ハンドル (handle)

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

(140)

6.5 優先度付きキュー (Priority queues)

手続き H

EAP

-M

AXIMUM  MAXIMUM を O(1) 時間で実現する

アルゴリズム

max-ヒープの場合,集合の最大値が根に格納されているため, 単純に A[1] を出力するだけでよい

HEAP-MAXIMUM(A) 1 return A[1]

(141)

6.5 優先度付きキュー (Priority queues)

手続き H

EAP

-E

XTRACT

-M

AX

 EXTRACT-MAX を 実現する

 手続き HEAPSORT の for ループ本体(第3-5行)に類似している

アルゴリズム

HEAP-EXTRACT-MAX(A) 1 if heap-size[A] < 1

2 then error “heap underflow”

3 max ← A[1] 4 A[1] ← A[heap-size[A]] 5 heap-size[A] ← heap-size[A] – 1 6 MAX-HEAPIFY(A,1) 7 return max Line 1-2 if 文 heap-size[A] が1未満であれば, エラーメッセージを出力

(142)

6.5 優先度付きキュー (Priority queues)

手続き H

EAP

-E

XTRACT

-M

AX

 EXTRACT-MAX を 実現する

 手続き HEAPSORT の for ループ本体(第3-5行)に類似している

アルゴリズム

HEAP-EXTRACT-MAX(A) 1 if heap-size[A] < 1

2 then error “heap underflow”

3 max ← A[1] 4 A[1] ← A[heap-size[A]] 5 heap-size[A] ← heap-size[A] – 1 6 MAX-HEAPIFY(A,1) 7 return max Line 3-5 最大値 A[1]をmaxに代入,さらに A[1]にヒープの最後尾の要素を代 入し,heap-size[A] を1減少させて 最大値をヒープから取り除く

(143)

6.5 優先度付きキュー (Priority queues)

手続き H

EAP

-E

XTRACT

-M

AX

 EXTRACT-MAX を 実現する

 手続き HEAPSORT の for ループ本体(第3-5行)に類似している

アルゴリズム

HEAP-EXTRACT-MAX(A) 1 if heap-size[A] < 1

2 then error “heap underflow”

3 max ← A[1] 4 A[1] ← A[heap-size[A]] 5 heap-size[A] ← heap-size[A] – 1 6 MAX-HEAPIFY(A,1) 7 return max Line 6 残されたヒープが max-ヒープ条件 を満たすようにする

(144)

6.5 優先度付きキュー (Priority queues)

手続き H

EAP

-E

XTRACT

-M

AX

 EXTRACT-MAX を 実現する

 手続き HEAPSORT の for ループ本体(第3-5行)に類似している

アルゴリズム

HEAP-EXTRACT-MAX(A) 1 if heap-size[A] < 1

2 then error “heap underflow”

3 max ← A[1]

4 A[1] ← A[heap-size[A]]

5 heap-size[A] ← heap-size[A] – 1 6 MAX-HEAPIFY(A,1)

7 return max Line 7

(145)

6.5 優先度付きキュー (Priority queues)

手続き H

EAP

-E

XTRACT

-M

AX  EXTRACT-MAX を 実現する  手続き HEAPSORT の for ループ本体(第3-5行)に類似している

アルゴリズム

MAX-HEAPIFY の呼び出し(O(lgn))以外では定数時間しかかからないので, HEAP-EXTRACT-MAX の実行時間は O(lgn) である

HEAP-EXTRACT-MAX(A) 1 if heap-size[A] < 1

2 then error “heap underflow”

3 max ← A[1]

4 A[1] ← A[heap-size[A]]

5 heap-size[A] ← heap-size[A] – 1 6 MAX-HEAPIFY(A,1)

(146)

6.5 優先度付きキュー (Priority queues)

手続き H

EAP

-I

NCREASE

-K

EY

 INCREASE-KEY を実現する

 キー値を増やす優先度付きキューの要素配列の添字 i で表す

アルゴリズム

HEAP-INCREASE-KEY(A,i,key)

1 if key < A[i]

2 then error “new key is smaller than current key”

3 A[i] ← key

4 while i > 1 AND A[PARENT(i)] < A[i] 5 do exchange A[i] ↔ A[PARENT(i)] 6 i ← PARENT(i)

Line 1-2 if 文

入力されたキー値が,増やす対象 となるキー値より小さければエラー メッセージを出力

参照

関連したドキュメント

バックスイングの小さい ことはミートの不安がある からで初心者の時には小さ い。その構えもスマッシュ

原田マハの小説「生きるぼくら」

また、 NO 2 の環境基準は、 「1時間値の1 日平均値が 0.04ppm から 0.06ppm までの ゾーン内又はそれ以下であること。」です

①配慮義務の内容として︑どの程度の措置をとる必要があるかについては︑粘り強い議論が行なわれた︒メンガー

図一1 に示す ような,縦 お よび横 補剛材 で補 剛 された 板要素か らなる断面部材 の全 体剛性 行列 お よび安定係数 行列は局所 座標 系で求 め られた横補 剛材

の変化は空間的に滑らかである」という仮定に基づいて おり,任意の画素と隣接する画素のフローの差分が小さ くなるまで推定を何回も繰り返す必要がある

そこで本解説では,X線CT画像から患者別に骨の有限 要素モデルを作成することが可能な,画像処理と力学解析 の統合ソフトウェアである

4.4 前倒しおよび先送りの範囲の設定 前倒しの範囲は,管理目標値である健全度 2 から 3 未 満とし,先送りは健全度 2 から