C++ での優先順位付きキューの使い方まとめ (PriorityQueue)

はじめに

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

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

使い方

宣言

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

[sourcecode language=”cpp” title=””]
#include
using namespace std;

priority_queue maxpq; // default 大きい順
priority_queue, greater > minpq; // 小さい順
[/sourcecode]

関数

要素を追加する (push)

[sourcecode language=”cpp” title=””]
pq.push (1);
[/sourcecode]

先頭の要素を取り出す

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

[sourcecode language=”cpp” title=””]
pq.pop ();
[/sourcecode]

要素を調べる

[sourcecode language=”cpp” title=””]
// キューがからかどうかを調べる
pq.empty ()

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

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

Sample

昇順に取り出す

[sourcecode language=”cpp” title=””]
#include
#include
using namespace std;

int main ()
{
priority_queue 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;
}
[/sourcecode]

実行結果

[sourcecode language=”language” title=””]
3
2
1
[/sourcecode]

降順に取り出す

[sourcecode language=”cpp” title=””]
#include
#include
using namespace std;

int main ()
{
priority_queue, greater > 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;
}
[/sourcecode]

実行結果

[sourcecode language=”language” title=””]
1
2
3
[/sourcecode]

おまけ

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

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

MinPQ: