ヒープソート

前節の downheap() を用いて次のようなプログラムを書くことが できる.

def heapsort(L) {
    N = length(L);
    A = newvect(N+1);
    for ( I = 1; I <= N; I++, L = cdr(L) ) A[I] = car(L);
    /* heap construction; A[[N/2]+1],...,A[N] are leaves */
    for ( K = idiv(N,2); K >= 1; K-- ) downheap(A,K,N);
    /* retirement and promotion */
    for ( K = N; K >= 2; K-- ) {
        swap(A,1,K);
        downheap(A,1,K-1);
    }
    for ( I = 1, R = []; I <= N; I++ ) R = cons(A[I],R);
    return R;
}

このプログラムは, 与えられたリスト $L$ をソートしたリストを返す. ヒー プの構成は, 子を持つ最後の要素である $A[\lfloor N \rfloor]$ から順に, その要素の子孫からなる 2 分木に対して downheap() を呼び出すこと で行われる. 現在選ばれている要素に対し, 子を根とする木がヒープをなすことは 数学的帰納法による.

$A[\lfloor N \rfloor + 1]$ 以降は葉なので, それらを根とする 木に対しては自動的にヒープ条件がなりたっていることから帰納法の最初の ステップが正当であることがわかる.

出来上がったヒープに対して, 根と, その時点における最後尾の要素を 入れ換えて, downheap() を呼び出すことで, ヒープ条件を保ち ながら要素の個数を一つずつ減らすことができる. さらに, 根はその ヒープの最大要素で, それが順に空いた場所に移されるので, 配列 としては, 後ろから大きい順に整列することになる.

例 18.1   $L=[11,9,5,15,7,12,4,1,13,3,14,10,2,6,8]$ の ヒープソートによるソーティング. http://www.math.kobe-u.ac.jp/noro/hsdemo.pdf にヒープ構成およびソーティング (retirement and promotion) の経過が示されている.

定理 18.1   ヒープソートの計算量は $O(N \log_2 N)$ である.

問 18.3   定理を証明せよ. (ヒント : $N=2^n-1$ で考えてよい. 高さ, すなわち 頂点から最下段までのレベルの差が $k$ の downheap() 一回にどれだけ比較が必要か考える. あとは, ヒープ構成, 整列 それぞれに, どの高さの downheap() が何回必要か数えればよい. )

注意 18.1   クイックソートは平均 $O(N \log_2 N)$, 最悪 $O(N^2)$ のアルゴリズムで, ヒープソートは最悪でも $O(N \log_2 N)$ だが通常はクイックソートが 使われる場合が多い. これは, クイックソートに比べてヒープソートが 複雑であるため, ほとんどの入力に対してはクイックソートの方が 実際には高速なためである. しかし, 前節, 本節で与えたプログラム 例がそれぞれ最良とは限らないので, 双方比較してどちらが高速か 分からない. 興味がある人は, 同じ例で比較してみたり, あるいは より効率の高い実装を行ってみるとよい.