What is a Heap?

ヒープは、1つの単純な不変条件に従う木構造のデータ構造です。それは、すべての親がその子よりも小さい（または等しい）というものです。最小の値は常にルートに位置し、O(1)で読み取ることができます。この特定の形式は最小ヒープ（min-heap）と呼ばれます。ルートが最大値となる逆の形式は最大ヒープ（max-heap）です。

巧妙な点はその格納方法にあります。木構造として考えますが、ヒープはフラットな配列（array）の中に存在します。インデックス i にあるノードについて：

• その親はインデックス (i - 1) / 2 にあります。
• その左の子はインデックス 2 * i + 1 にあります。
• その右の子はインデックス 2 * i + 2 にあります。

ポインタもノードオブジェクトも不要で、単なるインデックスの計算だけです。これにより、ヒープはキャッシュ効率が非常に良く、実装も容易になります。

最小ヒープにおける5つの主な操作は以下の通りです：

1. Peek: 最小の値（ルート）を返します。
2. Insert: 値を追加し、適切な位置まで浮かび上がらせます。
3. ExtractMin: 最小の値を取り出して返します。
4. Size: 格納されている値の数を返します。
5. IsEmpty: ヒープが空かどうかを確認します。

それでは、MinHeap クラスを作成しましょう！