アルゴリズムとデータ構造 第8回 ソート（3）
本日の講義内容 heap 配列によるheap heap sort
heap 2分木で、そのノードが必ず子の値以上になっているものをheapという。heapでは、そのrootは必ず全体の最大値となっている。
配列によるheap 配列a[]の第0を、rootとみなす。 その子は1,2であり、１の子は3,4 2の子は 5,6, その子は1,2であり、１の子は3,4 2の子は 5,6, 3の子は7,8 4の子は9,10 5の子は11,12 6の子は13,14 ............. このようにして、配列を２分木とみなすことができる。
親子のindexの関係 親a[i]の 左の子=a[i*2+1] 右の子=a[i*2+2] 子a[i]の親は a[(i-1)/2] である。. この関係を使うと、１個の配列を２分木とみなす ことがいつでもできる。
例 a[10]の内容が 10 8 7 6 5 4 2 3 1 3 はheapである。（確認せよ！） 10 8 7 6 5 4 2 3 1 3 はheapである。（確認せよ！） 先頭がroot, その後の２個がlevel 1, 4個がlevel 2, 8個がlevel3,... となっている。
heap化 配列aの位置nから下の部分木を考える。 位置nのデータ以外の下方にあるデータは すでにheapであるとする。これを、heapにするには位置nのデータを子供たちの値と比較して データを交換しながら下にたどっていけばよい。 これを実行する関数を void downheap(int a[],int n,int right) とする。ただし、rightはheap化する範囲の 右端とする。
downheapのアルゴリズム 1. a[n]の子をnl, nrとしよう。 2. nl>rightならば終了 3. nr>rightのときは（nl==rightである) a[n]>=a[nl]なら終了 a[n]<a[nl]なら交換して終了 4. a[nl]<a[nr]ならc=nr そうでなければc=nlとする。 5. a[n]>=a[c]ならば終了 そうでなければa[n],a[c]を交換して n=cにして手順１に戻る。
配列をheap化する 配列a[]の大きさをsize, right=size-1とする。 rightの親をnとする。 このとき、nの右側の要素はすべて子を持たないから葉になっている。つまり、nより下の木は そのままheapである。 従って、downheap(a,n,right)を呼び出して n以下をheapにする。 以下、nを減らして0まで繰り返し downheapを実行すれば、配列全体がheap になる。
heap sortアルゴリズム 1. a[]を前の手順でheap化する。 2. このときa[0]が全体の最大値となっているので、a[0]とa[right]を入れ替える。 3. rightは確定したので、righを１減らす。 4. a[0]以外は、heapなので downheap(a,0,right)を実行する。 5. right>0ならば、手順２に戻る。
heap sortの速度 heapの再構成は、２分木をたどっていくので O(log n)回の比較と交換ですむ。 これが、n回行われるのでたかだかO(n log n) ですむ。 最初に行う配列全体のheap化は n=2^kとすると 2^(k-1)+2*2^(k-2)+3*2^(k-3)+..... <= k2^(k-1)=n/2 log n となるので 結局 O(n log n)の速度である。
heap sortの特徴 最大値を求めて、交換を繰り返すので選択ソートの高速版ともいえる。 アルゴリズムは、やや複雑だが美しい。 作業領域を必要としない。 安定ではない。