小公司网站维护,小程序外包公司出名,网站建设项目模板,如何在服务器上发布网站目录
1.关于优先队列
2.priority_queue的使用
1.构造方法
2.empty();判空
3.size();
4.top();
5.push(val);
6.pop();
3.优先队列模拟实现 4.用优先队列解决数组中第K个大的元素 1.关于优先队列 在C中#xff0c;可以使用STL#xff08;标准模板库#xff09;中的p…目录
1.关于优先队列
2.priority_queue的使用
1.构造方法
2.empty();判空
3.size();
4.top();
5.push(val);
6.pop();
3.优先队列模拟实现 4.用优先队列解决数组中第K个大的元素 1.关于优先队列 在C中可以使用STL标准模板库中的priority_queue类来实现优先队列。priority_queue是一个模板类可以存储任意类型的元素并按照元素的优先级进行排序。 1. 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。 2.类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元 素 ) 。 3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类 queue 提供一组特 定的成员函数来访问其元素。元素从特定容器的 “ 尾部 ” 弹出其称为优先队列的顶部。 4. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问并支持以下操作 empty() 检测容器是否为空 size() 返回容器中有效元素个数 front() 返回容器中第一个元素的引用 push_back() 在容器尾部插入元素 pop_back() 删除容器尾部元素 5.标准容器类 vector 和 deque 满足这些需求。默认情况下如果没有为特定的 priority_queue 类实例化指定容器类则使用vector 。 6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap 、 push_heap 和 pop_heap 来自动完成此操作。 2.priority_queue的使用 优先级队列默认使用vector 作为其底层存储数据的容器在 vector 上又使用了堆算法将 vector 中元素构造成 堆的结构因此 priority_queue 就是堆所有需要用到堆的位置都可以考虑使用 priority_queue 。 注意 默认情况下 priority_queue 是大堆 。 如果要小堆将第三个模板参数换成greater比较方式 #define _CRT_SECURE_NO_WARNINGS
#includeiostream
#includequeueusing namespace std;int main()
{vectorintnums { 1,2,4,6,78,4,23,65,3,12,5,45 };priority_queueint, vectorint, greaterint p(nums.begin(), nums.end());while (!p.empty()){cout p.top() ;p.pop();}return 0;
} 1.构造方法
1.priority queue();
构造一个空的优先级队列
comp用于对堆进行排序的比较对象。这可能是一个函数指针或函数对象能够通过比较其两个参数来执行严格的弱排序。 Compare 是第三类模板参数默认为lessT。默认为大根堆。
ctnr容器对象。 容器是第二个类模板参数priority_queue的基础容器的类型;默认为vectorT。
2.priority queuefirstlast);
将迭代器输入到序列中的初始和最终位置。在对基础容器进行排序之前将此序列中的元素插入到基础容器中。 使用的范围是 [firstlast它包括 first 和 last 之间的所有元素包括 first 指向的元素但不包括 last 指向的元素。
2.empty();判空 返回priority_queue是否为空即其大小是否为零。
此成员函数有效地调用基础容器对象的空成员。
3.size(); 返回priority_queue中的元素数。
此成员函数有效地调用基础容器对象的成员大小。
4.top(); 返回对 priority_queue 中顶部元素的常量引用。
top 元素是priority_queue中比较较高的元素以及调用 priority_queue:p op 时从容器中删除的下一个元素。此成员函数有效地调用基础容器对象的成员前端。
5.push(val); 在priority_queue中插入一个新元素。此新元素的内容初始化为 val。
此成员函数有效地调用基础容器对象的成员函数push_back然后通过对包含容器的所有元素的范围调用 push_heap 算法将其重新排序到堆中的位置。
6.pop(); 移除priority_queue顶部的元素有效地将其尺寸减小 1。删除的元素是具有最高值的元素。
在弹出之前可以通过调用成员 priority_queuetop 来检索此元素的值。此成员函数有效地调用 pop_heap 算法来保留 priority_queues 的堆属性然后调用基础容器对象的成员函数pop_back来删除元素。这将调用已删除元素的析构函数。
3.优先队列模拟实现
在vector容器基础上利用堆的向上调整算法和向下调整算法来实现。插入删除时保持堆属性。
#pragma oncenamespace wjc
{templateclass Tstruct less{bool operator()(const T left, const T right){return left right;}};templateclass Tstruct greater{bool operator()(const T left, const T right){return left right;}};templateclass T,class ContainervectorT,class ComparelessTclass priority_queue{public:priority_queue():_con(){};templateclass Iteratorpriority_queue(Iterator first, Iterator last):_con(first, last){int count _con.size();int root ((count - 1 - 1) / 2);while (root 0){AdjustDown(root);root--;}}void push(const T data){_con.pushback(data);AdjustUp(_con.size() - 1);}void pop(){if (empty())return;swap(_con.front(), _con.back());_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}size_t size()const{return _con.size();}const T top()const{return _con.front();}void AdjustDown(int parent){int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() Compare()(_con[child], _con[child 1]))child;if (Compare()(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}elsebreak;}}void AdjustUp(int child){int parent (child - 1) / 2;while (child 0){if (Compare()(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}elsebreak;}}private:Container _con;};}
测试代码
//如果需要升序排序 利用不同比较方法建小堆
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
using namespace std;
#includevector
#includepriority_queue.hint main()
{vectorint v { 2,3,6,3,2,45,74,23,21 };//wjc::priority_queueint p(v.begin(), v.end()); //默认大堆//如果需要升序排序 利用不同比较方法建小堆wjc::priority_queueint,vectorint,greaterint p(v.begin(), v.end());while (!p.empty()){cout p.top() ;p.pop();}return 0;
} 4.用优先队列解决数组中第K个大的元素
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint p(nums.begin(),nums.end());while(--k){p.pop();}return p.top();}
};
因为优先队列默认是大堆所以删除--k个元素堆顶就是第K大个元素也就是p.top();
