優先度つきキューは、何をどういう順序で入れても、優先順位の高いものから順に取り出すことができるキューです。内部的にはヒープを使って実装されます。C++では、priority_queueというのがあります。
コード
int main() { priority_queue<int> que; que.push(1); que.push(6); cout << que.top() << endl; }
結果
6
デフォルトでは、値が大きい順になります。小さい順にするには下記のようにします。
コード
int main() { priority_queue< int, vector<int>, greater<int> > que; que.push(1); que.push(6); cout << que.top() << endl; }
結果
1
では、pairをキューに入れてみたいと思います。
コード
int main() { priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > que; que.push(make_pair(10, 1)); que.push(make_pair(5, 2)); que.push(make_pair(7, 3)); cout << que.top().first << ' ' << que.top().second << endl; }
結果
5 2
問題なく実行できました。ペアの左(first)の要素の小さい順になります。