c++怎么实现一个优先队列_c++优先队列(priority_queue)的原理与实现-C++-PHP中文网

c++怎么实现一个优先队列_c++优先队列(priority_queue)的原理与实现

冰火之心

发布： 2025-12-09 13:18:07

原创

653人浏览过

C++中priority_queue是基于堆的容器适配器，默认为大顶堆，自动排序并优先弹出最大值；通过std::greater可改为小顶堆；底层使用vector存储，借助push_heap和pop_heap维护堆性质；支持自定义类型，需重载operator

c++怎么实现一个优先队列_c++优先队列(priority_queue)的原理与实现

在C++中，priority_queue 是一个基于堆（heap）实现的容器适配器，能够自动将元素按照优先级排序，默认是大顶堆（最大值优先）。它并不像普通队列那样遵循先进先出原则，而是每次取出当前优先级最高的元素。

priority_queue 的基本用法

在 C++ 标准库中，priority_queue 定义在头文件中。使用方式如下：

默认大顶堆（最大值优先）：

#include <queue>
#include <iostream>
<p>std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
while (!pq.empty()) {
std::cout << pq.top() << " ";  // 输出：30 20 10
pq.pop();
}</p>

登录后复制

小顶堆（最小值优先）：

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

std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

登录后复制

这里第三个模板参数指定比较函数对象，使用 std::greater 实现升序，即最小值在 top。

priority_queue 的底层原理

priority_queue 实际上是一个堆结构的封装，通常基于完全二叉树，使用数组（如 vector）存储。其核心操作依赖于两个算法：

向上调整（push_heap）：插入新元素后，从底部向上调整以维持堆性质。
向下调整（pop_heap）：删除堆顶后，将最后一个元素移到顶部，再向下调整。

这些操作的时间复杂度为 O(log n)，而访问堆顶是 O(1)。

C++ STL 中的 priority_queue 默认使用 std::vector 作为底层容器，并通过 std::make_heap、std::push_heap、std::pop_heap 等函数维护堆结构。

Seede AI

AI 驱动的设计工具

713

查看详情

自定义数据类型的优先队列

如果要存储自定义类型（如结构体），需要提供比较逻辑。有两种方式：

方法一：重载 operator

struct Person {
    int age;
    std::string name;
    // 重载小于号，用于大顶堆（年龄大的优先）
    bool operator<(const Person& p) const {
        return age < p.age;
    }
};
std::priority_queue<Person> pq;

登录后复制

方法二：自定义比较结构体

struct Compare {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age;  // 大顶堆
    }
};
std::priority_queue<Person, std::vector<Person>, Compare> pq;

登录后复制

手动实现一个简单的优先队列

虽然标准库提供了 priority_queue，但理解其手动实现有助于掌握原理。以下是一个简化版的大顶堆实现：

#include <vector>
#include <iostream>
<p>class MaxPriorityQueue {
private:
std::vector<int> heap;</p><pre class='brush:php;toolbar:false;'>void sift_up(int idx) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (heap[idx] <= heap[parent]) break;
        std::swap(heap[idx], heap[parent]);
        idx = parent;
    }
}

void sift_down(int idx) {
    int n = heap.size();
    while (idx < n) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        int max_idx = idx;

        if (left < n && heap[left] > heap[max_idx])
            max_idx = left;
        if (right < n && heap[right] > heap[max_idx])
            max_idx = right;

        if (max_idx == idx) break;
        std::swap(heap[idx], heap[max_idx]);
        idx = max_idx;
    }
}

登录后复制

public: void push(int val) { heap.push_back(val); sift_up(heap.size() - 1); }

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

int top() { return heap.empty() ? -1 : heap[0]; }
bool empty() { return heap.empty(); }

登录后复制

};

这个实现包含了基本的插入、删除和访问操作，使用数组模拟完全二叉树结构，通过 sift_up 和 sift_down 维护堆性质。

基本上就这些。C++ 的 priority_queue 封装得很好，大多数情况下直接使用标准库即可。了解其背后是堆结构，以及如何通过比较函数控制排序方向，就能灵活应对各种优先级调度场景。

以上就是c++++怎么实现一个优先队列_c++优先队列(priority_queue)的原理与实现的详细内容，更多请关注php中文网其它相关文章！