目录
杂谈
vector和list的区别
1. 优先级队列的定义
2. 优先级队列的模拟实现
3. 仿函数
链接：
priority_queue - C++ Reference (cplusplus.com)
https://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue
杂谈
vector和list的区别
在这种情况下诞生了一个缝合怪：deque
但是依旧有缺陷
1. 优先级队列的定义
队列是一种先进先出的数据类型。元素的入队都只能从队尾进入，出队时从队列头部出去
*
优先级队列不能先进先出，更像是数据类型中的“堆”，也就是数组
优先级队列每次出队的元素是队列中优先级最高的那个元素，默认大的值优先级高，如果想要小的值优先级高可以使用仿函数，而不是队首的元素，也就是每次出队，都是将当前队列中最大的那个元素出队
2. 优先级队列的模拟实现
假设父节点在数组中的下标为i，那么：
1.左孩子在数组中的下标为：2*i+1
2.右孩子在数组中的下标为：2*i+2
假设孩子在数组中的下标为i，那么：
父在数组中的下标为：（i - 1）/ 2
在这里不区分左孩子和右孩子，因为除以会向下取整
#pragma once
//优先级队列：默认大的值优先级高，如果想要小的值优先级高可以使用仿函数
//底层是堆
namespace bit
{template<class T, class Container = vector<T>>class priority_queue{public://堆的向上调整void AdjustUp(size_t child){//孩子/2找到父节点int parent = (child - 1) / 2;//孩子大于0就进入/继续while (child > 0){//如果孩子小于父亲if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向下调整void AdjustDown(size_t parent){// 先假设左孩子小int child = parent * 2 + 1;// child >= n说明孩子不存在，调整到叶子了while (child < 0){//找到大的子结点 if (child + 1 < _con.size() && _con[child] < _con[child + 1]){child++;}//if (_con[child] > _con[parent]) 大堆//孩子小于父亲if (_con[child] < _con[parent])//小堆{swap(_con[child], _con[parent]);parent = child;//继续算左孩子child = parent * 2 + 1；}else{break;}}}void push(const T & x){//插入数据之前已经是一个堆了，那么数据就要_con.push_back(x);//从堆底向上调整AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}3. 仿函数
仿函数的本质是一个类，使用到了仿函数来重载 operator()，以达到改变大/小堆的功能，他的对象可以像函数一样使用
// 仿函数：本质是一个类，这个类重载operator(),他的对象可以像函数一样使用
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;}
};#pragma once
//优先级队列：默认大的值优先级高，如果想要小的值优先级高可以使用仿函数
//底层是堆
namespace bit
{template<class T, class Container = vector<T>>class priority_queue{public://堆的向上调整void AdjustUp(size_t child){Compare com;//孩子/2找到父节点int parent = (child - 1) / 2;//孩子大于0就进入/继续while (child > 0){//如果孩子小于父亲//if (_con[parent] < _con[child])//将大的值移向堆顶，建大堆if (com(_con[child], _con[parent])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向下调整void AdjustDown(size_t parent){Compare com;// 先假设左孩子小int child = parent * 2 + 1;// child >= n说明孩子不存在，调整到叶子了while (child < 0){//找到大的子结点 //if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}//if (_con[child] > _con[parent]) 大堆//孩子小于父亲//if (_con[child] < _con[parent])//小堆if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;//继续算左孩子child = parent * 2 + 1；}else{break;}}}void push(const T & x){//插入数据之前已经是一个堆了，那么数据就要_con.push_back(x);//从堆底向上调整AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}感谢观看~
