建设网站的和服务器,外国人搞笑做视频网站,wordpress主题 网站大全,网站开发工作协议书范本文章目录一、priority_queue 的介绍和使用1、priority_queue 的介绍2、priority_queue 的使用3、priority_queue 相关 OJ 题二、仿函数1、什么是仿函数2、仿函数的作用三、priority_queue 的模拟实现一、priority_queue 的介绍和使用
1、priority_queue 的介绍
priority_queu…
文章目录一、priority_queue 的介绍和使用1、priority_queue 的介绍2、priority_queue 的使用3、priority_queue 相关 OJ 题二、仿函数1、什么是仿函数2、仿函数的作用三、priority_queue 的模拟实现一、priority_queue 的介绍和使用
1、priority_queue 的介绍
priority_queue (优先级队列) 是一种容器适配器它与 queue 共用一个头文件其底层结构是一个堆并且默认情况下是一个大根堆所以它的第一个元素总是它所包含的元素中最大的并且为了不破坏堆结构它也不支持迭代器
同时由于堆需要进行下标计算所以 priority_queue 使用 vector 作为它的默认适配容器 (支持随机访问)
但是priority_queue 比 queue 和 stack 多了一个模板参数 – 仿函数关于仿函数的具体细节我们将在后文介绍。
class Compare lesstypename Container::value_type2、priority_queue 的使用
优先级队列默认使用 vector 作为其底层存储数据的容器在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构因此 priority_queue 就是堆所有需要用到堆的位置都可以考虑使用 priority_queue。(注意默认情况下priority_queue是大堆)
priority_queue 的使用文档
-函数声明接口说明-priority_queue()构造一个空的优先级队列priority_queue(first, last)迭代器区间构造优先级队列empty( )检测优先级队列是否为空top( )返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素size()返回优先级队列中的元素个数
注意事项
priority_queue 默认使用的仿函数是 less所以默认建成的堆是大堆如果我们想要建小堆则需要指定仿函数为 greater该仿函数包含在头文件 functional 中并且由于仿函数是第三个缺省模板参数所以如果要传递它必须先传递第二个模板参数即适配容器。 void test_priority_queue() {priority_queueint pq; //默认建大堆仿函数为lesspq.push(5);pq.push(2);pq.push(4);pq.push(1);pq.push(3);while (!pq.empty()) {cout pq.top() ;pq.pop();}cout endl;priority_queueint, vectorint, greaterint pq1; //建小堆仿函数为greater需要显式指定pq1.push(5);pq1.push(2);pq1.push(4);pq1.push(1);pq1.push(3);while (!pq1.empty()) {cout pq1.top() ;pq1.pop();}cout endl;
}3、priority_queue 相关 OJ 题
215. 数组中的第K个最大元素 - 力扣LeetCode
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 输入: [3,2,1,5,6,4], k 2
输出: 5输入: [3,2,3,1,2,4,5,5,6], k 4
输出: 4思路1
思路1非常简单直接对 nums 数组使用 sort 进行排序然后返回 nums[nums.size() - k] 即可但是排序的时间复杂度为 O(N*logN)太高。
思路2
思路2就是建N个数的大堆然后 pop k-1 次此时堆顶元素就是第 K 大的数向下调整建堆时间复杂度为 O(N)pop 再向下调整的时间复杂度为 K*logN所以总的时间复杂度为 O(N K*logN)此方法可行但是当 N 很大K 很小时空间复杂度过高。
思路3
建 K 个数的小堆剩余 N- K 个数依次与堆顶元素进行比较如果大于堆顶元素就将堆顶元素 pop 掉然后将其 push 进堆中最后堆顶元素就是第 K 大的数建堆的时间复杂度为 O(K)push 再向上调整的时间复杂度为 O((N-k)*logK)所以总的时间复杂度为 O(K (N-k) * logK)此方法在 N 很大K 很小的情况下依然适用因为堆的大小固定为 K。
代码实现
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint, vectorint, greaterint pq; //建小堆for(int i 0; i k; i) { //建K个数的小堆pq.push(nums[i]);}for(int i k; i nums.size(); i) { //剩余n-k个数与堆顶比较大于就删除堆顶元素入堆if(nums[i] pq.top()) {pq.pop();pq.push(nums[i]);}}return pq.top(); //堆顶元素为第K大的数}
};二、仿函数
1、什么是仿函数
仿函数也叫函数对象仿函数是一个类但是该类必须重载函数调用运算符 ()即 operator()(参数)由于这样的类的对象可以像函数一样去使用所以我们将其称为仿函数/函数对象如下
namespace thj {templateclass Tstruct less {bool operator()(const T x, const T y) const {return x y;}};templateclass Tstruct greater {bool operator()(const T x, const T y) {return x y;}};
}void functor_test() {thj::lessint lessFunc;cout lessFunc(1, 2) endl; //lessFunc.operator(1,2)thj::greaterint greaterFunc;cout greaterFunc(1, 2) endl; //greaterFunc.operator(1,2)
}可以看到因为 less 类和 greater 类重载了 () 操作符所以类对象可以像函数一样去使用因此它们被称为仿函数。
2、仿函数的作用
我们以最简单的冒泡排序为例来说明仿函数的作用我们知道排序分为排升序和排降序那么在没有仿函数的时候即C语言阶段我们是如何来解决这个问题的呢 – 答案是函数指针
将排序函数的最后一个参数定义为函数指针然后通过用户给排序函数传递不同的比较函数来决定升序还是降序
templateclass T
bool cmpUp(const T e1, const T e2) { //排升序return e1 e2;
}templateclass T
bool cmpDown(const T e1, const T e2) { //排降序return e1 e2;
}// 冒泡排序
templateclass T
void BubbleSort(T* a, int n, bool (*cmp)(const T, const T))
{T i 0;T j 0;for (i 0; i n - 1; i){int exchange 0;for (j 0; j n - i - 1; j){if (cmp(a[j], a[j 1])) //函数调用{std::swap(a[j], a[j 1]);exchange 1;}}if (exchange 0) break;}
}void bubbleSort_test() {int a[] { 1, 3, 2, 2, 4, 8, 5, 1, 9 };BubbleSort(a, sizeof(a) / sizeof(int), cmpUp);for (auto e : a) {cout e ;}cout endl;int b[] { 1, 3, 2, 2, 4, 8, 5, 1, 9 };BubbleSort(b, sizeof(b) / sizeof(int), cmpDown);for (auto e : b) {cout e ;}cout endl;
}在 C 中我们不再使用函数指针解决升序降序的问题转而使用更加方便的仿函数。(注关于仿函数的更多细节以及仿函数和函数指针各自的优缺我们将在以后慢慢学习现在仅仅是浅浅入门一下仿函数)
// 冒泡排序
templateclass T, class Compare
void BubbleSort(T* a, int n, Compare cmp) //使用仿函数
{T i 0;T j 0;for (i 0; i n - 1; i){int exchange 0;for (j 0; j n - i - 1; j){if (cmp(a[j], a[j 1])) //函数调用 cmp.operator()(a[j], a[j1]){std::swap(a[j], a[j 1]);exchange 1;}}if (exchange 0) break;}
}//复用前面的 less 和 greater 类
void bubbleSort_test1() {int a[] { 1, 3, 2, 2, 4, 8, 5, 1, 9 };BubbleSort(a, sizeof(a) / sizeof(int), thj::lessint()); //排降序匿名对象for (auto e : a) {cout e ;}cout endl;int b[] { 1, 3, 2, 2, 4, 8, 5, 1, 9 };BubbleSort(b, sizeof(b) / sizeof(int), thj::greaterint()); //排升序for (auto e : b) {cout e ;}cout endl;
}三、priority_queue 的模拟实现
其实 priority_queue 的模拟实现我们已经做过了 – priority_queue 的底层是堆而关于堆的C语言实现包括堆的应用 (堆排序与TopK问题) 我们在数据结构初阶都已经做过了这里只是用类和对象再加上容器适配器和仿函数将其封装起来而已所以下面我就直接给出实现代码而不进行细节分析了如果有疑问的同学可以回头看看我之前的博客。
【数据结构】二叉树 – 堆
【数据结构】堆的应用 – 堆排序和TopK问题
priority_queue.h
#pragma oncenamespace thj {//仿函数templateclass Tstruct less {bool operator()(const T x, const T y) const {return x y;}};templateclass Tstruct greater {bool operator()(const T x, const T y) {return x y;}};//priority_queuetemplateclass T, class Container vectorT, class Compare lessT //默认建大堆传lessclass priority_queue {public:priority_queue() {} //默认构造templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last) //迭代器区间构造: _con(first, last){//向下调整建堆 O(N) 从最后一个非叶子节点开始for (int i (_con.size() - 1 - 1) / 2; i 0; i--) {adjustDown(i);}}bool empty() const { //判空return _con.empty();}size_t size() const { //元素个数return _con.size();}const T top() const { //取堆顶数据return _con[0];}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); //从堆顶向下调整}void adjustDown(size_t parent) { //堆的向下调整Compare cmp; //仿函数size_t child parent * 2 1;while (child _con.size()) { //特别注意边界问题if (child 1 _con.size() cmp(_con[child], _con[child 1])) { //仿函数child child 1; //如果是less则建大堆找大孩子结果为真右孩子大}if (cmp(_con[parent], _con[child])) {std::swap(_con[parent], _con[child]);//迭代parent child;child parent * 2 1;}else break; //满足堆结构跳出循环}}void adjustUp(size_t child) { //堆的向上调整Compare cmp;size_t parent (child - 1) / 2;while (child 0) { //一直向上调整到根节点if (cmp(_con[parent], _con[child])) {std::swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else break;}}private:Container _con;};
}test.cpp
#include priority_queue.h
#include iostream
#include functional
#include vector
#include algorithm
using namespace std;void my_priority_queue_test() {thj::priority_queueint pq; //默认建大堆仿函数为lesspq.push(5);pq.push(2);pq.push(4);pq.push(1);pq.push(3);while (!pq.empty()) {cout pq.top() ;pq.pop();}cout endl;thj::priority_queueint, vectorint, thj::greaterint pq1; //建小堆仿函数为greater需要显式指定pq1.push(5);pq1.push(2);pq1.push(4);pq1.push(1);pq1.push(3);while (!pq1.empty()) {cout pq1.top() ;pq1.pop();}cout endl;std::vectorint v;v.push_back(1);v.push_back(8);v.push_back(2);v.push_back(3);v.push_back(6);thj::priority_queueint pq2(v.begin(), v.end()); //迭代器区间构造while (!pq2.empty()) {cout pq2.top() ;pq2.pop();}cout endl;
}
