c++如何使用std::priority_queue_c++优先队列容器使用详解-C++-PHP中文网

c++如何使用std::priority_queue_c++优先队列容器使用详解

穿越時空

发布： 2025-10-31 21:19:01

原创

446人浏览过

std::priority_queue是C++中基于堆的容器适配器，默认为最大堆，可通过std::greater或自定义比较实现最小堆及复杂优先级逻辑，常用于Top K、Dijkstra等场景。

c++如何使用std::priority_queue_c++优先队列容器使用详解

在C++中，std::priority_queue 是一个基于堆结构实现的容器适配器，用于自动维护元素的优先级顺序。默认情况下，它是一个最大堆，即每次取出的元素是当前队列中最大的。下面详细介绍其基本用法、自定义比较方式以及常见应用场景。

基本用法

std::priority_queue 定义在 <queue> 头文件中，使用时需要包含该头文件。其模板参数有三个，但通常只使用前两个：

T：存储元素的数据类型
Container：底层容器类型，默认为 std::vector<T>
Compare：比较函数对象，默认为 std::less<T>（最大堆）

基本声明方式如下：

priority_queue pq; // 最大堆，顶部是最大值

常用操作接口：

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

pq.push(x)：插入元素 x
pq.pop()：删除堆顶元素（不返回）
pq.top()：返回堆顶元素
pq.empty()：判断是否为空
pq.size()：返回元素个数

示例代码：

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

int main() {
    priority_queue pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);

    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    // 输出：30 20 10
    return 0;
}

创建最小堆

默认是最大堆，若要实现最小堆，可以使用 std::greater 作为比较函数：

priority_queue, greater> min_pq;

此时堆顶是当前最小元素。示例：

min_pq.push(10);
min_pq.push(30);
min_pq.push(20);
cout << min_pq.top(); // 输出 10

自定义比较函数（结构体或类）

当处理自定义类型（如结构体）时，需要提供比较逻辑。可以通过重载 operator< 或定义比较结构体实现。

AI图像编辑器

使用文本提示编辑、变换和增强照片

查看详情

方法一：重载 operator<

struct Person {
    int age;
    string name;
    bool operator<(const Person& p) const {
        return age < p.age; // 年龄大的优先级高（最大堆）
    }
};

priority_queue pq;
pq.push({25, "Alice"});
pq.push({30, "Bob"});
cout << pq.top().name; // 输出 Bob

方法二：自定义比较结构体（推荐用于复杂逻辑）

struct Compare {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age; // 最大堆
    }
};

priority_queue, Compare> pq;

注意：在自定义比较结构体中，如果想让某个值“优先级更高”，需理解：返回 true 表示 a 的优先级低于 b，即 b 应该更靠近堆顶。例如使用 less 时，a < b 意味着 a 在 b 下面。

常见应用场景

std::priority_queue 常用于以下场景：

堆排序：利用堆特性进行高效排序
Dijkstra 算法：取出距离最短的节点
Huffman 编码：合并频率最小的两棵树
Top K 问题：维护前 K 个最大/最小值

例如求 Top K 最小元素，可以用最大堆维护 K 个元素：

priority_queue pq; // 最大堆
for (int x : nums) {
    if (pq.size() < k) {
        pq.push(x);
    } else if (x < pq.top()) {
        pq.pop();
        pq.push(x);
    }
}

基本上就这些。std::priority_queue 使用简单，配合自定义比较能应对大多数优先级调度需求，不需要手动维护堆结构，效率高且不易出错。

以上就是c++++如何使用std::priority_queue_c++优先队列容器使用详解的详细内容，更多请关注php中文网其它相关文章！