ヒープソートとHeapify — O(n log n)のインプレースソート

ヒープソートの動作原理

ヒープソートは最大ヒープデータ構造を活用して配列をインプレースでソートします。入力データから最大ヒープを構築し、最大要素を繰り返し抽出する2つのフェーズで構成されます。

フェーズ1：最大ヒープの構築

最大ヒープは、各親がその子以上である完全二分木です。配列表現はレベルごとにツリーを格納します：

• ノード i の親：floor((i-1)/2)
• ノード i の左の子：2*i + 1
• ノード i の右の子：2*i + 2

heapify を使用したボトムアップのヒープ構築はO(n)時間で行えます（素朴な分析が示唆するO(n log n)ではありません）。

Heapify手順

heapify(arr, size, i) はインデックス i をルートとするサブツリーがヒープ性を満たすことを保証します：

function heapify(arr, size, i):
  largest = i
  left = 2*i + 1
  right = 2*i + 2
  if left < size and arr[left] > arr[largest]:
    largest = left
  if right < size and arr[right] > arr[largest]:
    largest = right
  if largest != i:
    swap(arr[i], arr[largest])
    heapify(arr, size, largest)

フェーズ2：要素の抽出

ヒープ構築後、最大要素はインデックス0にあります。最後の未ソート要素とスワップし、ヒープサイズを1減らし、ルートをheapifyします：

for i = n-1 down to 1:
  swap(arr[0], arr[i])
  heapify(arr, i, 0)

計算量分析

指標	値
ヒープ構築	O(n)
n回の抽出 x heapify	O(n log n)
合計時間	O(n log n) — すべてのケース
空間	O(1) — インプレース
安定	いいえ

ヒープ構築がO(n)である理由

直感的には、ほとんどのノードはツリーの下部に近く、わずかな距離のみheapifyが必要です。ノードの半分は葉（heapify不要）、4分の1は最大1回のスワップ、8分の1は最大2回、というように合計はO(n)に収束します。