admin管理员组文章数量:1623793
参考资料:https://wwwblogs/nirvana-phoenix/archive/2012/05/29/2524344.html
1.基本类型实现
#include <iostream>
#include <vector>
#include <queue>
void log(const char* str)
{
std::cout << str;
}
void log(const int v)
{
std::cout << "" << +v << " ";
}
int main()
{
//默认构造最大堆
std::priority_queue<int> maxHeap;
//构造最小堆
std::priority_queue<int,std::vector<int>,std::greater<int>> minHeap;
for (auto i : {1,3,5,9,8,6,2,7,4,0})
{
maxHeap.push(i);
minHeap.push(i);
}
log("最大堆:");
while (!maxHeap.empty())
{
log(maxHeap.top());
maxHeap.pop();
}
log("\n");
log("最小堆:");
while (!minHeap.empty())
{
log(minHeap.top());
minHeap.pop();
}
getchar();
return 0;
}
打印信息:
上面是使用基本类型实现的最大/最小堆,而比较常用的是自定义类型的最大最小堆,其实现也不复杂,只需重载大于或小于运算符即可。
2.自定义类型实现
#include <iostream>
#include <vector>
#include <queue>
void log(const char* str)
{
std::cout << str;
}
void log(const int v)
{
std::cout << "" << +v << " ";
}
struct Stuent
{
int score = 0;
bool operator >(const Stuent& right) const
{
return this->score > right.score;
}
};
int main()
{
//构造最小堆
std::priority_queue<Stuent,std::vector<Stuent>,std::greater<Stuent>> minHeap;
Stuent stu;
for (auto i : {1,3,5,9,8,6,2,7,4,0})
{
stu.score = i * 10;
minHeap.push(stu);
}
log("最小堆:");
while (!minHeap.empty())
{
log(minHeap.top().score);
minHeap.pop();
}
getchar();
return 0;
}
输出:
注意:实现运算符重载时记得在函数后加const关键字修饰,因为在模板中
是const变量调用的运算符,而const变量不能调用非const函数。
本文标签: 最小priorityqueue
版权声明:本文标题:C++使用priority_queue 实现最大最小堆 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1728895714a1178381.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论