C++：priority_queue类
目录
前言
数据结构
向上调整
less
greater
向下调整
push
pop
top
size
empty
完整代码
前言
priority_queue类的本质是堆，下面是数据结构中的实现
C数据结构：堆（实现、排序）-CSDN博客
它的实现也是和前面的栈和堆类似，一样用其他容器的成员函数来实现
数据结构
template<class T, class Container = std::vector<T>, class Compare = Less<T>>
class priority_queue
{
public:private:Container _con;
};这里的模板需要有三个，T是堆里存储的数据类型，Container是实现堆的容器，Compare是决定堆是大堆还是小堆
容器默认用vector即可，因为它是需要下标访问的
Less是大堆，稍后我们可以自己使用仿函数实现这个Less
向上调整
要实现堆我们需要先实现向上调整和向下调整的函数
void AdjustUp(int child)
{Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}和数据结构中的实现一致，唯一有区别的地方就是比较的地方
这里我们使用了类里面的Compare，它定义了一个com，这里就用了这个com里面的仿函数来比较，Compare默认是Less，那么这个Less是什么呢？
less
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};这里就是使用仿函数，里面返回小于的比较即可
greater
template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};也是仿函数，里面返回大于的比较即可
如果使用原来的直接比较的方法我们只能通过改代码来更改大小堆
但是如果我们使用仿函数可以通过调整参数来决定是大堆还是小堆
向下调整
void AdjustDown(int parent)
{Compare com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}用了数据结构中的思路和上面向上调整的比较思路实现
push
void push(const T& x)
{_con.push_back(x);AdjustUp(_con.size() - 1);
}push函数是向堆中插入数据
数据放到堆的最后，这时候将该元素向上调整成堆即可
pop
void pop()
{std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);
}pop函数是删除堆顶数据
只需要交换堆顶数据到最后，删除最后一个数据，并向下调整第一个数据即可
top
const T& top() const
{return _con[0];
}top函数是返回堆顶数据
size
size_t size() const
{return _con.size();
}size函数是返回堆的数据个数
empty
bool empty() const
{return _con.empty();
}empty函数是返回判断堆是否为空
完整代码
#pragma once#include<iostream>
#include<vector>template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};namespace lyw
{template<class T, class Container = std::vector<T>, class Compare = Less<T>>class priority_queue{public:void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void AdjustDown(int parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top() const{return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}完