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() を呼び出すことで, ヒープ条件を保ち ながら要素の個数を一つずつ減らすことができる. さらに, 根はその ヒープの最大要素で, それが順に空いた場所に移されるので, 配列 としては, 後ろから大きい順に整列することになる.
注意: クイックソートは平均 , 最悪 のアルゴリズムで, ヒープソートは最悪でも だが通常はクイックソートが 使われる場合が多い. これは, クイックソートに比べてヒープソートが 複雑であるため, ほとんどの入力に対してはクイックソートの方が 実際には高速なためである. しかし, 前節, 本節で与えたプログラム 例がそれぞれ最良とは限らないので, 双方比較してどちらが高速か 分からない. 興味がある人は, 同じ例で比較してみたり, あるいは より効率の高い実装を行ってみるとよい.