c++ - Priority queue在push操作过程中是如何比较和存储值的？

Question

我正在研究优先级队列，我想检查如何使用可比较的类来比较这些值。这是我的代码。

#include <iostream>
#include <queue>

using namespace std;

class g {
    public:
        bool operator() (int a, int b) {
        cout<<a<<" "<<b<<endl;
            return (a > b);
        }
};

int main() {
    priority_queue<int,vector<int>,g> p;
    p.push(2);
    cout<<"CHECK1"<<endl;
    p.push(4);
    cout<<"CHECK2"<<endl;
    p.push(8);
    cout<<"CHECK3"<<endl;
    p.push(1);
    cout<<"CHECK4"<<endl;
    while(!p.empty()) {
        cout<<p.top()<<endl;
        p.pop();
    }
}

输出是

CHECK1
2 4
CHECK2
2 8
CHECK3
4 1
2 1
CHECK4
1
8 2
2 4
2
4 8
4
8

我看到当 4 被插入时，它与 2 进行比较，当 8 被插入时，它再次与 2 进行比较。但为什么 8 不与 4 进行比较呢？有人可以帮忙吗？

Answer 1

优先级队列通常被实现为一个完美平衡的堆结构。堆可以看作是一棵二叉树，唯一的要求是根的优先级高于(比较器的值较小)它的 child ，堆条件。

                root
      Lchild1             Rchild1
  Lchild2  Rchild2     Lchild2  empty

任何插入物都会插入空位以保持树的平衡。插入后，它会向上移动到树中以维持堆状态。所以在这种情况下，唯一可能的比较是 Rchild1 和 root。

删除/pop() 是通过删除根并交换 Lchild2 来完成的，以保持完美的平衡，然后将 Lchild2 向下移动到堆中以更正堆条件。

这棵树很容易保存在 vector 中。

                root(2)
      Lchild1(4)        empty.

8 的插入(在空位)只需要与根进行比较。

                root(2)
      Lchild1(4)        Rchild1(8).
   empty

在空位插入1，需要检查4并交换，然后与根比较(交换)。

有很多可能的内部表示，例如参见 https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/pq_performance_tests.html .其他包括红黑树。

这也可能有帮助 Efficiency of the STL priority_queue