priority_queue的使用
priority_queue的介绍
优先级队列（priority queue）
是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有（1）查找（2）插入一个新元素（3）删除一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。
对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。
这里还是用简单的语言来描述下
我们可以将优先级队列想象成一个堆（默认是大堆）
priority_queue的定义
它的定义包括下面的三个参数
priority_queue<int, vector<int>,less<int> > q1;
我们通过观察可以发现 这里的三个参数代表的分别是
存储的数据类型 存储的容器类型 比较的方式
其中存储容器的类型和比较方式都是可以省略的
（默认是 vector 和 less）
所以说可以衍生出下面的两种定义方式
priority_queue<int, vector<int>> q2;
priority_queue<int> q3;
实际上来说它们定义的优先级队列是相同的
tips ： 这里的优先级队列设计的有点奇怪
less对应的是大堆 而greater则对应的是小堆
priority_queue的使用
接口函数如下
使用代码如下
void test_priority_queue() { priority_queue<int, vector<int>, less<int> > q1; q1.push(1); q1.push(4); q1.push(9); q1.push(3); q1.push(7); while (!q1.empty()) { cout << q1.top() << endl; q1.pop(); } }
这段代码的意思呢 就是我们随机插入几个数字
然后一个个打印出来 看看打印出来的顺序是什么？
显示结果如下
我们可以发现 它们在优先级队列中实际上就是按照从大到小的顺序
那么如果我们想到将它变成从小到大呢？
是不是改变下比较的仿函数就可以了
我们可以发现 变成greater之后就会是从小到大排序了
priority_queue的题目
就像这个问题 我们就可以使用我们的优先级队列来解决（堆）
因为大堆的顶部一定是最大的数字 所以说我们只需要删除掉前面top（k -1）个元素 之后我们就能得到我们第k大的数了
代码表示如下
class Solution { public: int findKthLargest(vector<int>& nums, int k) { // 我们使用优先级队列来做 // 因为要求第k大的数字 所以说我们只要建立一个大堆 // 然后pop掉前面k-1个数字 最后的一个数字就是我们要求的了 priority_queue<int> q1; for (auto x : nums) { q1.push(x); } // 之后删掉前面k-1个数 就是第k大个数在最前面了 while(k-1) { q1.pop(); k--; } return q1.top(); } };
运行结果如下
priority_queue的模拟实现
我们前面已经说过了 priority_queue的底层其实就是堆
所以说要我们实现一个优先级队列和实现一个堆 其实是差不多的
注意！ 博主下面的实现全部以大堆为例
堆的向上调整
主要用于我们建堆的时候
我们在堆的末尾插入一个元素
由于我们的堆是大堆的缘故 所以说父节点 一定是大于子节点的
这个时候我们就需要判断 我们的父节点是否确实大于我们的子节点
如果大于 我们就交换它们的位置 之后重复这个过程
void adjust_up(vector<int>& v ,int child) { // 首先找出孩子的父节点 int father = (child - 1) / 2; // 当子节点不为根节点时就一直判断 while ( child > 0 ) { if (v[child] > v[father]) { swap(v[child], v[father]); child = father; father = (child - 1) / 2; } else { // 符合规则 直接跳出循环 break; } } }
堆的向下调整
向下调整通常用于删除数据的时候
同样的 我们如果直接删除大堆顶部的数据有点不太好操作
这个时候我们就可以将大堆顶部和底部的数据交换 之后删除底部的数据
这个时候我们只需要让顶部的元素 向下进行调整就好了
代码表示如下
void adjust_down(vector<int>& v, int father) { int child = 2 * father + 1;//左孩子 // 开始循环 直到父亲没有孩子 或者符合小堆结构位置 while (child < v.size()) { // 首先判断右孩子是否存在并且右孩子是否大于左孩子 // 因为要是比较大的那个做父亲 if (child + 1 < v.size() && v[child+1] > v[child]) { child++; } // 之后就判断 孩子是否大于父亲 如果大于就交换并且继续比较 如果不大于就结束 if (v[child] > v[father]) { swap(v[child], v[father]); father = child; child = 2 * father + 1; } else { break; } } }
仿函数的实现
两个很简单的仿函数 operator（）重载
这两个函数比较特殊 我们先看代码
struct Less { template<class T> bool operator() (T& x, T& y) { return x < y; } };
struct Greater { template<class T> bool operator() (T& x, T& y) { return x > y; } };
我们可以看到 它们实际上就是重载了一个括号运算符来判断大小而已
priority_queue模拟实现 namespace shy //防止命名冲突 { //比较方式（使内部结构为大堆） template<class T> struct less { bool operator()(const T& x, const T& y) { return x < y; } }; //比较方式（使内部结构为小堆） template<class T> struct greater { bool operator()(const T& x, const T& y) { return x > y; } }; //优先级队列的模拟实现 template<class T, class Container = vector<T>, class Compare = less<T>> class priority_queue { public: //堆的向上调整 void AdjustUp(int child) { int parent = (child - 1) / 2; //通过child计算parent的下标 while (child > 0)//调整到根结点的位置截止 { if (_comp(_con[parent], _con[child]))//通过所给比较方式确定是否需要交换结点位置 { //将父结点与孩子结点交换 swap(_con[child], _con[parent]); //继续向上进行调整 child = parent; parent = (child - 1) / 2; } else//已成堆 { break; } } } //插入元素到队尾（并排序） void push(const T& x) { _con.push_back(x); AdjustUp(_con.size() - 1); //将最后一个元素进行一次向上调整 } //堆的向下调整 void AdjustDown(int n, int parent) { int child = 2 * parent + 1; while (child < n) { if (child + 1 < n&&_comp(_con[child], _con[child + 1])) { child++; } if (_comp(_con[parent], _con[child]))//通过所给比较方式确定是否需要交换结点位置 { //将父结点与孩子结点交换 swap(_con[child], _con[parent]); //继续向下进行调整 parent = child; child = 2 * parent + 1; } else//已成堆 { break; } } } //弹出队头元素（堆顶元素） void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(_con.size(), 0); //将第0个元素进行一次向下调整 } //访问队头元素（堆顶元素） T& top() { return _con[0]; } const T& top() const { return _con[0]; } //获取队列中有效元素个数 size_t size() const { return _con.size(); } //判断队列是否为空 bool empty() const { return _con.empty(); } private: Container _con; //底层容器 Compare _comp; //比较方式 }; }
总结
优先级队列的模拟实现主要是运用到了堆的知识 对于目前的同学们来说还是比较简单的
