ヒープソート - abwiki @ ウィキ (ActiveBasic非公式wiki)

整列アルゴリズムのひとつ。
安定ではなく、平均的にはクイックソートよりもやや遅いが、最悪の場合でもO(nlogn)である。

ヒープソートは、未整列データをヒープ構造に構成し、その"根"を順次取り出すことで整列を行う。ヒープ構造は、"親"に対して2つの"子"を持ち、昇順の場合a[i]>a[2i]かつa[i]>a[2i+1]を満たす構造であるため、その"根"は未整列データの最大値となる（降順の場合は"根"が最小になるようにヒープ構造を構築する）。昇順整列におけるヒープ構造の構築は下記方法で行うが、親子関係はたかだかlog2(n)程度しか続かない。
ある値a[i]に着目し、その"子"a[2i]とa[2i+1]を比較して大きいほうをa[j]とする
a[i]とa[j]を比較し、a[i]<a[j]であればこれを交換する
交換した場合a[i]の新しい場所で、その"子"との比較・交換を行う
上記比較交換を、交換できなくなるないし"子"がなくなるまで、全て行う

ヒープソートは配列添え字を1から使用するのが自然とのこと

プログラミング掲示板「ソートロジック大会」なども参照のこと

TypeDef keytype = Integer
Sub heapsort(n As Integer, a As *keytype)
Dim i As Integer, j As Integer, k As Integer
Dim x As keytype
k = n / 2
Do
i = k
x = a[i]
j = 2 * i
While j <= n
If j < n And a[j] < a[j + 1] Then j = j + 1
If x >= a[j] Then Exit While
a[i] = a[j]
i = j
j = 2 * i
Wend
a[i] = x
k = k - 1
Loop While k > 0

While n > 1
x = a[n]
a[n] = a[1]
n = n - 1
i = 1
j = 2 * 1
While j <= n
If j < n And a[j] < a[j + 1] Then j = j + 1
If x >= a[j] Then Exit While
a[i] = a[j]
i = j
j = 2 * i
Wend
a[i] = x
Wend
End Sub