インターバルヒープ（区間ヒープ）とは？データ構造の基本をわかりやすく解説

インターバルヒープとは

インターバルヒープ（Interval Heap）は、両端優先度キュー（Double-Ended Priority Queue）を効率的に実装するために用いられるデータ構造です。完全二分木の一種であり、最後のノードを除くすべてのノードが2つの要素を持つという特徴があります。

ノードと区間の関係

ノードPに格納された2つの要素の優先度を「a」と「b」とし、a ≤ b が成り立つものとします。このとき、ノードPは閉区間 [a, b] を表すと定義されます。ここで、a を区間の左端点、b を右端点と呼びます。

ある区間 [c, d] が区間 [a, b] に包含されるのは、次の条件が成り立つとき、かつそのときに限ります。

a ≤ c ≤ d ≤ b

親子ノード間の包含条件

インターバルヒープでは、各ノードPの左の子および右の子が表す区間は、必ずP自身が表す区間に包含されていなければなりません。つまり、木を根から葉に向かうほど区間が狭くなっていく構造になっています。

また、最後のノードが要素を1つしか持たない場合（優先度を c とする）、その親ノードの区間を [a, b] としたときに、a ≤ c ≤ b という条件を満たす必要があります。

最小ヒープと最大ヒープの性質を併せ持つ

インターバルヒープの重要な性質として、以下の2点が挙げられます。

• すべてのノードの左端点だけに着目すると、木全体が最小ヒープ（Min Heap）の構造になっている
• すべてのノードの右端点だけに着目すると、木全体が最大ヒープ（Max Heap）の構造になっている

この性質により、インターバルヒープは最小ヒープと最大ヒープの役割を1本の木で同時に実現できるのです。

主な操作と計算量

• 最小値の参照： 根ノードの左端点を見るだけでよいため、O(1) で取得可能
• 最大値の参照： 根ノードの右端点を見るだけでよいため、O(1) で取得可能
• 挿入・削除： ヒープの再構築が必要なため、O(log n)

応用例

インターバルヒープは、最小値と最大値の両方を高速に取り出したい場面で活躍します。具体的には、タスクスケジューリング、イベント駆動シミュレーション、ストリームデータからの中間値や極値の管理など、両端優先度キューが必要となるさまざまなアルゴリズムで利用されています。