优先级队列首先是一个队列，但是它强调的是“优先”，所以优先级队列又分为最大优先队列和最小优先队列。
最大优先级队列：每次从队列中取出优先级最大的数据，删除数据也是删除优先级最大的数据。
最小优先级队列：每次从队列中取出优先级最小的数据，删除也是删除优先级最小的数据。
所以我们用一个类去实现优先级队列时就需要用到小顶堆和大顶堆的概念。我们并不关心除了最高优先级和最低优先级的数据在队列中是怎体存储的。
为了提高代码的复用性，最大优先级对列和最小优先级队列都使用同一个堆调整函数，我们可以定义一个比较模板（Compare）也可以说是一个类，不过它是通过重载（）实现的。
计算
安全
数据库
网络和加速
企业服务
template<class T>
struct Less
{
bool operator()(const T& left, const T& right)
return left < right;
};
template<class T>
struct Greater
{
bool operator()(const T& left, const T& right)
return left>right;
};通过Less和Grearter模板，我们就可以在优先级队列初始化的时候通过传Less或者Greater的对象，来调整是最大优先级队列还是最小优先级队列。
#pragma once
#include<iostream>
#include<vector>
using namespace std;
template<class T>
struct Less
{
bool operator()(const T& left, const T& right)
{
return (left < right);
}
};
template<class T>
struct Greater
{
bool operator()(const T& left, const T& right)
{
return (left>right);
}
};
template<class T,template<class> class Compare=Less>
class PQueue
{
public:
PQueue()
:_size(0)
{}
PQueue(const T* a, size_t size)
:_size(size)
{
_data.resize(size);
for (size_t i = 0; i < size; i++)
{
_data[i] = a[i];
}
for (int i = (size - 2) / 2; i >= 0; --i)
{
_AdjustDown(i);
}
}
size_t Size()
{
return _size;
}
void Push(const T& d)
{
_data.push_back(d);
++_size;
_AdjustUp();
}
void Pop()
{
swap(_data[0], _data[_size - 1]);
_data.pop_back();
_AdjustDown(0);
}
T& Front()
{
return _data[0];
}
bool Empty()
{
return _size;
}
protected:
void _AdjustDown(int parent)
{
Compare<T> con;
int child = parent * 2 + 1;
while (child < _size)
{
if (child + 1 < _size&&con(_data[child + 1], _data[child]))
++child;
if (con(_data[child], _data[parent]))
{
swap(_data[child], _data[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void _AdjustUp(int child)
{
Compare<T> con;
parent = (child - 1) / 2;
while (child > 0)
{
if (con(_data[child], _data[parent]))
{
swap(_data[child], _data[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
protected:
vector<T> _data;
size_t _size;
};亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
