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

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

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

priority_queue 的基本用法

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

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

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

小顶堆（最小值优先）：

std::priority_queue, std::greater> 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 等函数维护堆结构。

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

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

方法一：重载 operator

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

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

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

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

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

#include 
#include 
class MaxPriorityQueue {
private:
std::vector heap;
void sift_up(int idx) {
    while (idx youjiankuohaophpcn 0) {
        int parent = (idx - 1) / 2;
        if (heap[idx] zuojiankuohaophpcn= heap[parent]) break;
        std::swap(heap[idx], heap[parent]);
        idx = parent;
    }
}

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

        if (left zuojiankuohaophpcn n && heap[left] youjiankuohaophpcn heap[max_idx])
            max_idx = left;
        if (right zuojiankuohaophpcn n && heap[right] youjiankuohaophpcn 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 封装得很好，大多数情况下直接使用标准库即可。了解其背后是堆结构，以及如何通过比较函数控制排序方向，就能灵活应对各种优先级调度场景。




相关栏目：
    【
        最新资讯    】
    【
        网络优化    】
    【
        主机评测    】
    【
        网站百科    】
    【
        技术教程    】
    【
        文学范文    】
    【
        分站    】
    【
        网址导航    】
    【
        关于我们    】




            
 算法 是一个 自定义 就能 很好 对象 stream ios 弹出 堆 封装 数据类型 public c++ 标准库 结构体 有两种 operator int 第三个 升序 void 最小值 二叉树