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

穿越時空

发布时间：2025-12-27 16:17:08

833人浏览过

来源于php中文网

原创

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

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

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();
}

自定义类型与比较函数

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

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

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)，而构建过程类似于堆排序中的建堆阶段。

Explainpaper

阅读学术论文的更好方法，你的学术论文阅读助手。

下载

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

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

这正是 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 编码、任务调度等需要优先处理最大/最小元素的场合。

为什么Golang的函数参数都是值传递分析指针与引用传递的区别

如何为C++搭建区块链节点开发环境 Hyperledger Fabric集成

Golang的包管理机制如何运作介绍go mod的依赖管理方式

为什么Golang要禁止循环引用讲解编译器的包依赖检查规则

Golang的select语句如何实现多路复用剖析非阻塞IO处理机制

c++速学教程(入门到精通)

c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

go 编码 ai c++ ios stream 标准库结构体接口堆对象算法

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：c++中的fold expressions(折叠表达式)是什么_c++17简化可变参数模板【语法糖】下一篇：c++怎么实现socket网络编程_c++ TCP/IP通信协议栈与客户端实现【案例】

作者最新文章

Mac无法连接Wi-Fi怎么办？（5种解决方法）

2025-12-27 13:35

edge浏览器如何重置所有标志 edge浏览器恢复实验性功能【方法】

2025-12-27 13:39

Excel怎么制作工资条 Excel一键生成工资条的两种方法【教程】

2025-12-27 13:40

sublime怎么配置RubyOnRails开发环境_sublime安装Rails插件【教程】

2025-12-27 13:41

百度网盘如何开启离线下载_百度网盘添加BT任务下载教程【技巧】

2025-12-27 13:42

c++怎么解决循环引用问题_c++ weak_ptr与shared_ptr配合使用【方法】

2025-12-27 13:48

Win10右下角网络图标消失怎么办 Win10任务栏系统图标恢复【解决】

2025-12-27 13:58

sublime怎么实现代码块快速包裹_sublime快捷键添加标签环绕【方法】

2025-12-27 14:02

c++如何实现访问者模式 c++设计模式之Visitor【实例】

2025-12-27 14:04

sublime如何实时预览Markdown文件 _sublime MarkdownEditing插件教程

2025-12-27 14:07

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PDF 文档

相关专题

golang结构体相关大全

本专题整合了golang结构体相关大全，想了解更多内容，请阅读专题下面的文章。

193

2025.06.09

golang结构体方法

本专题整合了golang结构体相关内容，请阅读专题下面的文章了解更多。

184

2025.07.04

硬盘接口类型介绍

硬盘接口类型有IDE、SATA、SCSI、Fibre Channel、USB、eSATA、mSATA、PCIe等等。详细介绍：1、IDE接口是一种并行接口，主要用于连接硬盘和光驱等设备，它主要有两种类型：ATA和ATAPI，IDE接口已经逐渐被SATA接口；2、SATA接口是一种串行接口，相较于IDE接口，它具有更高的传输速度、更低的功耗和更小的体积；3、SCSI接口等等。

985

2023.10.19