std::priority_queue は安定ではない #C++

std::priority_queue は要素 T を push() しておくと優先順位の高い(=大きい)順に pop() できます。

int を要素とし、その一ケタ目を優先順位とみなして 0...29 を push() し、一気に pop() してみましょう。

#include <iostream>
#include <queue>

// 一ケタ目だけを比較する
struct less_digit {
  bool operator()(int x, int y) const {
    return (x%10) < (y%10);
  }
};

using namespace std;

int main() {
  priority_queue<int,std::vector<int>,less_digit> pq;
  for ( int i = 0; i < 30; ++i ) {
    pq.push(i);
  }

  while ( !pq.empty() ) {
    cout << pq.top() << ' ';
    pq.pop();
  }
  cout << endl;
}

実行結果はどうなるでしょう。一ケタ目が大きいものが先に現れるなら、
9 19 29 8 18 28 7 17 27 ...
と出力されると期待しますが、実際には:
9 29 19 28 8 18 27 7 17 26 6 16 5 25 15 14 4 24 13 23 3 12 22 2 11 21 1 20 10 0
でした。優先順位の等しい要素が複数あるとき、pop順は安定(=push順)ではないのです。

その理由は priority_queue::push()/pop() の実装にあります。

clas priority_queue {
  ...
  void push(const value_type& _Val) { // insert value in priority order
    c.push_back(_Val);
    push_heap(c.begin(), c.end(), comp);
  }

  void pop() { // erase highest-priority element
    pop_heap(c.begin(), c.end(), comp);
    c.pop_back();
  }

ご覧のとおり、push_heap/pop_heap で実現しているんです。
そのため時間計算量は Nlog(N) と高速だけど安定ではないというわけ。

安定なpriority_queueが欲しいなら、要素の挿入順を比較キーに使うのが安直な方法でしょう。

#include <iostream>
#include <queue>

struct less_digit {
  bool operator()(int x, int y) const {
    return (x%10) < (y%10);
  }
};

using namespace std;

template<typename T, typename Compare> 
struct stable_compare {
  bool operator()(const std::pair<T,unsigned>& x, const std::pair<T,unsigned>& y) const {
    if ( comp_(x.first, y.first) ) return true;
    if ( comp_(y.first, x.first) ) return false;
    return x.second > y.second; // 優先順位が等しいときは先に挿入した方を選ぶ
  }
  Compare comp_;
};

template<typename T, typename Compare> 
struct helper {
  typedef std::pair<T,unsigned> value_type;
  typedef std::vector<value_type> container_type;
  typedef stable_compare<T,Compare> compare_type;
  typedef std::priority_queue<value_type, container_type, compare_type> stable_priority_queue;
};

int main() {
  helper<int,less_digit>::stable_priority_queue pq;
  unsigned order = 0;
  for ( int i = 0; i < 30; ++i ) {
    pq.push(std::make_pair(i,order++));
  }

  while ( !pq.empty() ) {
    cout << pq.top().first << ' ';
    pq.pop();
  }
  cout << endl;
}

/* 実行結果:
9 19 29 8 18 28 7 17 27 6 16 26 5 15 25 4 14 24 3 13 23 2 12 22 1 11 21 0 10 20
*/

std::priority_queue は 安定ではない

std::priority_queue は安定ではない