酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2013年7月2日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html

ヒープソート（１８５ページ） ソート前 ソート済み i length-1 挿入法では、ソート未完了の列から線形探索により i length-1 挿入法では、ソート未完了の列から線形探索により 次の挿入対象を探していた。 配列[i]の位置に、配列[0]から配列[i]までの間の 最大値を置くことを、配列末端から繰り返せばソートできる。 ただし、線形探索を毎回繰り返すのは効率が悪い。 比較回数の合計がおおむね

部分順序付き木（１８６ページ） 挿入法におけるソート前データ列から探索しやすいように データの置き方を工夫する。これまでの探索木のような順序木ではなく、 部分順序付き木というものにデータを置く。 データを置くルールは、親の値が子の値より小さくないこと。 そうすると、根には最大値が来る。 23 21 19 17 15 11 7 9 13 5 3 1 二分探索木ではないので、 このような配置でも問題ない

部分順序付き木の組み替え1 (原理的•187ページ) c a b d a c b d a f b e b a f e

ソートのための部分順序付き木 ソートのために特別なデータ構造を定義し使用することは非効率。 これを配列に置くことを考える。 木の高さがバランスしていないとソート途中の探索も非効率。 配列上のデータの並びから、一律に木の形を定義する。 配列[i]の子は、根を配列[0]とすると、配列[2*i+1]配列[2*i+2]になる。 教科書と違うことに注意。 23 21 19 1 2 17 15 11 7 3 4 5 6 9 3 13 5 1 7 8 9 10 11

配列に木を表現したことにする（１８８ページ） 13 21 19 9 5 11 7 17 3 15 23 1 根 ２段目 ３段目 ４段目 根　　　２段目　　　　３段目　　　　　４段目 木にバランスよくデータを置くには 配列上にあるデータ列を区切って 木に対応付けるとよい。 でも、部分順序付き木ですらない。 （このページの現状では…） 13 21 19 9 5 11 7 17 3 15 23 1

部分順序付き木の組み替え2 (ソート目的•190ページ) 木のバランスを崩さないように 頂点ｆを根に動かした。 根を取り除いた。 f e c a b d e c a f b d 根は配列[0]、fは配列の最後にある。 aとfを入れ替え e c d a b f e c f a b d dとfを入れ替え

（１８９ページから１９１ページ、手続きdownheap） 17 9 11 21 23 5 7 3 19 1 13 15 最初のヒープを作る （１８９ページから１９１ページ、手続きdownheap） 17 9 21 23 13 11 5 7 3 19 1 15 13 23 21 23 21 13 17 9 23 5 13 15 配列にデータを置いているので、 葉とその親の位置は計算で 一意に求まる。 そこで、葉に近いところから、 部分順序付き木のルールに 従ってデータをそろえていく。 （１９２ページ） 17 9 21 23 13 11 5 7 3 19 1 15 9 17 21 5 23 11 13 7 3 19 1 15 9 17 13 5 23 11 21 7 3 19 1 15 9 17 21 5 23 11 15 7 3 19 1 13 9 17 23 5 21 3 15 9 17 3 5 23 15

探しながら挿入法のようにソート（１９２・１９３ページ） 最大値を部分順序付き木から 探しながら挿入法のようにソート（１９２・１９３ページ） 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 17 9 11 21 23 5 7 3 19 1 13 15 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 5 13 3 9 17 15 21 1 11 7 19 23 最大値をソート済み列に加える。 未ソートデータ列の最後のデータを根に置く。 部分順序付き木になるようにデータを移動する。

lengthが奇数なら、2*x+2=length-1, x=(length-3)/2 public class HeapSort { private final static <E extends Comparable<E>> int downheap(E[] array, int root, int last){ int n = 0; E v = array[root]; while(true){ int j = 2*root+1; // 左の子 if(j > last) break; // 左の子がない(もちろん、右にも子がない)場合は終了 if(j != last){ // 両方の子がある n++; if(array[j+1].compareTo(array[j]) > 0) j++; // 右の子 > 左の子、大きいほうを選ぶ } if(v.compareTo(array[j]) >= 0) break; array[root] = array[j]; root = j; // 上→下 array[root] = v; return n; public static <E extends Comparable<E>> int sort(E[] array) { for(int i = array.length/2 - 1; i >= 0; i--) n += downheap(array, i, array.length - 1); //下→上 for(int i = array.length - 1; i > 0; i--){ E temp = array[0]; array[0] = array[i]; array[i] = temp; n += downheap(array, 0, i-1); }} xの子は2*x+1と2*x+2にあるので、 lengthが奇数なら、2*x+2=length-1, x=(length-3)/2 lengthが偶数なら、2*x+1=length-1, x=(length-2)/2

兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 18 private final static String[] test_data_string = { "東京", "北海道", "高知", "兵庫", "鹿児島", "沖縄", "青森"}; private final static Integer[] test_data_int = { 47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10}; public static void main(String[] args) { int n; StringBuffer sb = new StringBuffer(); String[] data1 = test_data_string.clone(); n = sort(data1); for (String e : data1) { sb.append(e).append(", "); } sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n'); Integer[] data2 = test_data_int.clone(); n = sort(data2); for (Integer e : data2) { System.out.print(sb.toString()); 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 18 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 66

ヒープソートの計算量(193ページ) 完全２分木とすると、downheapで調べる 段数は、部分木の範囲ごとに次のようになる。 全体では、 全体では、　　　　　　　　　　　　　　　　　　 　　　　　　とすると 　　　　　　　　　　　　　だったので、 初期操作にはO(n)必要。 1段　n/4からn/2 2段　n/8からn/4 3段　n/16からn/8 4段　n/32からn/16

ヒープソートの計算量（つづき） 最大値を一つづつ取り出して、ソートする 作業では、 最大値を取り出す作業が 回 　最大値を取り出す作業が　　回 　その後で木を作り替える作業が　　　　　回 　つまり　　　　　　　　になる。　　　　　

問題: 部分順序付き木を作り替える過程を記入しなさい。 アルゴリズムとデータ構造　演習 学生番号：　　　　　　　　　　　名前：　　　　　　　　　　　　　　　 問題: 部分順序付き木を作り替える過程を記入しなさい。 23 21 19 1 17 15 11 7 21 19 9 3 13 5 1 17 15 11 7 1. 最初期のヒープ 9 3 13 5 23 2. 最大値を取り出し、未ソート配列より 　　値を取り出し、根に置く。 23 3. 途中経過

6. データ１個のソートが終わり、木の再構成も終わった状態。 23 4. 途中経過 23 21 5. 途中経過 17 19 9 15 11 7 1 3 13 5 23 6. データ１個のソートが終わり、木の再構成も終わった状態。

5 17 19 9 15 11 7 1 3 13 21 23 7. 2個目のデータのソート開始。 21 23 途中経過(必要に応じて使うこと） 21 23 途中経過(必要に応じて使うこと）

データ２個のソートが終わり、木の再構成も終わった状態。 21 23 途中経過(必要に応じて使うこと） 21 23 途中経過(必要に応じて使うこと） 21 23 データ２個のソートが終わり、木の再構成も終わった状態。