priority queue は、T 型の要素を保持するデータ構造で、表 17 に示す 5 つの演算を実装します。
表 17 -- priority queue 演算
| 関数 | 実装される演算 |
|---|---|
|
push(T) |
維持されるコレクションに値を追加する |
|
top() |
コレクションの最小の要素への参照を返す |
|
pop() |
コレクションから最小の要素を削除する |
|
size() |
コレクションの要素数を返す |
|
empty() |
コレクションが空の場合、true を返す |
T 型の要素は、デフォルトの小なり演算子 < を使用するか、テンプレート引数またはコンストラクタの任意の引数のいずれかとして渡される比較関数を利用して、互いに互換性を持つようにする必要があります。この章の後半で示すプログラム例で、後者の形式を説明します。標準ライブラリのすべてのコンテナと同様に、複数のコンストラクタがあります。デフォルトコンストラクタは、引数がないこと、または任意の比較関数を要求します。代替コンストラクタは反復子 pair を使用して、引数のシーケンスからコンテナの値を初期化します。さらに、任意の 3 番目の引数を使用して、比較関数を定義することができます。
priority queue データ型はコンテナクラスの最上部に構築され、コレクションの値を実際に維持するために使用される構造です。標準 C++ ライブラリには、priority queuesの構築に使用できる vector と deque の 2 つのコンテナがあります。デフォルトでは、priority_queue は vector を使用します。
以下に、priority queue3 の宣言をいくつか示します。
priority_queue< int > queue_one; //vector と less<int> を使用する
priority_queue< int, vector<int>, greater<int> > queue_two;
priority_queue< double, deque<double> >
queue_three(aList.begin(), aList.end());
priority_queue< eventStruct, vector<eventStruct> >
queue_four(eventComparison);
priority_queue< eventStruct, deque<eventStruct> >
queue_five(aVector.begin(), aVector.end(), eventComparison);
queue の要素の数が実行中に大きく変化する場合は特に、vector から作成される queue はより小さくなる傾向があり、一方、deque から作成される queue はより速くなる傾向があります。しかし、これらの相違はわずかで、いずれも通常は、ほとんどの状況で動作します。
priority queue データ構造自体は反復子の作成を行わないため、第 13 章に示すアルゴリズムのほとんどは priority queue で使用することができません。値を使用しての反復の代わりに、priority queue を使用する標準的なアルゴリズムでは、コレクションが空になるまで (empty() 演算を使用してテストします) 構造から値を繰り返し (top() および pop() 演算を使用して) 引き出すループを作成します。11.3 節 に記述されるプログラム例に、この使用例を示します。
priority queue は、heap と呼ばれるデータ構造を内部的に構築することによって実装されます。抽象的に言えば、heap4とは、各ノードに関連付けられた値が子ノードに関連付けられた値以下となる二分木のことです。