インターバルヒープの操作一覧と計算量(時間複雑度)を解説
インターバルヒープ(DEPQ)とは
両端優先度付きキュー(Double-Ended Priority Queue:DEPQ)は、インターバルヒープとして実装されるデータ構造で、最小値と最大値の両方に効率的にアクセスできます。DEPQ(インターバルヒープ)では、以下のような基本操作が定義されています。
主な操作の詳細
isEmpty()
DEPQが空かどうかを判定する関数です。キューが空であればtrueを返します。
size()
DEPQ内に現在存在する要素の総数を返す関数です。
getMin()
最も優先度が低い(最小の)要素を参照して返す関数です。要素の削除は行いません。
getMax()
最も優先度が高い(最大の)要素を参照して返す関数です。こちらも要素の削除は行いません。
put(z)
要素zをDEPQに挿入する関数です。
removeMin()
最も優先度が小さい要素をDEPQから削除し、その要素を返す関数です。
removeMax()
最も優先度が大きい要素をDEPQから削除し、その要素を返す関数です。
各操作の計算量(時間複雑度)
- isEmpty()、size()、getMin()、getMax() の各操作は、それぞれ O(1) の時間で実行できます。
- put(z)、removeMin()、removeMax() の各操作は、それぞれ O(log n) の時間で実行できます。
- n個の要素からインターバルヒープを初期化(構築)するには、O(n) の時間がかかります。
このように、インターバルヒープは最小値・最大値の取得を定数時間で行え、挿入や削除も対数時間で処理できるため、両端での優先度アクセスが必要な場面において非常に効率的なデータ構造といえます。
-
ペアリングヒープとは？特徴・基本操作・計算量をわかりやすく解説
ペアリングヒープとは ペアリングヒープ（Pairing Heap）は、比較的シンプルな実装でありながら、実用上きわめて優れた償却性能（amortized performance）を発揮することで知られるヒープデータ構造の一種です。 ペアリングヒープは「ヒープ順序」を満たす多分木構造として定義され、簡略化されたフィボナッチヒープとみなすこともできます。 プリム法（Primの最小全域木アルゴリズム）のようなアルゴリズムを実装する際の「堅牢な選択肢」とされており、最小ヒープを前提とした場合、以下の操作をサポートします。 ペアリングヒープの主な操作 find-min（最小値の参照） − ヒープの先
-
データ構造の償却時間計算量とは？償却解析の基礎と計算方法を解説
償却解析（Amortized Analysis）とは償却解析は、ごく一部の操作が非常に遅い一方で、頻繁に実行される大半の操作は高速であるような状況で用いられる分析手法です。データ構造の分野では、ハッシュテーブルや素集合データ構造（Disjoint Set／Union-Find）などの性能評価において重要な役割を果たします。例えばハッシュテーブルでは、探索の時間計算量はほとんどの場合 O(1) ですが、ときに O(n) の操作が発生することがあります。要素の検索や挿入は通常、定数時間で完了する処理です。しかし衝突（コリジョン）が発生した場合には、その解決のために O(n) の操作が必要になること