priority_queue とは

priority_queueとは優先度つき待ち行列と呼ばれるもので、 挿入された順序どおりに要素の取り出しを行うのではなく、 優先度の高い要素から先に取り出す待ち行列。

例えば、int型を格納するpriority_queueで、整数の値をそのまま優先度として用いると、値の大きな整数から順に取り出される待ち行列になります。

priority_queueはヒープと呼ばれるデータ構造が使われます。 このヒープは、完全な2分木の形をしていて、 木の各ノードは自身より下にの要素よりも大きな値を持ちます。 そのため、最大の値を持つ要素は常に木の根に含まれていることになります。 この木の根にある要素を取り出すことで常に最大の値を持つ要素を取り出します。

ヒープの実装は、ランダムアクセス([]を使った添字によるアクセス)のできるデータ構造を使って行えます。

STL におけるpriority_queue

STLのpriority_queueは何を使って実装するかをvector,queueのいずれかから選べます。

キューの要素の型をTとすると、

priority_queue<T, vector<T> >	vectorによるpriority_queue
priority_queue<T, deque<T> >	dequeによるpriority_queue
priority_queue<T, vector<T>, greater<T> >	vectorによるpriority_queue (値の小さな要素から取り出す)

他にも、push_back, pop_front, front, back, sizeなどのメソッドを適当に定義したクラスなら 何でもキューの実装に使えます。