インターバルヒープへの要素の挿入方法
インターバルヒープへの要素の挿入
インターバルヒープに新しい要素を挿入する手順は、現在ヒープ内に存在する要素数によって異なります。以下の2つの場合に分けて考えることができます。
要素数が奇数の場合
要素数が奇数である場合、まず新しい要素を最後のノードに挿入します。その後、直前のノードの要素と順次比較を行い、インターバルヒープとして必要な条件（親ノードの区間に含まれることなど）を満たしているかどうかを確認します。もし条件を満たしていなければ、すべての条件が満たされるまで、要素を最後のノードから根（ルート）方向へと順に移動させていきます。
要素数が偶数の場合
要素数が偶数である場合、新しい要素を挿入するために新たなノードを作成します。このとき、新しい要素が親ノードの区間の左側（最小値より小さい）に位置する場合はミンヒープ側の要素として扱われ、区間の右側（最大値より大きい）に位置する場合はマックスヒープ側の要素として扱われます。
その後、同様に順次比較を行いながら、インターバルヒープの条件がすべて満たされるまで、要素を最後のノードから根へと移動させます。一方、新しい要素がすでに親ノードの区間内に収まっている場合は、その時点で処理を終了し、要素の移動は一切行われません。
挿入にかかる計算量
要素の挿入に必要な時間は、インターバルヒープの条件をすべて満たすために必要な要素の移動回数に依存します。最悪の場合でも木の高さに比例するため、計算量は O(log n) となります。
-
インターバルヒープ（区間ヒープ）とは？データ構造の基本をわかりやすく解説
インターバルヒープとはインターバルヒープ（Interval Heap）は、両端優先度キュー（Double-Ended Priority Queue）を効率的に実装するために用いられるデータ構造です。完全二分木の一種であり、最後のノードを除くすべてのノードが2つの要素を持つという特徴があります。ノードと区間の関係ノードPに格納された2つの要素の優先度を「a」と「b」とし、a ≤ b が成り立つものとします。このとき、ノードPは閉区間 [a, b] を表すと定義されます。ここで、a を区間の左端点、b を右端点と呼びます。ある区間 [c, d] が区間 [a, b] に包含されるのは、次の条件が成
-
C言語でキューに要素を挿入する方法を徹底解説！基本概念からサンプルコードまで
データ構造とは、データを体系的かつ効率的に整理・格納するための仕組みです。データ構造は、その構成方法によって大きく以下の2種類に分類できます。線形データ構造 − データが一直線上に順序立てて配置される構造です。例として、配列、構造体、スタック、キュー、連結リストなどが挙げられます。非線形データ構造 − データが階層的・網目的に配置される構造です。例として、木（ツリー）、グラフ、集合、テーブルなどが挙げられます。キュー（Queue）とはキューは線形データ構造の一つで、後端（リア/rear）から要素を挿入し、前端（フロント/front）から要素を削除するという特徴を持っています。キューにおけるデー