深入理解 C++ STL 优先队列 priority_queue 原理与实现

这里的关键在于第三个模板参数，它决定了元素的排序规则。

模拟实现：从底层看本质

理解优先队列的最好方式就是自己写一遍。它的核心在于两个调整函数：向上调整（维护插入后的堆序）和向下调整（维护删除后的堆序）。

类模板定义

我们利用缺省参数将底层容器设为 vector：

template<class T, class Container = std::vector<T>>
class MyPriorityQueue {
private:
    Container x;
public:
    // ... 成员函数
};

插入与向上调整

插入时先追加到末尾，然后从下往上比较交换：

void push(const T& data) {
    x.push_back(data);
    shiftUp(x.size() - 1);
}

void shiftUp(int child) {
    int parent = (child - 1) / 2;
    while (parent >= 0 && x[child] > x[parent]) {
        std::swap(x[child], x[parent]);
        child = parent;
        parent = (child - 1) / 2;
    }
}

这里要注意边界条件，当 child 到达根节点时循环自然终止。

删除与向下调整

删除堆顶时，为了保持数组紧凑，我们将最后一个元素移到顶部，再从上往下调整：

void pop() {
    if (x.empty()) return;
    std::swap(x[0], x.back());
    x.pop_back();
    if (!x.empty()) shiftDown(0);
}

void shiftDown(int parent) {
    int child = 2 * parent + 1;
    while (child < x.size()) {
        // 如果右孩子存在且更大，选右孩子
        if (child + 1 < x.size() && x[child + 1] > x[child]) {
            child++;
        }
        // 如果父节点小于子节点，交换
        if (x[parent] < x[child]) {
            std::swap(x[parent], x[child]);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

这个逻辑保证了删除任意元素后，剩余部分依然满足堆的性质。

实战示例

下面是一个完整的测试用例，展示了基本操作流程：

#include <iostream>
#include <queue>

void test_priority_queue() {
    priority_queue<int> pq;
    
    pq.push(10);
    pq.push(15);
    pq.push(5);
    pq.push(20);
    
    // 输出当前最大值
    std::cout << pq.top() << std::endl; // 20
    
    pq.pop();
    
    // 再次输出
    std::cout << pq.top() << std::endl; // 15
    
    std::cout << "是否为空：" << pq.empty() << std::endl;
}

通过这种方式，你可以灵活地将优先队列应用到各种场景中，无论是任务调度还是路径规划。掌握其内部调整机制，能让你在遇到性能瓶颈时知道如何优化。