如何用c++实现一个优先队列 priority_queue和堆【数据结构】

C++中priority_queue默认为最大堆，基于vector和堆算法实现；最小堆需指定greater比较器；还可用make_heap等底层函数或手动实现堆结构。

在 C++ 中，priority_queue 是标准模板库（STL）提供的容器适配器，底层默认基于 最大堆（max-heap） 实现，使用 std::vector 作为存储结构，并通过 std::make_heap、std::push_heap、std::pop_heap 等算法维护堆性质。你可以直接使用它，也可以手动实现一个最小堆/最大堆来深入理解原理。

用 STL priority_queue 快速实现优先队列

这是最常用、最安全的方式，适用于绝大多数场景：

• 默认是最大堆：顶部元素最大（top() 返回最大值）
• 要改成最小堆，需指定比较器：priority_queue<int vector>, greater<int>></int></int>
• 支持的操作：`push()`、`top()`、`pop()`、`empty()`、`size()`，时间复杂度均为 O(log n)

示例代码：

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

int main() {
    // 最大堆（默认）
    priority_queue<int> maxQ;
    maxQ.push(3); maxQ.push(1); maxQ.push(4);
    cout << maxQ.top() << endl; // 输出 4

    // 最小堆
    priority_queue<int, vector<int>, greater<int>> minQ;
    minQ.push(3); minQ.push(1); minQ.push(4);
    cout << minQ.top() << endl; // 输出 1
}

登录后复制

手动实现一个最小堆（数组模拟）

理解堆本质的关键是掌握「完全二叉树的数组表示」和「上浮（sift-up）/下沉（sift-down）」操作：

立即学习“C++免费学习笔记（深入）”；

• 对于下标为 i 的节点，左子节点下标 = 2*i + 1，右子节点 = 2*i + 2，父节点 = (i-1)/2
• 插入时：加到末尾，然后向上调整（与父节点比较并交换，直到满足堆序）
• 弹出堆顶时：把最后一个元素移到堆顶，再向下调整（与较小的子节点交换，直到满足堆序）

简易最小堆实现（不带泛型，便于理解）：

标签： go ai c++ ios stream 排序算法