優先度付きキュー

優先度付きキュー

優先度付きキューは、要素に優先度を付けて管理する抽象データ型です。通常のキューとは異なり、要素が追加された順ではなく、優先度に基づいて取り出される点が特徴です。このデータ構造は、様々なアルゴリズムやシステムで利用されており、効率的なデータ管理に役立ちます。

基本操作

優先度付きキューは、主に以下の4つの操作をサポートします。

1. 要素の追加: 要素を優先度付きでキューに追加します。
2. 最大優先度要素の取り出し: キュー内で最も高い優先度を持つ要素を取り出し、返します。取り出した要素はキューから削除されます。
3. (オプション)最大優先度要素の参照: キュー内で最も高い優先度を持つ要素を取り出さずに参照します。
4. (オプション)要素の優先度変更: 指定した要素の優先度を変更します。

実装方法

優先度付きキューの実装には、様々な方法があります。それぞれの実装方法によって、操作の計算量やメモリ使用量が異なります。

連想配列

最も単純な実装方法は、連想配列を使用して、各優先度に対応する要素のリストを保持する方法です。要素の追加はO(1)で高速ですが、要素の削除や参照には、すべてのキーを探索する必要があるためO(n)の計算量がかかります。

平衡2分探索木

平衡2分探索木を使用すると、要素の追加、削除、参照のすべての操作をO(log n)の計算量で実行できます。平衡木が提供されている環境では、一般的な実装方法として利用されます。

Van Emde Boas tree

Van Emde Boas treeは、連想配列の一種で、上記の3つの操作をO(log log n)で実行できます。ただし、キューの空間コストがO(2m/2)と大きくなるため、注意が必要です。ここで、mは優先度を表現するために必要なビット数です。

ヒープ

ヒープは、優先度付きキューを効率的に実装するためのデータ構造です。二分ヒープは、要素の挿入と削除をO(log n)で、先頭要素の参照をO(1)で実行できます。二項ヒープは、いくつかの操作を追加できますが、先頭要素の参照にO(log n)の計算量がかかります。フィボナッチヒープは、要素の挿入、先頭要素の参照、優先度の引き下げを償却時間O(1)で実行でき、要素の削除はO(log n)で行うことができます。

各プログラミング言語での実装

C++

C++のSTLには、コンテナアダプタとしてpriority_queueが提供されています。実装はコンパイラ依存ですが、GCCでは二分ヒープが採用されています。g++拡張のPBDSには、内部データ構造を選択可能なpriority_queueが存在し、デフォルトではペアリングヒープが使用されています。

Java

Javaの標準クラスライブラリには、java.util.PriorityQueueが提供されており、二分ヒープで実装されています。Java 8現在、優先度変更のAPIは提供されていませんが、先頭以外の削除と追加を組み合わせて実現できます。ただし、先頭以外の削除は計算量が大きくなる場合があるため、注意が必要です。

応用例

優先度付きキューは、様々な分野で応用されています。

グラフアルゴリズム: ダイクストラ法やプリム法などで、最短経路や最小全域木を求める際に利用されます。
バンド幅管理: ネットワーク帯域幅の管理において、優先度に基づいてトラフィックを制御する際に利用されます。
オペレーティングシステム: プロセス処理、割り込み処理、ロードバランシングなど、優先度に基づいてタスクを管理する際に利用されます。
データ圧縮: ハフマン符号などのデータ圧縮アルゴリズムで、文字の出現頻度を優先度として利用する際に利用されます。
離散イベントシミュレーション: イベントを優先度（時間）順に管理し、シミュレーションを実行する際に利用されます。

ソートとの関係

優先度付きキューは、ソートアルゴリズムとも密接な関係があります。優先度付きキューに要素を挿入し、順番に取り出すことで、要素をソートできます。この操作は、ヒープソート、選択ソート、挿入ソートなどのソートアルゴリズムで実際に利用されています。

ヒープソート: 優先度付きキューがヒープで実装されている場合に相当します。
選択ソート: 優先度付きキューがソートされていない配列で実装されている場合に相当します。
挿入ソート: 優先度付きキューがソートされた配列で実装されている場合に相当します。

関連項目

アルゴリズム
データ構造

参照

Wikipedia - 優先度付きキュー

もう一度検索