「ヒープソート」の編集履歴（バックアップ）一覧はこちら

「ヒープソート」(2010/01/25 (月) 19:20:16) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

整列アルゴリズムのひとつ。
安定ではなく、平均的にはクイックソートよりもやや遅いが、最悪の場合でも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から使用するのが自然とのこと 

プログラミング掲示板「ソートロジック大会」なども参照のこと 
#asciiart(blockquote){
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
}