ソフトウェア工学-akita.pptVIP

４－３：高度なソートアルゴリズム②（データ構造にもとづくソート） ヒープソート ヒープソートの方針 ヒープとは ２分木 高々２つ子しかない木。 左と右の子を区別する。 木に関する用語 深さ：根までの道の長さ 高さ：木中の最大の深さ 完全２分木 ヒープの形 ヒープ番号と配列での実現 ヒープにおける親子関係 ヒープにおける挿入 挿入の例 練習 ヒープにおける削除 削除の例 ヒープソートの動き前半（ヒープへ値挿入） ヒープソートの動き後半（ヒープからの最小値削除） 練習 ヒープソートの実現 ヒープソートの計算量 単一配列でのヒープソート 単一配列に変更する方針 ヒープ条件の変更 ヒープ化（ヒープソート前半） 最大値の削除とソート ヒープソート２の動き後半２ 練習 単一配列ヒープの実現 単一配列ヒープソートの計算量 ヒープ化の高速化 ヒープ化の高速化におけるアィディア イメージ 高速ヒープ化の動き ヒープソートの計算量 void heap_sort() { int i; /* カウンタ */ 　　　make_heap();/*空のヒープの作成*/ /* ヒープ挿入 */ for(i=0;in;i++){ insert_heap(A[i]); 　　　} /*ヒープからのデータの取り出し*/ for(i=0;in;i++){ A[i]=get_min(); } return ; } 細かい部分 は省略します。 命題HP３（ヒープソートの正当性） 証明 ヒープの削除（get_min())により、 繰り返し最小値を求められることに注意すれば、 帰納法により証明できる。 ヒープソートにより、配列はソートされる。 最悪時間量 のアルゴリズム ヒープへのデータ挿入 操作insert_heap(A) １回あたり、時間量 n回行うので、時間量 整列（最小値の削除の反復） 操作get_min() １回あたり、時間量 n回行うので、時間量 根が最大値になるように変更する。 最大値を取り出して、最後のデータにする。 先頭から順にヒープに挿入し、データ全体をヒープ化する。 １ 0 2 5 ４ ２ １ 3 13 ８ 9 3 4 5 6 7 方針 全ての節点において、親の値が子の値より大きい （ヒープ条件） A 0 1 2 3 4 5 7 6 ５ ３ ８ １ ４ 13 9 ２ 配列 ヒープ ５ ３ ８ １ ４ 13 9 ２ ヒープ 未ヒープ 5 ５ ３ ８ １ ４ 13 9 ２ ヒープ 未ヒープ 5 3 0 １ 0 配列 ヒープ A 0 1 2 3 4 5 7 6 ５ ３ ８ １ ４ 13 9 ２ ヒープ 未ヒープ 3 １ 0 ８ 5 2 ちょっと省略 １ 0 2 5 ４ ２ １ 3 13 ８ 9 3 4 5 6 7 A 0 1 2 3 4 5 7 6 ５ ３ ８ １ ４ 13 9 ２ ヒープ １ 0 2 5 ４ ２ １ 3 13 ８ 9 3 4 5 6 7 A 0 1 2 3 4 5 7 6 ５ ３ ８ ４ 13 9 ２ ヒープ 最大要素を、ヒープから削除し 後ろに挿入 A 0 1 2 3 4 5 7 6 ５ ３ ８ １ ４ 13 9 ２ ヒープ １ 0 2 5 ４ ２ １ 3 ８ 9 3 4 5 6 １ ソート済 A 0 1 2 3 4 5 7 6 ５ ３ ８ １ ４ 13 9 ２ ヒープ １ 0 2 5 ４ ２ １ 3 ８ 3 4 5 ソート済 ちょっと省略 A ５ ３ ８ １ ４ 13 9 ２ ソート済 １ ３ ５ ８ １１ １６ ２１ ２５ 次の配列を、単一配列ヒープソートを用いてソートするとき、 配列の動きをシミュレートせよ。 void heap_sort() { int i; /* カウンタ */ 　　　make_heap();/*空のヒープの作成*/ /* ヒープ化 */ for(i=0;in;i++){ insert_heap(A[i]); 　　　} /*ヒープからのデータの取り出し*/ for(i=n-1;i=0;i--){ A[i]=get_max(); } return ; } 仔細省略、 ヒープの動作 も変更する 必要がある。 最悪時間量 のアルゴリズム ヒープ化 操作insert_heap(A) １回あたり、時間量 n回行うので、時間量 整列（最小値の削除の反復） 操作get_max() １回あたり、時間量 n回行うので、時間量 ヒープ化、整列は、１回づつ行われるので、 ヒープをボトムアップ