インターバルヒープの初期化方法を徹底解説

インターバルヒープとは

インターバルヒープ（Interval Heap）は、各ノードが2つの要素を持つ「埋め込み型ミニマックスヒープ」と同等のデータ構造です。完全二分木として定義され、以下の性質を満たします。

• 左側の要素は、右側の要素以下（≤）である。
• 両方の要素によって、1つの閉区間が定義される。
• 根以外の任意のノードが表す区間は、必ず親ノードの区間の部分区間となる。
• 左側の要素群は最小ヒープ（min heap）を構成する。
• 右側の要素群は最大ヒープ（max heap）を構成する。

この構造により、インターバルヒープは両端優先キュー（double-ended priority queue）の実装など、最小値と最大値の両方に高速にアクセスが必要な場面で活用されます。

要素数による2つの場合

格納する要素の数に応じて、インターバルヒープは次の2つの場合に分けられます。

偶数個の要素の場合

各ノードは a と b の2つの要素を持ち、常に a ≤ b が成り立ちます。このとき、すべてのノードは区間 [a, b] として表現されます。

奇数個の要素の場合

最後のノード以外は2つの要素を持ち、区間 [a, b] として表現されます。一方、最後のノードには要素が1つだけ含まれ、その単一の要素によって区間 [a, b] が表されます。

インターバルヒープの初期化手順

インターバルヒープは、通常のヒープの初期化と同じ戦略を用いて初期化できます。具体的には、ヒープの最下層から根へと向かって処理を進めながら、各部分木がインターバルヒープとして成立していることを保証していきます。

各部分木に対しては、以下の手順を実行します。

1. 根の要素を整列する：まず、その部分木の根にある要素を順序付けし、左端点 ≤ 右端点となるように並べます。
2. 左端点を再挿入する：次に、この部分木の根の左端点を取り出し、removeMin 関数で用いられる再挿入戦略を実装して、適切な位置へ再度挿入します。
3. 右端点を再挿入する：最後に、同じく根の右端点を取り出し、removeMax 関数で用いられる戦略を実装して、再度挿入します。

この手順をすべての部分木に対して繰り返すことで、木全体が正しいインターバルヒープの不変条件（各区間が親の区間に包含されること）を満たすように初期化されます。