定義

ヒープは「親が子より常に大きい(最大ヒープ)または小さい(最小ヒープ)」というルールを満たす完全二分木です。 このルールにより、ルートノードで常に最大値(または最小値)を即座に確認できます。

主な特性

• ✓完全二分木: 最後のレベルを除くすべてのレベルが埋まっており、左から順に埋められます。
• ✓ヒープ性質: 最大ヒープでは親≥子、最小ヒープでは親≤子を常に満たします。
• ✓配列で実装: インデックスiの子は2i+1、2i+2に、親は(i-1)/2に位置します。
• ✓ルートアクセスO(1): 最大/最小値は常にルート(インデックス0)にあり、即座にアクセス可能です。

時間計算量