priority_queue
是 C++ 标准模板库(STL)中的一种容器适配器,它提供了一个基于优先级的队列。这意味着它存储的元素是按照一定的优先级进行排序的,每次访问队头元素都是当前队列中优先级最高的元素。
在 C++ 中,priority_queue
通常使用堆(heap)来实现,堆是一种特殊的二叉树结构,满足堆的性质。C++ 中的 priority_queue
默认使用大顶堆,也就是队头元素是最大的元素。你可以通过提供比较函数来使用小顶堆。
以下是一个简单的示例,演示了如何使用 priority_queue:
#include <iostream>
#include <queue>
int main() {
// 创建一个大顶堆的 priority_queue
std::priority_queue<int> maxHeap;
// 插入元素
maxHeap.push(10);
maxHeap.push(30);
maxHeap.push(20);
// 访问队头元素
std::cout << "Top element: " << maxHeap.top() << std::endl;
// 弹出队头元素
maxHeap.pop();
// 访问新的队头元素
std::cout << "Top element after pop: " << maxHeap.top() << std::endl;
return 0;
}
在这个示例中,std::priority_queue 被创建为大顶堆,默认情况下,元素的比较使用 < 操作符。你可以通过提供自定义的比较函数来创建小顶堆。
例如,如果要创建一个小顶堆,可以这样做:
#include <iostream>
#include <queue>
// 自定义比较函数,使得小的元素优先级高
struct Compare {
bool operator()(int a, int b) {
return a > b;
}
};
int main() {
// 创建一个小顶堆的 priority_queue
std::priority_queue<int, std::vector<int>, Compare> minHeap;
// 插入元素
minHeap.push(10);
minHeap.push(30);
minHeap.push(20);
// 访问队头元素
std::cout << "Top element: " << minHeap.top() << std::endl;
// 弹出队头元素
minHeap.pop();
// 访问新的队头元素
std::cout << "Top element after pop: " << minHeap.top() << std::endl;
return 0;
}
这个例子中,Compare 结构体定义了自定义的比较函数,确保小的元素优先级更高。
组合实例:
#include <iostream>
#include <queue>
// 自定义比较函数,使得小的元素优先级高
struct Compare {
bool operator()(int a, int b) {
return a > b;
}
};
int main() {
// 创建一个大顶堆的 priority_queue
std::priority_queue<int> maxHeap;
// 插入元素
maxHeap.push(10);
maxHeap.push(30);
maxHeap.push(20);
// 访问队头元素
std::cout << "Top Max element: " << maxHeap.top() << std::endl;
// 弹出队头元素
maxHeap.pop();
// 访问新的队头元素
std::cout << "Top Max element after pop: " << maxHeap.top() << std::endl;
// 创建一个小顶堆的 priority_queue
std::priority_queue<int, std::vector<int>, Compare> minHeap;
// 插入元素
minHeap.push(10);
minHeap.push(30);
minHeap.push(20);
// 访问队头元素
std::cout << "Top Min element: " << minHeap.top() << std::endl;
// 弹出队头元素
minHeap.pop();
// 访问新的队头元素
std::cout << "Top Min element after pop: " << minHeap.top() << std::endl;
return 0;
}