C++ ヒープ (priority_queue)

優先度つきキューは、何をどういう順序で入れても、優先順位の高いものから順に取り出すことができるキューです。内部的にはヒープを使って実装されます。C++では、priority_queueというのがあります。

コード

int main() {
  priority_queue<int> que;
  que.push(1);
  que.push(6);
  cout << que.top() << endl;
}

結果

デフォルトでは、値が大きい順になります。小さい順にするには下記のようにします。

コード

int main() {
  priority_queue<
    int,
    vector<int>,
    greater<int>
  > que;
  que.push(1);
  que.push(6);
  cout << que.top() << endl;
}

結果

では、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)の要素の小さい順になります。