priority_queue (优先级队列的使用和模拟实现)

使用

priority_queue

优先级队列与 stack 和 queue 一样，也是一个容器适配器，其底层通过 vector 来实现的。与 stack 和 queue 不同的是，它的第一个元素总是它所包含的元素中最大或最小的一个。

也就是说，优先级队列就是数据结构中所说的堆。其通过堆的向上调整算法、向下调整算法等，将其变为一个堆，保证其第一个元素一定为其所包含元素中最大或最小的一个。

priority_queue<int> q;
q.push(9);
q.push(2);
q.push(7);
q.push(1);
q.push(5);while (!q.empty())
{cout << q.top() << " ";q.pop();
}
cout << endl;

模拟实现

基础实现

模拟实现优先级队列就是模拟实现堆，要实现的核心接口为 push() 和 pop() 。(堆的实现详解)

其为适配器，底层利用 vector 来实现。

默认实现为大堆。

#include<vector>//大堆
namespace Friend
{template<class T, class Container = vector<T>>class priority_queue{public:bool empty() const{return con.empty();}size_t size() const{return con.size();}const T& top() const{// 返回数组的第一个元素return con.front();}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;}}}void AdjustDown(int parent){int 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[parent], con[child]);parent = child;child = 2 * parent + 1;}else{break;}}}void push(const T& x){// 在尾部插入一个新数据con.push_back(x);// 将其重新调整为堆AdjustUp(con.size() - 1);}// 删除堆顶的数据void pop(){// 交换堆顶和尾部的数据std::swap(con[0], con[con.size() - 1]);// 删除尾部数据con.pop_back();// 将其重新调整为堆AdjustDown(0);}private:Container con;};
}

仿函数

按照之前的方法，如果要把大堆变为小堆，就要把 AdjustUp( )、AdjustDown( ) 中所有的 ‘<' 变为 ’>'  ，十分麻烦。因此，C++ 中使用仿函数来解决这个问题。

仿函数实际上为类，并非真正的函数。

其通过重载了 ( ) ，来控制大堆、小堆的变化。

template<class T>
class Less
{
public:// x -- i-1  *******  y -- ibool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:// x -- i-1  *******  y -- ibool operator()(const T& x, const T& y){return x > y;}
};

由于其调用时像函数调用，因此得名仿函数。

Less<int> less;less(10, 20);
less.operator()(1, 9);Greater<int> greater;greater(10, 20);
greater.operator()(1, 9);

改进

因此，我们对代码进行改进。

namespace Friend
{template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{public:bool empty() const{return con.empty();}size_t size() const{return con.size();}const T& top() const{// 返回数组的第一个元素return con.front();}void AdjustUp(int child){int parent = (child - 1) / 2;while (parent >= 0){// if (con[parent] < con[child])if (com(con[parent], con[child])){std::swap(con[parent], con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(int parent){int child = 2 * parent + 1;while (child < con.size()){// if (child + 1 < con.size() && con[child] < con[child + 1])if (child + 1 < con.size() &&  com(con[child], con[child + 1])){child++;}// if (con[parent] < con[child])if (com(con[parent], con[child])){std::swap(con[parent], con[child]);parent = child;child = 2 * parent + 1;}else{break;}}}void push(const T& x){// 在尾部插入一个新数据con.push_back(x);// 将其重新调整为堆AdjustUp(con.size() - 1);}// 删除堆顶的数据void pop(){// 交换堆顶和尾部的数据std::swap(con[0], con[con.size() - 1]);// 删除尾部数据con.pop_back();// 将其重新调整为堆AdjustDown(0);}private:Container con;Compare com;};
}

大堆时：

Friend::priority_queue<int> q;

如果要变为小堆，则：

Friend::priority_queue<int, vector<int>, Greater<int>> q;

只需通过仿函数的变换就能达到目的。