C++优先队列-何时重新平衡堆？

在C++中，优先队列以堆为基础实现。堆是一种具有特殊属性的完全二叉树，即每个父节点的值都大于或等于其子节点的值（对于大根堆），或每个父节点的值都小于或等于其子节点的值（对于小根堆）。

当插入一个新元素或删除最高优先级元素时，优先队列需要维护堆的性质。插入新元素时，需要将其插入到堆的最后一个位置，然后沿着其父节点一直向上交换，直到堆的性质得到满足。删除最高优先级元素时，需要将堆的最后一个元素移动到根节点位置，然后沿着其子节点中较大或较小的那个一直向下交换，直到堆的性质得到满足。

堆的插入和删除操作具有O(log n)的时间复杂度，其中n是堆中元素的数量。但是，这些操作可能会导致堆失衡（即堆的某个节点的子树的深度差异超过1），从而导致效率下降。为了避免这种情况，实现时可以在插入和删除操作后进行堆的平衡化操作，这样可以确保堆的性质得到维护。

以下是C++的示例代码，其中priority_queue类已经自带维护堆的性质，因此不需要手动平衡化堆：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq; // 创建一个大根堆
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    
    cout << "队首元素：" << pq.top() << endl; // 输出队首元素，应该为4
    
    pq.pop(); // 删除队首元素
    cout << "队首元素：" << pq.top() << endl; // 输出队首元素，应该为3
    
    return 0;
}