【C++】优先队列（Priority Queue）全知道

Honkers · 2025-3-5 17:10:17

一、前言

二、优先队列（Priority Queue）：排队也有 “特权”？

（一）优先队列是啥？

（二）C++ 里怎么用优先队列？

（三）优先队列内部到底咋回事？

1. 秘密武器：二叉堆（Binary Heap）

2. 元素进出的 “魔法”

插入（push）元素

删除（pop）元素

（四）优先队列都在哪里大显身手？

1. 任务调度：谁先谁后安排好

2. 图算法中的 “指路明灯”

3. 数据压缩：让数据 “瘦身” 有妙招

一、前言

在 C++ 编程的奇妙世界里，数据结构就像是一个个功能各异的工具，帮助我们高效地处理和组织数据。而在众多的数据结构中，优先队列（Priority Queue）有着独特且重要的地位。它们各自有着独特的工作方式和应用场景，就如同特殊的钥匙，能为我们开启解决不同编程难题的大门。

👉 priority_queue文档介绍

二、优先队列（Priority Queue）：排队也有 “特权”？

（一）优先队列是啥？

想象一下，你在一个超级特别的队伍里。这个队伍里的人可不是按照先来后到排队的哦😉，而是每个人都有一个 “重要程度” 的标签🧾。比如说，在医院的急诊室，重伤的病人就比轻伤的病人更 “重要”，会优先得到救治。这就是优先队列的基本概念啦！它是一种数据结构，元素们按照自己的优先级排队，优先级最高的元素总是站在队伍的最前面，等着被处理。

（二）C++ 里怎么用优先队列？

标准模板库（STL）来帮忙
C++ 的 STL 给我们提供了一个超方便的priority_queue类。要用它的话，先把
头文件包含进来哦🧐。就像这样：
1. #include <iostream>
2. #include <queue>
4. int main() {
5. std::priority_queue<int> pq;
6. pq.push(5);
7. pq.push(10);
8. pq.push(3);
10. std::cout << "队首元素（最大值）: " << pq.top() << std::endl;
12. pq.pop();
14. std::cout << "队首元素（最大值）: " << pq.top() << std::endl;
16. return 0;
17. }
复制代码
这里我们创建了一个存整数的优先队列，默认情况下，它就像一个 “选大比赛”，最大的数在队首哦😎。每次push进去一个数，它就会自动按照大小排好队，top就能看到队首的最大值，pop就把最大值请出去啦。
想自定义规则？没问题！
要是你觉得默认的 “选大” 或者 “选小” 规则不合心意，也可以自己定规则哦😏。这时候就要用到比较函数或者函数对象啦。看下面这个例子，我们来创建一个小顶堆，让最小的数在队首：
1. #include <iostream>
2. #include <queue>
4. struct Compare {
5. bool operator()(int a, int b) {
6. return a > b;
7. }
8. };
10. int main() {
11. std::priority_queue<int, std::vector<int="">, Compare> pq;
12. pq.push(5);
13. pq.push(10);
14. pq.push(3);
16. std::cout << "队首元素（最小值）: " << pq.top() << std::endl;
18. pq.pop();
20. std::cout << "队首元素（最小值）: " << pq.top() << std::endl;
22. return 0;
23. }
复制代码
我们定义了一个Compare结构体，里面的operator()函数就是我们的比较规则。这样，优先队列就会按照我们定的规则来排队啦。

（三）优先队列内部到底咋回事？

1. 秘密武器：二叉堆（Binary Heap）

其实呀，priority_queue背后是靠二叉堆这个小助手来干活的呢😎。二叉堆就像一棵特别的树，每个节点都有自己的任务哦。对于大顶堆来说，父节点就像个小队长，它的值得比子节点的值大，这样才能保证队里最大的值在最上面呀。小顶堆呢，就刚好相反，父节点的值要小于等于子节点的值。

下面是个简单示意二叉堆节点结构体的代码，实际 STL 里的实现更复杂哦：

template<typename t="">
struct BinaryHeapNode {
T value;
BinaryHeapNode<t>* left;
BinaryHeapNode<t>* right;
BinaryHeapNode(T val) : value(val), left(nullptr), right(nullptr) {}
};

复制代码

2. 元素进出的 “魔法”

插入（push）元素

当有新元素要加进这个特别的队伍时，它会先站到队伍最后面哦。然后呢，它就开始和前面的人比，如果它比前面的人更 “重要”（按堆的规则），就和前面的人换位置，一直这么比下去，直到找到自己合适的位置，这就叫 “上溯（sift up）” 啦，就好像新队员要在队伍里找到自己的等级一样呢🧐。

下面是个简单示例代码片段，展示插入元素并维护二叉堆性质（假设已有上面那个二叉堆节点结构体定义哦）：

template<typename t="">
void siftUp(BinaryHeapNode<t>* node) {
while (node!= nullptr && node->parent!= nullptr && node->value > node->parent->value) {
// 交换节点和其父节点的值
swap(node->value, node->parent->value);
node = node->parent;
}
}
template<typename t="">
void pushToHeap(BinaryHeapNode<t>* root, T value) {
// 创建新节点并插入到堆的末尾
BinaryHeapNode<t>* newNode = new BinaryHeapNode<t>(value);
if (root == nullptr) {
root = newNode;
} else {
// 找到合适的位置插入新节点（这里简单假设插入到最后一个叶子节点位置）
BinaryHeapNode<t>* current = root;
while (current->left!= nullptr && current->right!= nullptr) {
current = current->left;
}
if (current->left == nullptr) {
current->left = newNode;
} else {
current->right = newNode;
}
// 对新插入的节点进行上溯操作
siftUp(newNode);
}
}

复制代码

删除（pop）元素

当要处理队首元素（也就是pop操作）时，队伍最后面的那个人会跑到队首来。但他可能不符合队首的要求呀，所以他就得和下面的人比，如果下面的人比他更 “适合” 队首，就和下面的人换位置，一直比到他找到自己合适的位置为止，这就是 “下溯（sift down）” 的过程啦😉。

下面是个简单示例代码片段，展示删除堆顶元素并维护二叉堆性质（同样假设已有上面那个二叉堆节点结构体定义哦）：

template<typename t="">
void siftDown(BinaryHeapNode<t>* node) {
while (node!= nullptr) {
BinaryHeapNode<t>* largest = node;
if (node->left!= nullptr && node->left->value > largest->value) {
largest = node->left;
}
if (node->right!= nullptr && node->right->value > largest->value) {
largest = node->right;
}
if (largest!= node) {
// 交换节点和最大子节点的值
swap(node->value, largest->value);
node = largest;
} else {
break;
}
}
}
template<typename t="">
T popFromHeap(BinaryHeapNode<t>* root) {
if (root == nullptr) {
throw runtime_error("堆为空");
}
T rootValue = root->value;
// 将堆的最后一个节点的值赋给堆顶
BinaryHeapNode<t>* lastNode = findLastNode(root);
root->value = lastNode->value;
// 删除最后一个节点（这里简单假设能正确删除，实际可能更复杂）
delete lastNode;
// 对新的堆顶节点进行下溯操作
siftDown(root);
return rootValue;
}

复制代码

在这代码里，popFromHeap函数就是用来删二叉堆的堆顶元素的，删完后用siftDown函数来保证二叉堆还是符合大顶堆的条件呢。

（四）优先队列都在哪里大显身手？

1. 任务调度：谁先谁后安排好

在操作系统或者任务管理系统里呀，任务就像一群等着被处理的小士兵👨‍✈️。每个任务都有自己的优先级，比如紧急任务优先级高，普通任务优先级低。优先队列就像个聪明的指挥官，把任务按优先级排好队，处理器就可以按顺序先处理重要的任务啦，这样系统就能高效地运行咯，就跟快递分拣中心会优先处理加急件一样呢😎。

下面是个简单的任务调度模拟代码示例，用优先队列来实现任务按优先级排序处理哦：

#include <iostream>
#include <queue>
#include <string>
using namespace std;
// 任务结构体
struct Task {
string name;
int priority;
Task(const string& n, int p) : name(n), priority(p) {}
};
// 自定义比较函数，按照任务优先级从高到低排序
struct TaskCompare {
bool operator()(const Task& t1, const Task& t2) {
return t1.priority < t2.priority;
}
};
int main() {
// 创建任务优先队列
priority_queue<task, vector<task="">, TaskCompare> taskQueue;
// 添加一些任务到队列
taskQueue.push(Task("任务1", 5));
taskQueue.push(Task("任务2", 3));
taskQueue.push(Task("任务3", 8));
// 模拟处理器处理任务
while (!taskQueue.empty()) {
Task currentTask = taskQueue.top();
cout << "正在处理任务: " << currentTask.name << "，优先级: " << currentTask.priority << endl;
taskQueue.pop();
}
return 0;
}

复制代码

在这个例子里，我们先定义了Task结构体来表示任务，有任务名字和优先级两个属性哦。然后通过自定义的TaskCompare比较函数，让优先队列按任务优先级从高到低给任务排队。最后模拟处理器依次处理队列里的任务呢。

2. 图算法中的 “指路明灯”

在一些图算法里呀，比如 Dijkstra 算法求单源最短路径，优先队列可真是个大功臣呢🧐。想象一下你在一个迷宫里找出口，每个路口都有不同的距离标记。算法得不断选离起点最近的未访问路口继续探索呀，优先队列就能很快告诉算法哪个路口离起点最近，就像个导航仪一样，让算法能高效地找到最短路径呢😉。

下面是个简单的 Dijkstra 算法示例，用优先队列来辅助找到从一个源点到其他节点的最短路径哦（这只是个简化示例，实际应用可能更复杂啦）：

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
// 节点结构体
struct Node {
int id;
vector<node*> neighbors;
int distance;
Node(int i) : id(i), distance(INT_MAX) {}
};
// 自定义比较函数，按照节点距离从小到大排序
struct NodeCompare {
bool operator()(const Node* n1, const Node* n2) {
return n1->distance > n2->distance;
}
};
// Dijkstra算法实现
void dijkstra(Node* source) {
// 创建优先队列，按照节点距离排序
priority_queue<node*, vector<node*="">, NodeCompare> pq;
// 将源点加入队列，并设置其距离为0
source->distance = 0;
pq.push(source);
// 用于记录已访问过的节点
unordered_map<int, bool=""> visited;
while (!pq.empty()) {
Node* currentNode = pq.top();
pq.pop();
// 如果节点已经访问过，跳过
if (visited[currentNode->id]) {
continue;
}
// 标记当前节点为已访问
visited[currentNode->id] = true;
// 更新当前节点邻居的距离
for (Node* neighbor : currentNode->neighbors) {
int newDistance = currentNode->日前距离 + 1;
if (newDistance < neighbor->distance) {
neighbor->distance = newDistance;
pq.push(neighbor);
}
}
}
}
int main() {
// 创建一些节点
Node* node1 = new Node(1);
Node* node2 = new Node(2);
Node* node3 = new Node(3);
// 构建节点之间的连接关系
node1->日前邻居.push_back(node2);
node1->日前邻居.push_back(node3);
node2->日前邻居.push_back(node3);
// 运行Dijkstra算法
dijkstra(node1);
// 输出节点到源点的距离
cout << "节点2到源点的距离: " << node2->distance << endl;
cout << "节点3到源点的距离: " << node3->distance << endl;
return 0;
}

复制代码

在这个例子里，我们先定义了Node结构体来表示图中的节点，有节点 ID、邻居节点列表和到源点的距离这些属性哦。然后通过自定义的NodeCompare比较函数，让优先队列按节点距离从小到大给节点排队。接着在 Dijkstra 算法里，利用优先队列高效地选离源点最近的未访问节点进行处理，这样就能找到从源点到其他节点的最短路径啦。

3. 数据压缩：让数据 “瘦身” 有妙招

在哈夫曼编码这个数据压缩方法里呀，优先队列也发挥着重要作用呢😎。它就像个聪明的小助手，帮我们构建哈夫曼树。在构建过程中，它会选出现频率最低的两个字符，把它们合并成一个新的 “组合字符”，然后继续选频率最低的进行合并，直到构建出完整的哈夫曼树。最后根据这棵树给每个字符分配不同长度的编码，这样就能让数据占用更少的空间啦😃。

下面是个简单的哈夫曼编码构建示例，用优先队列来辅助构建哈夫曼树哦（这也是个简化示例，实际应用可能更复杂啦）：

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
// 哈夫曼树节点结构体
struct HuffmanNode {
char data;
int frequency;
HuffmanNode* left;
HuffmanNode* left右;
HuffmanNode(char d, int f) : data(d), frequency(f), left(nullptr), left右(nullptr) {}
}
// 自定义比较函数，按照节点频率从小到大排序
struct HuffmanNodeCompare {
bool operator()(const HuffmanNode* n1, const HuffmanNode* n2) {
return n1->frequency > n2->frequency;
}
};
// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(const unordered_map<char, int="">& frequencyMap) {
// 创建优先队列，按照节点频率排序
priority_queue<huffmannode*, vector<h夫曼node*="">, HuffmanNodeCompare> pq;
// 将每个字符及其频率对应的节点加入队列
for (const auto& pair : frequencyMap) {
pq.push(new HuffmanNode(pair.first, pair.second));
}
while (pq.size() > 1) {
// 取出频率最低的两个节点
HuffmanNode* leftNode = pq.top();
pq.pop();
HuffmanNode* rightNode = pq.top();
pq.pop();
// 创建新的父节点，频率为两个子节点频率之和
HuffmanNode* parentNode = new HuffmanNode('\0', leftNode->frequency + rightNode->frequency);
parentNode->left = leftNode;
parentNode->right = rightNode;
// 将父节点加入队列
pq.push(parentNode);
}
return pq.top();
}
int main() {
// 假设这里有个字符频率映射表
unordered_map<char, int=""> frequencyMap = {
{'a', 5},
{'b', 3},
{'c', 8}
};
// 构建哈夫曼树
HuffmanNode* huffmanTree = buildHuffmanTree(frequencyMap);
// 这里可以根据哈夫曼树进一步处理，比如生成编码等，但为了简化先不展示啦
return 0;
}

复制代码

在这个例子里，我们先定义了HuffmanNode结构体来表示哈夫曼树的节点，有字符数据、频率、左右子节点这些属性哦。然后通过自定义的HuffmanNodeCompare比较函数，让优先队列按节点频率从小到大给节点排队。接着在构建哈夫曼树的过程中，利用优先队列选出频率最低的两个节点合并成新节点，一直重复这个过程直到构建出完整的哈夫曼树呢。

[C.C++] 【C++】优先队列（Priority Queue）全知道

一、前言

二、优先队列（Priority Queue）：排队也有 “特权”？

（一）优先队列是啥？

（二）C++ 里怎么用优先队列？

（三）优先队列内部到底咋回事？

1. 秘密武器：二叉堆（Binary Heap）

2. 元素进出的 “魔法”

插入（push）元素

删除（pop）元素

（四）优先队列都在哪里大显身手？

1. 任务调度：谁先谁后安排好

2. 图算法中的 “指路明灯”

3. 数据压缩：让数据 “瘦身” 有妙招

本帖子中包含更多资源

新人须知

常见问题

关于我们