: 1/28 : レポートについて
: 1/21 : 整列 その
: downheap()
前節の 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;
}
このプログラムは, 与えられたリスト
をソートしたリストを返す. ヒー
プの構成は, 子を持つ最後の要素である
から順に,
その要素の子孫からなる 2 分木に対して downheap() を呼び出すこと
で行われる. 現在選ばれている要素に対し, 子を根とする木がヒープをなすことは
数学的帰納法による.
以降は葉なので, それらを根とする
木に対しては自動的にヒープ条件がなりたっていることから帰納法の最初の
ステップが正当であることがわかる.
出来上がったヒープに対して, 根と, その時点における最後尾の要素を
入れ換えて, downheap() を呼び出すことで, ヒープ条件を保ち
ながら要素の個数を一つずつ減らすことができる. さらに, 根はその
ヒープの最大要素で, それが順に空いた場所に移されるので, 配列
としては, 後ろから大きい順に整列することになる.
定理 18.1
ヒープソートの計算量は

である.
問 18.3
定理を証明せよ. (ヒント :

で考えてよい. 高さ, すなわち
頂点から最下段までのレベルの差が

の
downheap() 一回にどれだけ比較が必要か考える. あとは, ヒープ構成, 整列
それぞれに, どの高さの
downheap() が何回必要か数えればよい. )
注意 18.1
クイックソートは平均

, 最悪

のアルゴリズムで,
ヒープソートは最悪でも

だが通常はクイックソートが
使われる場合が多い. これは, クイックソートに比べてヒープソートが
複雑であるため, ほとんどの入力に対してはクイックソートの方が
実際には高速なためである. しかし, 前節, 本節で与えたプログラム
例がそれぞれ最良とは限らないので, 双方比較してどちらが高速か
分からない. 興味がある人は, 同じ例で比較してみたり, あるいは
より効率の高い実装を行ってみるとよい.
Masayuki Noro
平成14年2月25日