デュアルプライオリティキュー（DEPQ）とは？双対構造法による実装を解説

デュアルプライオリティキュー（DEPQ）の概要

デュアルプライオリティキュー（Double Ended Priority Queue：DEPQ、両端優先度キュー）は、最小要素と最大要素の両方に効率的にアクセスできるデータ構造です。本記事では、片側のみの優先度キュー（PQ）から効率的なDEPQデータ構造を構築する一般的な手法について解説します。

単一端の優先度キュー（PQ）からDEPQを導出するための一般的な手法が存在します。これらの手法は、remove(bNode)操作（指定されたノードbNodeをPQから削除する操作）を効率的に実装できるPQデータ構造を前提としています。

双対構造法（Dual Structure Method）

最もシンプルな手法が「双対構造法」です。この方法では、DEPQの全要素について、最小ヒープ（min PQ）と最大ヒープ（max PQ）の2つのヒープを同時に管理します。さらに、同じ要素に対応する最小ヒープ側のノードと最大ヒープ側のノードの間に「対応ポインタ（correspondence pointers）」を設定します。

図Dは、要素 7, 8, 3, 6, 5 からなる双対ヒープ構造を示したものです。対応ポインタは赤い矢印で表現されています。

図D：双対ヒープ

各要素の格納場所について

図では各要素が最小ヒープと最大ヒープの両方に格納されているように見えますが、実際には各要素をどちらか一方のヒープにのみ格納すれば十分です。この工夫により、メモリ使用量を抑えることができます。

DEPQの基本操作

isEmpty および size 操作

isEmpty（空判定）とsize（要素数の取得）は、DEPQ内の要素数を追跡する変数 size を保持しておくことで、簡単かつ高速に実装できます。

最小・最大要素の参照

最小要素は必ず最小ヒープの根（ルート）に位置し、最大要素は最大ヒープの根に位置します。そのため、どちらの要素も定数時間で参照可能です。

挿入操作

要素Bを挿入する際は、まずBを最小ヒープと最大ヒープの両方に挿入します。その後、最小ヒープ内のBの位置と最大ヒープ内のBの位置の間に対応ポインタを設定します。

削除操作

最小要素を削除する場合は、最小ヒープに対してremoveMinを実行するとともに、最大ヒープに対してremove(bNode)を実行します。ここでbNodeは、削除された要素に対応する最大ヒープ側のノードを指します。最大要素の削除も、これと対称的な手順で行うことができます。