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;
只需通过仿函数的变换就能达到目的。