優先順位付きキューのを PriorityQueue という.

キューの中で最大 (最小) のものを抜き出す場合などに利用する.

PriorityQueueの使い方

宣言

デフォルトでは大きい順で pop されるので, 最小のものを pop で取り出すには, greater を宣言時に追記する.

#include <queue>
using namespace std;

priority_queue <int> maxpq; // default 大きい順
priority_queue<int, vector<int>, greater<int> > minpq; // 小さい順

関数

要素を追加する (push)

pq.push (1);

先頭の要素を取り出す

最大 (または最小) の先頭を取り出します.

pq.pop ();

要素を調べる

// キューがからかどうかを調べる
pq.empty ()

//  要素数をしらべる
pq.size ();

// 次に取り出される要素を調べる
pq.top ();

Sample

昇順に取り出す

#include <queue>
#include <iostream>
using namespace std;

int main ()
{
  priority_queue<int> pq;

  pq.push ( 2 );
  pq.push ( 1 );
  pq.push ( 3 );

  cout << pq.top () << endl;
  pq.pop ();
  cout << pq.top () << endl;
  pq.pop ();
  cout << pq.top () << endl;
  pq.pop ();

  return 0;
}

実行結果

3
2
1

降順に取り出す

#include <queue>
#include <iostream>
using namespace std;

int main ()
{
  priority_queue<int, vector<int>, greater<int> > pq;

  pq.push ( 2 );
  pq.push ( 1 );
  pq.push ( 3 );

  cout << pq.top () << endl;
  pq.pop ();
  cout << pq.top () << endl;
  pq.pop ();
  cout << pq.top () << endl;
  pq.pop ();

  return 0;
}

実行結果

1
2
3

おまけ

ダイクストラ法の実装をする際に, C++ の STL があるとは知らずに, 自前で最小優先キューを実装しました. STL を利用すればよかった.

この Java Sourse を参考に C++ に書きなおした.

MinPQ: