Pseudo Code
Coddyの「ヒープソート - DSAシリーズ」コースのレッスン 4/9。
siftDown(array, i, size):
loop:
largest = i
left = 2*i + 1
right = 2*i + 2
if left < size and array[left] > array[largest]: largest = left
if right < size and array[right] > array[largest]: largest = right
if largest == i: stop
swap array[i] and array[largest]
i = largest
heapSort(array):
n = length(array)
for i from n/2 - 1 down to 0: # 最大ヒープを構築
siftDown(array, i, n)
for end from n-1 down to 1: # 最大値を繰り返し抽出
swap array[0] and array[end]
siftDown(array, 0, end)- siftDown は、最大ヒープの特性が復元されるまで、小さすぎる親をその大きな子よりも下に押し下げます。
sizeは、配列のどの範囲がまだヒープの一部であるかを表します。 - 構築フェーズ: すべての非葉ノード（最後の親であるインデックス
n/2 - 1からルートまで）を sift down することで、任意の配列を最大ヒープに変換します。 - ソートフェーズ: 各ステップで現在の最大値を末尾に移動し、ヒープを縮小します。これにより、配列は後ろから順にソートされた状態で埋まっていきます。
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
ヒープソート - DSAシリーズのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity