优先级队列priority_queue以及仿函数的使用

优先级队列priority_queue

优先级队列priority_queue是一种容器适配器，根据严格的弱排序标准，它默认第一个元素总是它所包含的元素中最大的

优先级队列默认使用vector作为底层存储数据的容器，在vector上又使用了堆排序的算法对数据进行排序，所以priority_queue就是堆。注意：priority_queue默认情况下是大堆

priority_queue是存在<queue>文件中，要使用只需要包queue文件就可以

所以以后有需要用到堆的位置，我们就不用手动实现一个堆了，可以直接使用priority_queue就可以

下面是优先级队列的定义：

template <class T, class Container = vector<T>,class Compare = less<typename Container::value_type> > class priority_queue;

第一个模板参数是放在适配器容器内元素的类型
第二个模板参数是适配器，默认为vector
第三个模板参数是一个仿函数，默认是less，为了保证默认是大堆

函数	接口说明
priority_queue()	构造一个空的优先级队列
priority_queue (InputIterator first, InputIterator last)	用[first,last)迭代器区间构造一个优先级队列
empty()	判空
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

下面我们使用优先级队列尝试一下：

void test1()
{priority_queue<int> pq;pq.push(1);pq.push(6);pq.push(9);pq.push(3);pq.push(0);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}//输出 9 6 3 2 1 0 cout << endl;
}

如果我们先实现一个小堆，只需要改变第三个模板参数就可以，让第三个模板参数为greater<T>，因为我们指定了第三个模板参数，所以我们还需手动显式传第二个模板参数

下面我们实现一个小堆的priority_queue:

void test1()
{priority_queue<int,vector<int>,greater<int>> pq;pq.push(1);pq.push(6);pq.push(9);pq.push(3);pq.push(0);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}//输出 0 1 2 3 6 9cout << endl;
}

---

priority_queue的模拟实现

因为优先级队列的底层是堆排序，所以我们先完成堆排序中的向下调整，和向上调整

void AdjustDown(int parent)
{Compare com;size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child]<_con[child + 1]){child++;}if (_con[parent]< _con[child]){std::swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void AdjustUp(int child)
{Compare com;int parent = (child - 1) / 2;while (parent >= 0){if (_con[parent]< _con[child]){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}

push函数，就是，先向底层适配器中插入一个元素，然后再调用向上调整法

void push(const T& t)
{_con.push_back(t);AdjustUp(_con.size() - 1);}

pop函数，先把适配器中首元素和尾元素交换，然后删除尾元素，再调用向下调整法

void pop()
{std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);
}

还有几个实现起来很简单的函数：

bool empty()
{return _con.empty();
}const T& top()
{return _con[0];
}size_t size()
{return _con.size();
}

当前完整代码：

namespace my_priority_queue
{template<class T, class Container = std::vector<T>>class priority_queue{private:void AdjustDown(int parent){size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child]<_con[child + 1]){child++;}if (_con[parent]< _con[child]){std::swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}void AdjustUp(int child){int parent = (child - 1) / 2;while (parent >= 0){if (_con[parent]< _con[child]){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);first++;}for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void push(const T& t){_con.push_back(t);AdjustUp(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T& top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
}

此时，我们已经实现了一个大堆的优先级队列
那么怎么实现小堆的优先级队列呢？当前我们只能去修改向下调整和向上调整中比较大小的部分：

这其实挺麻烦的，有没有什么方法可以使大堆和小堆的优先级队列可以秒切换呢？
答案就是：可以使用仿函数

---

仿函数

仿函数也叫函数对象，这个类的对象可以像函数一样使用，使一个类的使用看上去像一个函数
其实现就是类中实现一个operator()，有了对括号的重载，就可以让这个类的对象像函数一样使用

下面就是一个仿函数：

class IntLess
{
public:bool operator()(int x,int y){return x < y;}};

怎么使用仿函数呢？毕竟仿函数是一个类，所以我们使用时需要先实例化一个对象出来
然后将这个对象像使用函数一样使用
在对象后面加上()，该传参就传参

void test2()
{IntLess LessFunc;cout<<LessFunc(1,2)<<endl;//仿函数的使用
}

LessFunc(1,2)会被处理成：LessFunc.operator()(1,2)

接下来，用仿函数完善模拟实现的优先级队列

template<class T>
struct Less//首字母大写，为了与库中的less区分
{bool operator()(const T& t1, const T& t2){return t1 < t2;}
};template<class T>
struct Greater
{bool operator()(const T& t1, const T& t2){return t1 > t2;}
};

首先，在模板声明中加一个参数：

template<class T,class Container = std::vector<T>,class Compare = Less<T>>

然后，然后将向上调整和向下调整中大小判断部分改为仿函数

void AdjustDown(int parent)
{Compare com;//仿函数使用前，实例化出一个对象size_t child = 2 * parent + 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[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void AdjustUp(int child)
{Compare com;//仿函数使用前，实例化出一个对象int parent = (child - 1) / 2;while (parent >= 0){if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}