C++ STL 优先队列（priority_queue）原理与模拟实现

深入底层：模拟实现

理解优先队列的最佳方式是亲手实现它。既然底层是 vector，我们只需要封装一层逻辑，维护堆的性质即可。

类模板定义

template<class T, class container = std::vector<T>>
class priority_queue {
public:
    // 构造函数通常可省略，依赖 vector 默认构造
private:
    container x; // 底层容器
};

插入逻辑：向上调整

插入时，先将元素追加到尾部，然后从该位置开始向上调整，直到满足父节点大于子节点的大顶堆性质。

void push(const T& value) {
    x.push_back(value);
    shiftUp(x.size() - 1); // 向上调整
}

void shiftUp(int child) {
    while (child > 0) {
        int parent = (child - 1) / 2;
        if (x[child] > x[parent]) {
            std::swap(x[child], x[parent]);
            child = parent;
        } else {
            break; // 已满足堆性质
        }
    }
}

删除逻辑：向下调整

删除堆顶元素不能直接删，否则会导致空缺。标准做法是将堆顶与最后一个元素交换，删除尾部，然后从根节点开始向下调整。

void pop() {
    if (!x.empty()) {
        std::swap(x[0], x.back());
        x.pop_back();
        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;
        }
    }
}

完整测试示例

void test_priority_queue() {
    std::priority_queue<int> pq;
    
    // 插入一组数据
    for (int val : {10, 15, 5, 20, 0, 25}) {
        pq.push(val);
    }

    // 输出堆顶（最大值）
    std::cout << "Top: " << pq.top() << std::endl;
    
    // 弹出堆顶
    pq.pop();
    std::cout << "New Top: " << pq.top() << std::endl;
    
    // 检查是否为空
    std::cout << "Empty: " << pq.empty() << std::endl;
}