c++ stl 优先队列_低优先级队列要等几局
大家好，又见面了，我是你们的朋友全栈君。
priority_queue文章目录priority_queuepriority_queue的使用priority_queue在OJ中的使用数组中第k个最大元素priority_queue模拟实现push的模拟实现pop模拟实现迭代器区间构造函数模拟实现size的模拟实现empty的模拟实现top的模拟实现swap的模拟实现仿函数typename仿函数的变异玩法 翻译：
优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。虽然他叫优先级队列，但是它不符合队列的特性：
priority_queue的使用 优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆
函数声明
接口说明
priority_queue()/priority_queue(first,last)
构造一个空的优先级队列
empty( )
检测优先级队列是否为空，是返回true，否则返回false
top( )
返回优先级队列中最大(最小元素)，即堆顶元素
push(x)
在优先级队列中插入元素x
pop()
删除优先级队列中最大(最小)元素，即堆顶元素
代码语言：javascript复制void test_priority_queue()
{
priority_queue
priority_queue
pq.push(1);
pq.push(10);
pq.push(12);
pq.push(3);
pq.push(5);
cout< while(!pq.empty()) { cout< pq.pop(); } cout< } int main() { return 0; }pop/top：取优先级最高的，默认是大的优先级高 实际上优先级队列的底层实现是堆 如果想要小的优先级高： 代码语言：javascript复制priority_queue 这样就成了小的优先级大了 下面我们来做一个题： priority_queue在OJ中的使用数组中第k个最大元素题目描述： 给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 方法一：排序，然后返回第k个最大的元素 代码语言：javascript复制class Solution { public: int findKthLargest(vector { //sort(nums.begin(),nums.end());//默认升序 //return nums[nums.size()-k]; sort(nums.begin(),nums.end(),greater return nums[nums.size()-k]; } }; 时间复杂度：O(N*logN) 方法二：利用优先队列 因为优先队列的本质上就是堆，pop取出第一大的数，将该队列pop k-1次，此时该队列的top就是第k大的数。 代码语言：javascript复制class Solution { public: int findKthLargest(vector { priority_queue while(--k) { maxHeap.pop(); } return maxHeap.top(); } }; 时间复杂度：O(N+K*logN)，空间复杂度：O(N) 怎么将时间复杂度和空间复杂度更优？ 方法三： 本质上和方法二一样，可以说是方法二的优化，我们可以建k个数的小堆，首先将前k个数进堆，然后如果后面的数大于堆里面的top时，先pop，然后再将该数push进去，结束时，第K大就是该堆的top 代码语言：javascript复制class Solution { public: int findKthLargest(vector { //建立K个数的小堆 priority_queue for(size_t i = 0;i< k;++i) { kMinHeap.push(nums[i]); } for(size_t j = k;j { if(kMinHeap.top() { kMinHeap.pop(); kMinHeap.push(nums[j]); } } return kMinHeap.top(); } }; *时间复杂度：O(K+(N-K)logK)，空间复杂度：O(K)，N远大于K时，这种方法更实用，尤其是N大到内存里存不下 priority_queue模拟实现通过对priority_queue的底层结构就是堆，因此此处只需对堆进行通用的封装即可，也就是用vector存储堆的元素，在priority_queue里面实现堆的操作即可，我们首先模拟实现优先级队列先不要第三个仿函数参数： 代码语言：javascript复制namespace Z { template class priority_queue { public: priority_queue() { }; private: Container _con; }; }我们来看看优先级队列的接口： push的模拟实现代码语言：javascript复制void AdjustUp(int child) { //默认大堆 int parent = (child-1)/2; while(child > 0) { if(_con[parent]<_con[child]) { swap(_con[parent],_con[child]); child = parent; parent = (child-1)/2; } else { break; } } } void push(const T& X) { _con.push_back(x);//先将元素插进去 AdjustUp(_con[_con.size()-1]);//向上调整一次 }pop模拟实现代码语言：javascript复制void AdjustDown(size_t parent) { size_t child = parent*2+1; while(child<_con.size()) { if(child+1<_con.size() && _con[child]<_con[child+1])//右孩子存在且左孩子小于右孩子 { child++;//右孩子 } if(_con[parent]<_con[child]) { swap(_con[parent],_con[child]); parent = child; child = parent*2+1; } else { braek; } } } void pop() { swap(_con[0],_con[_con.size()-1])//先将第一个和最后一个元素互换 _con.pop_back();//将最后一个元素pop掉 AdjustDown(0);//向下调整一次 }迭代器区间构造函数模拟实现代码语言：javascript复制template priority_queue(InputIterator first,InputIterator last) { while(first!=last) { _con.push_back(*first); ++first; } //建堆 for(size_t i = (_con.size()-1-1)/2;i >= 0;i--) { AjustDown(0); } }size的模拟实现代码语言：javascript复制size_t size() { return _con.size(); }empty的模拟实现代码语言：javascript复制bool empty() { return _con.empty(); }top的模拟实现代码语言：javascript复制const T& top() { return _con[0]; }swap的模拟实现代码语言：javascript复制void swap(priority_queue& x) { swap(_con,x._con); }仿函数对于上面的模拟实现我们还差点意思，因为库里面的优先级队列模板还有第三个参数：仿函数，我们前面学习优先级队列的使用的时候知道了我们实例化对象传参时多加一个仿函数参数就可以将优先级改变，接下来就说一说什么是仿函数： 前面我们知道加入了仿函数参数将默认建大堆改为了建小堆，而建大堆和建小堆的代码唯一的区别就在于向上调整算法和向下调整算法当中的比较符号的改变，那么我们怎么可以让它可以灵活改变呢？有人想到函数传参，但是我们仔细想想函数传参是不能传符号的，于是C++当中增加了仿函数/函数对象这个用法，通过仿函数类型的对象，我们可以像函数一样去使用。 仿函数是什么呢？仿函数是一个自定义类型： 代码语言：javascript复制template class Less { public: bool operator()(T x,T y) { return x < y; } }; 我们在Less这个类当中重载了()运算符，函数调用用的运算符就是()，比如我们想要调用一个比较大小的函数：IsLess(x,y);这样即可调用成功，而我们创建了这个类使得我们可以像函数一样的去使用它：Less IsLess;//创建对象，IsLess(x,y);//调用重载()的函数 我们来看一个例子： 代码语言：javascript复制class Less { public: bool operator()(int x,int y) { return x < y; } }; int main() { Less less; cout< //实际上是这样调用less.operator()(1,2) return 0; } 可以看到输出1为真 当然我们还可以写Greater类来比较大于： 代码语言：javascript复制template class Greater { public: bool operator()(T x,T y) { return x > y; } };我们也可以看一个例子： 代码语言：javascript复制template class Greater { public: bool operator()(T x,T y) { return x > y; } }; int main() { Greater cout< //实际上是这样调用greater.operator()(1,2) return 0; } 可以看到输出的是0，为假 通过仿函数我们知道了：函数传参不可以传符号，但是可以传对象，传对象完成想要的功能 代码语言：javascript复制int main() { priority_queue } 我们传一个对象就能完成想要的功能，需要注意的是优先级队列是类模板，我们传参数显式实例化就好了，传的是类型，而算法中的sort函数是函数，需要传的是对象 通过仿函数的讲解，我们就可以将向上调整算法和向下调整算法改一下： 代码语言：javascript复制//向上调整算法 void AdjustUp(int child) { Compare com; int parent = (child - 1) / 2; while (child > 0) { if (com(_con[parent], _con[child])) { swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } //向下调整算法 void AdjustDown(size_t parent) { Compare com; size_t child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { child = child + 1; } if (com(_con[parent], _con[child])) { swap(_con[parent], _con[child]); parent = child; child = parent * 2 + 1; } else { break; } } }typename可能有的人疑问，在文档当中仿函数的显式实例化为什么是这么一长串呢？ 这里面的value_type其实就是T： 而typename的作用是什么呢？ typename的第一个作用是用作模板里面，来声明某种类型： 代码语言：javascript复制template 代码语言：javascript复制template void foo(const T& y) { T::bar x;//编译到这里编译器不知道T类型是什么，还没有实例化出来，不知道去哪找bar } struct AA { typedef int bar; }; int main() { AA aa; foo(aa); }这里会报错，为什么呢？ 因为编译到T::bar x;这里，编译器不知道T类型是什么，还没有实例化出来，不知道去哪里找bar，此时我们需要将typename加上： 代码语言：javascript复制template void foo(const T& y) { typename T::bar x;//这样可以等调用这个函数实例化出来时才去找bar，这个时候加上typename就是为了告诉编译器，它后面的一大串字符串都是一个类型。 } 这样可以等调用这个函数实例化出来时才去找bar，这个时候加上typename就是为了告诉编译器，它后面的一大串字符串都是一个类型。 代码语言：javascript复制#include #include #include #include using namespace std; #include #include namespace Z { template class Less { public: bool operator()(T x, T y) { return x < y; } }; template class Greater { public: bool operator()(T x, T y) { return x > y; } }; template //默认用Less仿函数，比较的是小于，建大堆,如果传Greater仿函数，比较的是大于，建小堆 class priority_queue { public: priority_queue() { } template 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(0); } } //向上调整算法 void AdjustUp(int child) { Compare com; int parent = (child - 1) / 2; while (child > 0) { //if(_con[parent] < _con[child]) if (com(_con[parent], _con[child])) { swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } //向下调整算法 void AdjustDown(size_t parent) { Compare com; size_t child = parent * 2 + 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 = child + 1; } //if(_con[parent]<_con[child]) if (com(_con[parent], _con[child])) { swap(_con[parent], _con[child]); parent = child; child = parent * 2 + 1; } else { break; } } } void push(const T& X) { _con.push_back(X); AdjustUp(_con.size() - 1); } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } const T& top() { return _con[0]; } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; }; void test_priority_queue() { //priority_queue Z::priority_queue pq.push(1); pq.push(10); pq.push(12); pq.push(3); pq.push(5); cout << pq.top() << endl; while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; } }仿函数的变异玩法注意： 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。 代码语言：javascript复制class Date { public: Date(int year =1900,int month = 1,int day = 1) : _year(year) , _month(month) , _day(day) { } //重载< bool operator<(const Date& d)const { return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day); } friend ostream& operator<<(ostream& _cout, const Date& d); friend class PDateLess; } //重载<< ostream& operator<<(ostream& _cout, const Date& d) { _cout << d._year << "-" << d._month << "-" << d._day; return _cout; } int main() { priority_queue pq.push(Date(2021,11,24)); pq.push(Date(2021,10,24)); pq.push(Date(2021,12,24)); pq.push(Date(2022,11,24)); cout< pq.pop(); //选出最大 return 0; } 当我们优先级队列使用自定义类型时，我们必须要在该自定义类型当中重载<或者>。因为push和pop操作会调用仿函数类的重载函数，该重载函数进行比较时，默认是不支持自定义类型比较的，所以需要重载 我们还可以这样玩：当传的时Date*时，用less仿函数会有问题： 代码语言：javascript复制int main() { priority_queue pq.push(new Date(2024,11,24)); pq.push(new Date(2021,10,24)); pq.push(new Date(2021,12,24)); pq.push(new Date(2022,11,24)); cout<<*pq.top()< pq.pop(); //选出最大 return 0; } 此时程序出问题了，最大的明明是2024-11-24，却打印了2021-12-24 为什么呢？因为我们的数据类型为指针，仿函数类型的重载函数比较的是地址大小，所以会出问题 这是一种仿函数的变异玩法，我们可以控制仿函数比较方式我们需要另外写个仿函数： 代码语言：javascript复制class PDateLess { public: bool operator()(const Date*p1,const Date* p2) { if(p1->_year< p2->_year ||(p1->_year==p2->_year&&p1->_month ||(p1->_year==p2->_year&&p1->_month==p2->_month&&p1->_day { return true; } else { return false; } //或者这样比较，前提是自定义类型中重载了<运算符 //return *p1 < *p2; } }; int main() { priority_queue pq.push(new Date(2024,11,24)); pq.push(new Date(2021,10,24)); pq.push(new Date(2021,12,24)); pq.push(new Date(2022,11,24)); cout< pq.pop(); //选出最大 return 0; } 此时就没有问题了 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。 发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/190405.html原文链接：https://javaforall.cn