如何用c++实现一个优先队列 priority_queue和堆【数据结构】-C++-PHP中文网

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

尼克

发布： 2025-12-23 12:51:21

原创

215人浏览过

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

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

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

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

星绘

豆包旗下 AI 写真、P 图、换装和视频生成

429

查看详情

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

class MinHeap {
    vector<int> 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<t>()</t> 作为比较器

示例：

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> 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; // 新的最大值
}

登录后复制