情報工学概論 (アルゴリズムとデータ構造) 第4回

ヒープソート O(n lg n) 時間アルゴリズム, in-place ヒープ (heap) と呼ばれるデータ構造を用いる ヒープはプライオリティキュー (priority queue) を効率よく実現する

7.1 ヒープ ヒープ：完全2分木とみなせる配列 木の各節点は配列の要素に対応 木は最下位レベル以外の全てのレベルの点が完全に詰まっている 最下位のレベルは左から順に詰まっている 16 2 4 8 1 7 14 9 10 3 5 6 16 14 10 8 7 9 3 2 4 1 5 6

ヒープを表す構造体 ヒープに後から要素を追加する場合があるとき，配列 A は大きいものを確保しておく typedef struct { int length; // 配列 A に格納できる最大要素数 int heap_size; // ヒープに格納されている要素の数 data *A; // 要素を格納する配列 } HEAP; ヒープに後から要素を追加する場合があるとき，配列 A は大きいものを確保しておく

length(H): 配列 A に格納できる最大要素数 heap_size(H): H に格納されているヒープの要素数 heap_size(H)  length(H) 木の根： A[1] 節点の添え字が i のとき 親 PARENT(i) = i / 2 左の子 LEFT(i) = 2 i 右の子 RIGHT(i) = 2 i + 1 木の高さは (lg n) 16 2 4 8 1 7 14 9 10 3 5 6

ヒープ条件 (Heap Property) 根以外の任意の節点 i に対して A[PARENT(i)]  A[i] つまり，節点の値はその親の値以下 ヒープの最大要素は根に格納される

ヒープの操作 HEAPIFY: ヒープ条件を保持する. BUILD_HEAP: 入力の配列からヒープを構成する. 線形時間. HEAPSORT: 配列をソートする. O(n lg n) 時間. EXTRACT_MAX: ヒープの最大値を取り出す. O(lg n) 時間. INSERT: ヒープに値を追加する. O(lg n) 時間.

7.2 ヒープ条件の保持 HEAPIFY(H,i): A[i] を根とする部分木がヒープになるようにする. ただし LEFT(i) とRIGHT(i) を根とする2分木はヒープと仮定. void HEAPIFY(HEAP *H, int i) { int l, r, largest, heap_size; data tmp, *A; A = H->A; heap_size = H->heap_size; l = LEFT(i); r = RIGHT(i); if (l <= heap_size && A[l] > A[i]) largest = l; // A[i] と左の子で大きい else largest = i; // 方をlargestに if (r <= heap_size && A[r] > A[largest]) // 右の子の方が大きい largest = r; if (largest != i) { tmp = A[i]; A[i] = A[largest]; A[largest] = tmp; // A[i]を子供と入れ替える HEAPIFY(H, largest); }

HEAPIFY(A,2) 1 HEAPIFY(A,4) 1 16 16 2 3 2 3 4 14 10 10 4 4 5 6 7 5 6 7 14 4 7 9 3 7 9 3 8 9 10 8 9 10 2 8 1 2 8 1 1 HEAPIFY(A,9) 16 2 3 14 10 4 5 6 7 8 7 9 3 8 9 10 2 4 1

HEAPIFYの実行時間 節点 i を根とする，サイズ n の部分木に対するHEAPIFYの実行時間 T(n) T(n)  T(2n/3) + (1) T(n) = O(lg n) 高さ h の節点での実行時間は 　　　O(h) 1 n/3 n/3 8 7 2 4 n/3

7.3 ヒープの構成 HEAPIFYでは左右の部分木がヒープである必要がある 全体をヒープにするには，2分木の葉の方からヒープにしていけばいい void BUILD_HEAP(HEAP *H, int n, data *A, int length) { int i; H->length = length; H->heap_size = n; H->A = A; for (i = n/2; i >= 1; i--) { HEAPIFY(H,i); }

4 1 3 2 16 9 10 14 8 7 A 4 14 8 2 7 16 1 9 3 10 5 6 4 14 8 2 7 16 1 9 3 10 5 6 HEAPIFY(A,5) HEAPIFY(A,4) 4 2 8 14 7 16 1 9 3 10 5 6 4 2 8 14 7 16 1 9 10 3 5 6 HEAPIFY(A,3) HEAPIFY(A,2)

4 2 8 14 1 7 16 9 10 3 5 6 16 2 4 8 1 7 14 9 10 3 5 6 HEAPIFY(A,1)

計算量の解析 O(lg n) 時間のHEAPIFYが O(n) 回 ⇒O(n lg n)時間 (注: これはタイトではない) 高さ h の節点でのHEAPIFYは O(h) 時間 n 要素のヒープ内に高さ h の節点は高々n/2h+1個

7.4 ヒープソート まずヒープを作る すると最大要素が A[1] に入る A[1]とA[n]を交換すると，最大要素がA[n]に入る ヒープのサイズを1つ減らしてヒープを維持する void HEAPSORT(int n, data *A) { int i; data tmp; HEAP H; 　BUILD_HEAP(&H,n,A,n); for (i = n; i >= 2; i--) { tmp = A[1]; A[1] = A[i]; A[i] = tmp; // 根と最後の要素を交換 H.heap_size = H.heap_size - 1; HEAPIFY(&H,1); }

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

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

1 1 2 1 2 1 3 2 3 4 7 8 9 4 7 8 9 10 14 16 10 14 16 1 2 3 4 7 8 9 10 14 16 A

計算量 BUILD_HEAP: O(n) 時間 HEAPIFY: O(n lg n) 時間 全体で O(n lg n) 時間

7.5 プライオリティキュー 要素の集合 S を保持するためのデータ構造 各要素はキーと呼ばれる値を持つ 次の操作をサポートする INSERT(S,x): S に要素 x を追加する MAXIMUM(S): 最大のキーを持つ S の要素を返す EXTRACT_MAX(S): 最大のキーを持つ S の要素を削除し，その値を返す

応用：計算機のジョブ割り当て 実行中のジョブと優先順位をプライオリティキューに保持 ジョブが終了または割り込み発生時に，一時中断しているジョブの中から最大の優先順位のジョブを選び実行 (EXTRACT-MAX) 新しいジョブはプライオリティキューに挿入される (INSERT)

ヒープによるプライオリティキューの実現 MAXIMUM(S): A[1] を返す (O(1)時間) data EXTRACT_MAX(HEAP *H) // O(lg n) 時間 { data MAX, *A; A = H->A; if (H->heap_size < 1) { printf("ERROR ヒープのアンダーフロー\n"); exit(1); } MAX = A[1]; A[1] = A[H->heap_size]; H->heap_size = H->heap_size - 1; HEAPIFY(H,1); return MAX;

void INSERT(HEAP *H, data key) // O(lg n) 時間 { int i; data *A; A = H->A; H->heap_size = H->heap_size + 1; if (H->heap_size > H->length) { printf("ERROR ヒープのオーバーフロー\n"); exit(1); } i = H->heap_size; while (i > 1 && A[PARENT(i)] < key) { A[i] = A[PARENT(i)]; i = PARENT(i); A[i] = key;

9. 線形時間のソーティング 今までのソートアルゴリズム この節でのソートアルゴリズム 入力要素の比較のみに基づく 比較ソート (comparison sort) と呼ぶ 例：マージソート，ヒープソート，クイックソート 計算量：(n lg n) この節でのソートアルゴリズム 比較以外の演算を用いる 例：計数ソート，基数ソート，バケットソート 計算量：O(n) (線形時間)

9.2 計数ソート (counting sort) n 個の各入力要素が 1 から k の範囲の整数であると仮定 (k: ある整数) k = O(n) のとき，計数ソートは O(n) 時間 基本的なアイデア 各入力要素 x に対し，x より小さい要素の数を決定 その要素数から x の出力配列での位置が決まる 例： x より小さい数が17個 ⇒ x の出力位置は18 複数の要素が同じ値を持つ場合に対応する必要あり

計数ソートのプログラム A[1..n], B[1..n]: 入出力配列 C[1..k]: 補助的な配列 void COUNTING_SORT(int *A, int *B, int *C, int n, int k) { int i,j; for (i=1; i<=k; i++) C[i] = 0; for (j=1; j<=n; j++) C[A[j]] = C[A[j]] + 1; // C[i] は i に等しい要素の個数を含む for (i=2; i<=k; i++) C[i] = C[i] + C[i-1]; // C[i] は i 以下の要素の個数を含む for (j=n; j>=1; j--) { B[C[A[j]]] = A[j]; C[A[j]] = C[A[j]] - 1; }

1 2 3 4 5 6 7 8 A 3 6 4 1 3 4 1 4 1 2 3 4 5 6 for (j=1; j<=n; j++) C[A[j]] = C[A[j]] + 1; // C[i] は i に等しい要素の個数を含む C 2 2 3 1 1 2 3 4 5 6 for (i=2; i<=k; i++) C[i] = C[i] + C[i-1]; // C[i] は i 以下の要素の個数を含む C 2 1 2 4 2 3 7 5 4 6 7 8 7 for (j=n; j>=1; j--) { B[C[A[j]]] = A[j]; // A[j]以下がC[A[j]]個 C[A[j]] = C[A[j]] - 1; } 1 2 3 4 5 6 7 8 B 1 1 3 3 4 4 4 6

計数ソートの計算時間 C の初期化: O(k) 時間 頻度の計算: O(n) 時間 累積頻度の計算: O(k) 時間 全体で O(k + n) 時間 k = O(n) のとき，全体で O(n) 時間 比較ソートの下限 (n lg n) を下回る

安定なソート 同一の値は入力と出力で同じ順序になる 付属データをキーに従ってソートする場合に重要 1 2 3 4 5 6 7 8 A 3 6 B 1 1 3 3 4 4 4 6

9.3 基数ソート (radix sort) 数の集合をある桁に従って分割する機械がある この機械を用いて d 桁の数 n 個をソートしたい 329 355 457 436 657 720 839 329 457 657 839 436 720 355

まず最上位桁でソート (分割) し，それぞれを再帰的にソートすることを考える 大量の部分問題が生成される 解：最下位桁からソートする⇒基数ソート まず最下位桁に従ってソート 次に下から2桁目に従ってソート d 桁目まで繰り返す

329 457 657 839 436 720 355 720 355 436 457 657 329 839 720 329 436 839 355 457 657 329 355 436 457 657 720 839 基数ソートでは各桁のソートは安定である必要がある

基数ソートの擬似コード RADIX_SORT(A,d) for (i=1; i<=d; i++) 実行時間の解析 各桁が 1 から k の範囲として計数ソートを使用 d パスあるので (d(n+k)) 時間 d が定数で k = O(n) ならば，全体で O(n) 時間

比較ソートでは1つの数あたりほぼ lg n = 20 回の操作が必要となる 基数ソートでは，これらの数を4桁の216進数と思うと，4回のパスでソートできる 計数ソートを用いる基数ソートはin-placeではない メモリが高価な場合はクイックソートなどの方が良い

9.4 バケットソート (bucket sort) 入力： [0,1) の実数 n 個．一様分布と仮定 アイデア 各バケットを独立にソート 0.15 0.51 0.45 0.75 0.80 [0,.2) [.2,.4) [.4,.6) [.6,.8) [.8,1.0)

バケットソートの動作 A[1..n]: 入力配列 B[0..n1]: バケット (リストの配列) BUCKET_SORT(A,n) for (i = 1; i  n; i++) A[i] をリスト B[nA[i]] に挿入する for (i = 0; i  n1; i++) リスト B[i] を挿入ソートでソートする リスト B[0], B[1],...,B[n1] を順に連接する

A B 1 .78 2 .17 1 .17 .17 .12 3 .39 2 .26 .23 .21 .26 .26 .21 .26 .21 .23 4 .26 3 .39 5 .72 4 6 .94 5 .21 .68 7 6 8 .12 7 .78 .72 .78 9 .23 8 10 .68 .94 9 .12 .17 .21 .23 .26 .39 .68 .72 .78 .94 各リストを挿入ソートでソート

アルゴリズムの正当性 A[i] と A[j] が同じバケットに入る場合 A[i] と A[j] が異なるバケットに入る場合 各バケットは挿入ソートでソートされるのでOK A[i] と A[j] が異なるバケットに入る場合 バケット B[i’], B[j’] (i’ j’)に入るとする アルゴリズムの最後で B のリストは結合される B[i’] の要素は B[j’] の要素よりも前に現れる よって，出力中で A[i] は A[j] よりも前に現れる つまり， A[i]  A[j] を示せばよい

A[i]  A[j] と仮定して矛盾を導く． となり，i’ j’ に矛盾する

実行時間の解析 挿入ソート以外の部分は O(n) 時間 Ni: バケット B[i] に入れられる要素数を表す確率変数 バケット B[i] の要素をソートするのに必要な平均時間 = E[O(Ni2)] = O(E[Ni2]) 全てのバケット中の要素をソートする時間は

確率変数 Ni の分布 要素数 = バケット数 = n ある要素が B[i] に入る確率は p = 1/n Ni = k となる確率は2項分布 B(k;n,p) に従う E[Ni] = np = 1, Var[Ni] = np(1p) = 11/n E[Ni2] = Var[Ni] + E2[Ni] = 21/n = (1) 以上より，挿入ソートに必要な時間は O(n) バケットソートは線形時間で動作する