c++ - Priority queue在pop操作过程中如何比较和维护heap属性

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

这是构建的二叉堆:
1
2 8
4

我看到当 1 弹出时，它被替换为 4，然后 2 被替换为 4 以维护堆属性和二进制堆
2
4 8
然后当 2 弹出时 8 被替换为 2 然后 4 被替换为 8 以维护堆属性然后当 4 弹出时 4 被替换为 8 最后 8 被弹出。因此根据我的输出是

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

我哪里错了？

Answer 1

第一次调用

p.push(2)

节点 2 被添加到您的堆中，导致

 2
/ \

然后我们添加 4，它被添加到最左边的未平仓位置，导致

  2
 / \
4

自 2 < 4 以来保持堆属性，然后我们将 8 添加到下一个打开的位置

  2
 / \
4   8

堆属性仍然保持，最后我们加1。

    2
   / \
  4   8
 /
1

由于 1 < 4 违反了堆属性，因此我们筛选或交换节点 4 和 1，导致:

    2
   / \
  1   8
 /
4

由于 1 < 2 仍然违反堆属性，因此我们再次向上筛选，导致:

    1
   / \
  2   8
 /
4

现在回答你的问题。在我们第一次调用 top 时，我们返回堆的最小值，在我们的例子中是 1。然后我们弹出 1，将堆大小减 1，并将堆中的最后一个值复制到根，结果:

  4
 / \
2   8

因为2 < 4，违反了堆属性，需要筛选，导致:

  2
 / \
4   8

我们以这种方式继续，直到堆为空。我把它留给你弄清楚剩下的。希望这会有所帮助。