C++优先队列的使用
时间: 2023-12-03 12:04:26 浏览: 157
C++中的优先队列(priority queue)是一种特殊的队列,它根据元素的优先级进行排序。在C++中,优先队列使用堆(heap)数据结构来实现。
在C++中使用优先队列,你需要包含头文件<queue>。优先队列的定义格式如下:
```
priority_queue<元素类型, 容器类型, 比较函数> queue_name;
```
其中,元素类型是指优先队列中存储的元素类型,容器类型是指存储元素的容器类型(默认为vector),比较函数是用于确定元素优先级的比较函数(默认为less<元素类型>)。
对于整数类型的优先队列,可以使用以下代码进行定义和使用:
```
#include <queue>
#include <iostream>
int main() {
std::priority_queue<int> pq; // 默认为大根堆
pq.push(4);
pq.push(2);
pq.push(7);
while (!pq.empty()) {
int top = pq.top();
std::cout << top << " ";
pq.pop();
}
return 0;
}
```
输出结果为:7 4 2
对于自定义类型的优先队列,你可以通过自定义比较函数来确定元素的优先级。比如,根据y的值降序排序的测试代码如下:
```
#include <queue>
#include <iostream>
struct tmp {
int x, y;
};
struct comp {
bool operator()(tmp &a, tmp &b) {
return a.y < b.y; // 根据y的值降序排序
}
};
int main() {
std::priority_queue<tmp, std::vector<tmp>, comp> pq;
tmp t1 = {1, 5};
tmp t2 = {2, 3};
tmp t3 = {3, 9};
pq.push(t1);
pq.push(t2);
pq.push(t3);
while (!pq.empty()) {
tmp top = pq.top();
std::cout << "(" << top.x << "," << top.y << ") ";
pq.pop();
}
return 0;
}
```
输出结果为:(3,9) (1,5) (2,3)
总结一下,C++的优先队列是一种根据元素的优先级排序的数据结构。你可以使用默认的比较函数或者自定义比较函数来确定元素的优先级。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [C++优先队列的使用方法](https://blog.csdn.net/qq_42712351/article/details/94986621)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]
阅读全文