How it works?

バイナリヒープは単純な配列の中に格納されます。インデックス i（0から開始）にあるノードに対して、その子は 2*i + 1 と 2*i + 2 に位置します。このインデックス付けこそが、ツリーを配列の中に共存させるための重要なトリックです。

ステップバイステップのプロセス：

1. 最大ヒープの構築： すべての親がその子以上（>=）になるように配列を並べ替えます。最大の値がインデックス0に配置されます。
2. 最大値の抽出： ルート（最大値）をヒープの最後の要素と入れ替え、ヒープのサイズを1つ減らします。これにより、最大値は最終的なソート位置として末尾に固定されます。
3. シフトダウンによる修復： 新しいルートが適切な位置にない可能性があるため、ヒープの特性が再び保持されるまで、それをシフトダウン（より大きな子と入れ替える作業を繰り返す）します。
4. 繰り返し： ヒープが空になるまで繰り返します。これで配列は昇順にソートされます。

[4, 10, 3, 5, 1] の例：

• 最大ヒープを構築： [10, 5, 3, 4, 1]。
• ルートの10を末尾と入れ替えてシフトダウンし、次に5、4、3についても同様に繰り返します。
• 結果： [1, 3, 4, 5, 10]。