アルゴリズムイントロダクション 6 章「ヒープソート」
数学的基礎とデータ構造 (アルゴリズムイントロダクション)の 6章
6.1-1
min=2^h
max=2^(h + 1) - 1
6.1-2
n=min=2^h なら lgn = h
n=max=2^(h + 1) -1 なら lg(n + 1) = h + 1 → h = lg(n + 1) - 1 < lg(n + 1) 。
6.1-3
部分木の根以外に最大値があるとすると、その親との heap の関係が崩れている事になるので矛盾する。
6.1-4
色々と試してみたが leaf node の何れかの位置に来るようだ。
6.1-5
Yes.
6.1-6
No.
6 と 7 の親子関係がおかしい。
6.1.-7
leaf node の一つ上の階層の右端は n / 2 を超えない整数の添え字。
6.2-1
ノートに書いた。添え字は 1 origin か。
6.2-2
MIN-HEAPFIY(A, i)
if i == i
return
else
p <- parent(i)
if A[i] < p
swap
MIN-HEAPFIY(A, i/2
end
end
6.2-3
何もしない。
6.2-4
leaf node なので何もない。
6.2-5
MAX-HEAPFIY(A, i)
for (k = i; k != size(A);) {
// 素の MAX-HEAPFIY の中身
k=largest
}
6.2-6
最悪のケースは一番小さな値が root にあること。
その場合値の交換は木の高さ lg(n) 回起こる。
6.3-1
ノートに描いた。
6.3-2
leaf にある大きな物を上に持ってくる機会を作るため。
6.3-3
高さ h までに 2^h - 1 ということ。
6.4-1
ノートに描いた。
6.4-2
i = 1 のときは右の部分配列は空であるから明らかに成り立つ。
i = k で成り立つとすると
ループ3 にと max heap の性質により右の部分配列は不変表明を満たすようになる
ループ4, 5 によって左の部分配列は max heap となり不変表明を満たす。
6.4-3
減少順 nlogn 。増加順 n 。
6.4-4
最悪実行時間は全ての要素が、既存のヒープのルートからノードに移動する場合に発生。
logn 回の交換が n 要素に対して起こるので nlogn
6.5-1,2
ノートに描いた。
6.5-3
HEAP-MINIMUM(A) return A[1] HEAP-EXTRACT-MIN(A) if heap-size[1] < 1 then error [heap underflow] min <- A[1] A[1] <- A[heap-size[A]] heap-size[A]-- MIN-HEAPIFY(A, 1) return min HEAP-DECRESE(A, i, key) if key > A[i] then errro A[k] <- key while i > 1 && A[Parent(i)] > A[i] swap i <- Parent(i) MIN-HEAP-INSERT(A,Key) heap-size(A)++ A[heap-size(A)] <- +infinity HEAP-DECRESE(A, heap-size(a), Key)
6.5-4
HEAP-INCREASE-KEY で新しいキーが必ず現在のキーよりも大きい事を保証するため。
つまり heap が必ず成り立っている事を保証するため。
6.5-5
6.5-4 で見たように HEAP-INCREASE-KEY の呼び出し直前において heap が成り立っているので不変表明は成り立つ。
任意の i で成り立つと仮定すると A[i] と A[parent[i]] を入れ替える事で parent[i] と parent[parent[i]] 以外で max heap が成り立つ。
6.5-6
FIFOキュー:最初に挿入した物を優先度を大きく。
スタック：逆。
6.5-7
HEAP-DELETE(A, i) swap(A[heap-size(A)], i) heap-size(A)-- MAX-HEAPFIY(A, i)
6.5-8
k 個のリストそれぞれの一番小さな値を取り出し min-heap を作り、ソート済みリストにマージする。
計算量が O(nlgk) になるかが微妙。
数学的基礎とデータ構造 (アルゴリズムイントロダクション)
posted with amazlet at 09.12.06
