c++的std::priority_queue如何使用_c++优先队列与堆排序

std::priority_queue是C++中基于堆的容器适配器，默认实现大顶堆，可通过指定比较函数如std::greater构建小顶堆，支持自定义类型与比较规则，底层利用堆算法维护堆序，插入和弹出时间复杂度均为O(log n)，其行为类似堆排序中的动态维护过程，提供高效的最大（或最小）元素访问，适用于任务调度、Dijkstra等需优先处理极值的场景。

std::priority_queue 是 C++ 标准库中一个基于堆（heap）实现的容器适配器，常用于快速获取最大（或最小）元素。它底层通常使用 std::vector 或 std::deque，并通过堆算法维护堆序性质。它和堆排序有密切关系，但用途和行为有所不同。

基本用法：默认是大顶堆

默认情况下，std::priority_queue 是一个大顶堆，即每次 top() 返回当前最大值。

#include 
#include 

int main() {
    std::priority_queue pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(2);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";  // 输出: 4 3 2 1
        pq.pop();
    }
}

如何创建小顶堆

通过指定比较函数对象来改变排序规则。例如，使用 std::greater 实现小顶堆。

#include 
#include 
#include   // std::greater

std::priority_queue, std::greater> min_pq;
min_pq.push(3);
min_pq.push(1);
min_pq.push(4);
min_pq.push(2);

while (!min_pq.empty()) {
    std::cout << min_pq.top() << " ";  // 输出: 1 2 3 4
    min_pq.pop();
}

自定义类型与比较函数

对于结构体或类，需要提供比较方式。可以通过重载操作符或传入仿函数。

struct Task {
    int priority;
    std::string name;
};

// 自定义比较：优先级数值越小，优先级越高（用于小顶堆）
struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        return a.priority > b.priority;  // 注意：这里 > 表示更小的优先级先出
    }
};

std::priority_queue, CompareTask> task_queue;
task_queue.push({2, "Low"});
task_queue.push({1, "High"});
task_queue.push({3, "Normal"});

while (!task_queue.empty()) {
    std::cout << task_queue.top().name << " ";
    task_queue.pop();
}
// 输出: High Low Normal

priority_queue 与堆排序的关系

std::priority_queue 的内部实现依赖于堆结构，插入（push）和弹出（pop）操作的时间复杂度都是 O(log n)，而构建过程类似于堆排序中的建堆阶段。

堆排序的过程可以看作是：

将数组调整为堆（建堆）
反复取出堆顶并调整剩余元素

这正是 priority_queue 在背后做的事。如果你手动对一个 vector 使用 std::make_heap、std::push_heap 和 std::pop_heap，就相当于实现了 priority_queue 的功能。

#include 
#include 
#include 

std::vector v = {3, 1, 4, 2};
std::make_heap(v.begin(), v.end());  // 建大顶堆

while (!v.empty()) {
    std::cout << v.front() << " ";   // 输出最大值
    std::pop_heap(v.begin(), v.end()); // 将最大移到末尾
    v.pop_back();                      // 移除末尾
}
// 输出: 4 3 2 1

可以看到，这个过程和 priority_queue 的行为一致。因此可以说，priority_queue 提供了堆排序中“动态维护堆”的抽象接口，适合在运行时不断插入删除的场景。

基本上就这些。std::priority_queue 简化了堆的操作，避免手动调用堆算法，适用于 Dijkstra、Huffman 编码、任务调度等需要优先处理最大/最小元素的场合。

# go # 编码 # ai # c++ # ios # stream # 标准库 # 结构体 # 接口 # 堆 # 对象 # 算法 # 自定义 # 适用于 # 弹出 # 都是 # 是一个 # 如果你 # 可以说 # 均为 # 有所不同 # 可以通过

返回目录在线咨询

上一篇：公司网站服务器租用：性能稳定性和 uptime 保障有多重要？
下一篇：铁岭小学英语教材什么版本,辽宁中小学都用什么版本的课本？

您的项目需求