C++中priority_queue的实现_C/C++

一、priority_queue 核心定义

std::priority_queue（优先队列）是 c++ stl 中的适配器容器（基于其他容器实现），本质是一个「堆结构」——队列中的元素会按照优先级自动排序，而非按插入顺序。

核心特性：每次访问/弹出的都是优先级最高的元素（默认是最大值，可自定义为最小值）；
底层实现：默认基于 std::vector，也可指定 std::deque（不支持 std::list，因为堆需要随机访问）；
头文件：必须包含 <queue>。

二、基本用法（默认大顶堆）

1. 初始化与核心操作

#include <iostream>
#include <queue> // 必须包含
using namespace std;
int main() {
    // 1. 初始化：默认是大顶堆（最大值优先）
    priority_queue<int> pq;
    // 2. 插入元素（push）：o(log n) 复杂度
    pq.push(3);
    pq.push(1);
    pq.push(5);
    pq.push(2);
    // 3. 访问队首（top）：返回优先级最高的元素（最大值）
    cout << "队首元素（最大值）：" << pq.top() << endl; // 输出：5
    // 4. 弹出队首（pop）：删除优先级最高的元素，o(log n) 复杂度
    pq.pop();
    cout << "弹出后队首：" << pq.top() << endl; // 输出：3
    // 5. 判空（empty）、大小（size）
    cout << "是否为空：" << (pq.empty() ? "是" : "否") << endl; // 输出：否
    cout << "元素个数：" << pq.size() << endl; // 输出：3
    // 6. 遍历（无迭代器，需弹出所有元素）
    while (!pq.empty()) {
        cout << pq.top() << " "; // 输出：3 2 1
        pq.pop();
    }
    return 0;
}

2. 关键说明

top()：仅返回队首元素，不删除；pop()：仅删除队首元素，无返回值（需先 top() 再 pop()）；
无 clear() 成员函数：清空优先队列需手动弹出所有元素，或赋值空队列（pq = priority_queue<int>();）；
不支持随机访问：无法直接访问中间元素，只能通过 top() 访问队首。

三、自定义优先级（小顶堆/自定义规则）

默认的 priority_queue 是「大顶堆」（最大值优先），可通过以下方式修改优先级：

1. 实现小顶堆（最小值优先）

方式1：指定比较函数 greater<t>

#include <iostream>
#include <queue>
#include <vector> // 显式指定底层容器
using namespace std;

int main() {
    // 模板参数：<元素类型, 底层容器类型, 比较函数>
    priority_queue<int, vector<int>, greater<int>> pq;

    pq.push(3);
    pq.push(1);
    pq.push(5);
    pq.push(2);

    cout << "小顶堆队首（最小值）：" << pq.top() << endl; // 输出：1
    pq.pop();
    cout << "弹出后队首：" << pq.top() << endl; // 输出：2

    return 0;
}

方式2：对元素取反（适用于简单类型）

// 插入时取反，弹出时再取反，模拟小顶堆
priority_queue<int> pq;
pq.push(-3);
pq.push(-1);
pq.push(-5);
pq.push(-2);
cout << "模拟小顶堆队首：" << -pq.top() << endl; // 输出：1

2. 自定义结构体/类的优先级

需重载比较运算符（operator<），或自定义比较函数。

示例：结构体按指定字段排序

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

// 定义结构体：存储学生姓名和分数
struct student {
    string name;
    int score;

    // 重载 < 运算符（注意：优先队列用 < 比较，且规则与直觉相反）
    // 需求：分数高的优先级高（大顶堆）
    bool operator<(const student& other) const {
        // 若 this->score < other.score，则 other 优先级更高
        return score < other.score;
    }
};

int main() {
    priority_queue<student> pq;
    pq.push({"alice", 85});
    pq.push({"bob", 92});
    pq.push({"charlie", 78});

    // 输出优先级最高的元素（分数最高的bob）
    cout << "最高分：" << pq.top().name << " " << pq.top().score << endl; // bob 92
    pq.pop();
    cout << "次高分：" << pq.top().name << " " << pq.top().score << endl; // alice 85

    return 0;
}

自定义比较函数（适用于复杂规则）

#include <iostream>
#include <queue>
#include <string>
#include <functional> // 需包含（for function）
using namespace std;

struct student {
    string name;
    int score;
};

// 自定义比较函数：分数低的优先级高（小顶堆）
struct comparestudent {
    bool operator()(const student& a, const student& b) {
        return a.score > b.score; // 与小顶堆的 greater 逻辑一致
    }
};

int main() {
    priority_queue<student, vector<student>, comparestudent> pq;
    pq.push({"alice", 85});
    pq.push({"bob", 92});
    pq.push({"charlie", 78});

    cout << "最低分：" << pq.top().name << " " << pq.top().score << endl; // charlie 78

    return 0;
}

四、底层原理：堆结构

priority_queue 的核心是二叉堆（完全二叉树），所有操作均基于堆的特性：

插入（push）：将元素添加到堆尾，然后「上浮（sift up）」调整堆，确保父节点优先级高于子节点（o(log n)）；
弹出（pop）：将堆顶元素与堆尾元素交换，删除堆尾，然后「下沉（sift down）」调整堆（o(log n)）；
访问队首（top）：直接返回堆顶元素（o(1)）。

五、常见应用场景

top k 问题：如找数组中前 k 大/前 k 小的元素（用小顶堆存前 k 大，大顶堆存前 k 小）；

// 示例：找数组中前3大的元素
vector<int> nums = {5, 2, 9, 1, 7, 6, 8};
priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
for (int num : nums) {
    pq.push(num);
    if (pq.size() > 3) pq.pop(); // 保持堆大小为3
}
// 此时堆中是前3大的元素（7,8,9），但顺序是从小到大

贪心算法：如任务调度、哈夫曼编码、最短路径（dijkstra 算法）；
实时排序：需频繁获取最大值/最小值的场景（如事件优先级处理）。

六、注意事项

底层容器限制：只能用支持随机访问的容器（vector/deque），不能用 list（无随机访问）；
比较函数规则：
- 默认 less<t>：大顶堆（a < b 则 b 优先级高）；
- greater<t>：小顶堆（a > b 则 b 优先级高）；
性能：插入/弹出为 o(log n)，访问队首为 o(1)，遍历需弹出所有元素（o(n log n)）；
线程安全：无内置线程安全，多线程需手动加锁。

总结

核心特性	说明
排序规则	默认大顶堆，可自定义为小顶堆/自定义规则
核心操作	push（插入）、top（查队首）、pop（删队首）
时间复杂度	push/pop: o(log n)，top: o(1)
底层容器	默认 vector，可指定 deque
适用场景	top k、贪心算法、实时优先级处理

priority_queue 是 c++ 中处理「优先级排序」的核心容器，重点掌握自定义优先级的两种方式（greater<t>/自定义比较函数），以及 top k 问题的经典用法。

到此这篇关于c++中priority_queue的实现的文章就介绍到这了,更多相关c++ priority_queue内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！