C++优先队列详解（从零开始掌握priority_queue的使用与实现）

什么是优先队列？

优先队列是一种特殊的队列，其中每个元素都有一个“优先级”。与普通队列“先进先出”（FIFO）不同，优先队列总是先弹出优先级最高的元素。

在C++标准模板库（STL）中，优先队列是通过 std::priority_queue 实现的，底层通常基于堆（Heap）结构（通常是二叉堆）。默认情况下，它是一个最大堆——即顶部元素是最大的。

1. 基本使用：STL中的priority_queue

要使用C++优先队列，首先需要包含头文件：

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

下面是一个简单的例子，展示如何插入和弹出元素：

#include <iostream>#include <queue>using namespace std;int main() {    // 创建一个默认的最大堆优先队列    priority_queue<int> pq;    // 插入元素    pq.push(10);    pq.push(30);    pq.push(20);    // 输出顶部元素（最大值）    cout << "Top element: " << pq.top() << endl; // 输出 30    // 弹出顶部元素    pq.pop();    cout << "New top: " << pq.top() << endl; // 输出 20    return 0;}

2. 自定义比较方式：最小堆

默认的 priority_queue 是最大堆。如果我们想要最小堆（即顶部是最小元素），可以通过自定义比较器实现。

方法一：使用 greater<int>

#include <iostream>#include <queue>#include <functional> // 需要包含 functionalusing namespace std;int main() {    // 创建最小堆    priority_queue<int, vector<int>, greater<int>> minPQ;    minPQ.push(10);    minPQ.push(30);    minPQ.push(20);    cout << "Top (smallest): " << minPQ.top() << endl; // 输出 10    return 0;}

这里模板参数含义如下：

• int：存储的数据类型
• vector<int>：底层容器（默认就是 vector）
• greater<int>：比较函数对象，表示“小的优先”

3. 自定义结构体的优先队列

在实际开发中，我们经常需要对自定义类型（如结构体）使用优先队列。例如，按学生的成绩排序。

#include <iostream>#include <queue>#include <string>using namespace std;struct Student {    string name;    int score;    // 重载小于号：用于最大堆（分数高的优先）    bool operator < (const Student& other) const {        return score < other.score; // 注意：priority_queue是最大堆，所以这里“小于”表示优先级低    }};int main() {    priority_queue<Student> pq;    pq.push({"Alice", 85});    pq.push({"Bob", 92});    pq.push({"Charlie", 78});    while (!pq.empty()) {        cout << pq.top().name << ": " << pq.top().score << endl;        pq.pop();    }    // 输出顺序：Bob(92), Alice(85), Charlie(78)    return 0;}

注意：由于 priority_queue 默认使用 less<T> 比较，而它调用的是 operator<，所以为了让高分优先，我们在 operator< 中返回 score < other.score。这样，分数大的“更大”，就会排在堆顶。

4. 手动实现堆（加深理解）

虽然STL已经提供了高效的 priority_queue，但理解其底层原理有助于提升编程能力。下面是一个简易的最大堆实现：

#include <iostream>#include <vector>using namespace std;class MaxHeap {private:    vector<int> heap;    void heapifyUp(int index) {        if (index == 0) return;        int parent = (index - 1) / 2;        if (heap[parent] < heap[index]) {            swap(heap[parent], heap[index]);            heapifyUp(parent);        }    }    void heapifyDown(int index) {        int left = 2 * index + 1;        int right = 2 * index + 2;        int largest = index;        if (left < heap.size() && heap[left] > heap[largest])            largest = left;        if (right < heap.size() && heap[right] > heap[largest])            largest = right;        if (largest != index) {            swap(heap[index], heap[largest]);            heapifyDown(largest);        }    }public:    void push(int val) {        heap.push_back(val);        heapifyUp(heap.size() - 1);    }    void pop() {        if (heap.empty()) return;        heap[0] = heap.back();        heap.pop_back();        if (!heap.empty()) heapifyDown(0);    }    int top() {        return heap.empty() ? -1 : heap[0];    }    bool empty() {        return heap.empty();    }};// 测试int main() {    MaxHeap h;    h.push(10);    h.push(30);    h.push(20);    cout << h.top() << endl; // 30    h.pop();    cout << h.top() << endl; // 20    return 0;}

这个手动实现虽然不如STL高效，但它清晰展示了C++堆结构的工作原理：插入时向上调整（heapifyUp），删除时向下调整（heapifyDown）。

总结

通过本教程，你已经掌握了：

• 如何使用STL中的 priority_queue
• 如何创建最小堆和最大堆
• 如何对自定义类型进行优先级排序
• 堆的基本原理及简易实现

无论是面试还是实际项目开发，STL优先队列教程中的这些知识都非常实用。建议多动手练习，加深理解！

希望这篇关于 C++优先队列 的详细教程能帮助你顺利入门并掌握这一强大工具！