如何用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, greater>
• 支持的操作：`push()`、`top()`、`pop()`、`empty()`、`size()`，时间复杂度均为 O(log n)

示例代码：

#include 
#include 
using namespace std;

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

    // 最小堆
    priority_queue, greater> 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
• 插入时：加到末尾，然后向上调整（与父节点比较并交换，直到满足堆序）
• 弹出堆顶时：把最后一个元素移到堆顶，再向下调整（与较小的子节点交换，直到满足堆序）

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

EasySub – AI字幕生成翻译工具

EasySub 是一款在线 AI 字幕生成器。 它提供AI语音识别、AI字幕生成、AI字幕翻译，本来就很简单的视频剪辑。

下载

#include 
#include 
using namespace std;

class MinHeap {
    vector heap;
    
    void siftDown(int i) {
        int n = heap.size();
        while (true) {
            int smallest = i;
            int left = 2*i + 1, right = 2*i + 2;
            if (left < n && heap[left] < heap[smallest]) smallest = left;
            if (right < n && heap[right] < heap[smallest]) smallest = right;
            if (smallest == i) break;
            swap(heap[i], heap[smallest]);
            i = smallest;
        }
    }
    
    void siftUp(int i) {
        while (i > 0) {
            int parent = (i-1)/2;
            if (heap[i] >= heap[parent]) break;
            swap(heap[i], heap[parent]);
            i = parent;
        }
    }

public:
    void push(int x) {
        heap.push_back(x);
        siftUp(heap.size()-1);
    }
    
    int top() {
        return heap.empty() ? -1 : heap[0];
    }
    
    void pop() {
        if (heap.empty()) return;
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) siftDown(0);
    }
    
    bool empty() { return heap.empty(); }
};

用 STL 堆算法手写堆操作（更底层）

C++ 提供了原始堆操作函数，可直接在 vector 或数组上构建/维护堆：

• make_heap(first, last)：将区间转为最大堆
• push_heap(first, last)：把末尾元素加入已建好的堆（调用前需先 push_back）
• pop_heap(first, last)：把堆顶移到末尾，剩余部分仍是堆（调用后需再 pop_back）
• 若要最小堆，传入 greater() 作为比较器

示例：

#include 
#include 
#include 
using namespace std;

int main() {
    vector v = {3, 1, 4, 1, 5};
    make_heap(v.begin(), v.end()); // 构建最大堆
    cout << v[0] << endl; // 5

    v.push_back(2);
    push_heap(v.begin(), v.end()); // 插入 2 并调整
    cout << v[0] << endl; // 5 还是最大值

    pop_heap(v.begin(), v.end()); // 5 移到末尾
    v.pop_back(); // 真正删除
    cout << v[0] << endl; // 新的最大值
}

常见误区和注意事项

初学堆容易踩坑，这些点值得留意：

• priority_queue 不支持随机访问或遍历，不能像 vector 那样用下标取中间元素
• 修改堆中某个元素后，不会自动重排——必须重新建堆或手动调整（STL 没提供 update 接口）
• 自定义类型需重载 运算符，或显式传入比较函数对象（如 greater>）
• 堆不是排序算法，但可以借助多次 pop 实现堆排序（O(n log n)）

不复杂但容易忽略。