yuyi
知不可乎骤得,托遗响于悲风
在C++标准库中,std::priority_queue
默认是一个最大堆,它使用std::less
作为其比较函数,这意味着元素总是以非递增的顺序排序。如果你想实现一个最小堆,你可以通过指定一个不同的比较函数来实现,即使用std::greater
。
以下是如何使用std::priority_queue
来实现最大堆和最小堆的示例代码:
最大堆已经是std::priority_queue
的默认行为。如果你要创建一个存储Node
结构的最大堆,你可以像你已经做的那样直接使用它:
#include <iostream>
#include <queue>
#include <vector>
struct Node {
int value;
int idx;
Node (int v, int i): value(v), idx(i) {}
};
// 使得 priority_queue 默认的比较行为成为最大堆
bool operator < (const Node &n1, const Node &n2) {
return n1.value < n2.value;
}
int main() {
// std::priority_queue<Node, std::vector<Node>, std::less<Node>> maxHeap;
std::priority_queue<Node> maxHeap;
maxHeap.push(Node(10, 1));
maxHeap.push(Node(20, 2));
maxHeap.push(Node(15, 3));
while (!maxHeap.empty()) {
Node top = maxHeap.top();
std::cout << "Max heap top: " << top.value << std::endl;
maxHeap.pop();
}
return 0;
}
要创建一个最小堆,你需要使用std::greater
作为比较函数,这将使得元素以非递减的顺序被排列:
#include <iostream>
#include <queue>
#include <vector>
#include <functional> // For std::greater
struct Node {
int value;
int idx;
Node (int v, int i): value(v), idx(i) {}
};
// 重载比较运算符用于最小堆
bool operator > (const Node &n1, const Node &n2) {
return n1.value > n2.value;
}
int main() {
std::priority_queue<Node, std::vector<Node>, std::greater<Node>> minHeap;
minHeap.push(Node(10, 1));
minHeap.push(Node(20, 2));
minHeap.push(Node(15, 3));
while (!minHeap.empty()) {
Node top = minHeap.top();
std::cout << "Min heap top: " << top.value << std::endl;
minHeap.pop();
}
return 0;
}
在上述示例中,std::greater
是用来告诉priority_queue
如何比较Node
类型的对象。注意,为了使用std::greater
,你需要重载>
运算符而不是<
运算符。在这个例子中,>
运算符被重载以比较两个Node
对象的value
成员。
通过这种方式,你可以根据需要灵活地实现最大堆和最小堆。