ALGO_GUIDE: ヒープソートの構造

新人エンジニアがまず理解すべきは、ヒープソートが「完全二分木」を配列として効率的に管理している点です。

1. 親子の関係（インデックス計算）

メモリ上の配列内では、添え字 i に対して以下の計算で瞬時に親子へアクセス可能です：

• 親のインデックス：(i - 1) / 2 （切捨て）
• 左の子：2i + 1
• 右の子：2i + 2

2. 最大ヒープの構築 (Build Heap)

すべての親ノードがその子ノードよりも大きい値（親 ≧ 子）になるように調整する工程です。この状態になると、木の頂上（根）には必ず「全データ中の最大値」が来ます。

3. ソートプロトコル (Extraction)

根の最大値を取り出し、木の末尾の要素と入れ替えます。その後、崩れたヒープ構造を再び頂上から再調整（Heapify-Down）します。これを繰り返すことで、末尾から大きい順に値が確定していきます。

4. 計算量と実務での利点

計算量は常に O(n \log n) です。クイックソートのように最悪ケースで O(n^2) になることがなく、また追加のメモリもほとんど消費しない（空間計算量 O(1)）ため、組み込みシステム等のメモリ制限が厳しい環境で重宝されます。