黄石网站建设哪家专业,山东淄博网络科技有限公司,网页开发基础知识,做一网站要学些什么优先级队列的概念
优先队列是一种容器适配器#xff0c;根据严格的弱排序标准#xff0c;它的第一个元素总是它所包含的元素中最大的此上下文类似于堆#xff0c;在堆中可以随时插入元素#xff0c;并且只能检索最大堆元素(优先队列中位于顶部的元 素)。优先队列被实现为容…优先级队列的概念
优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元 素)。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问并支持以下操作 5. . 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指 定容器类则使用vector。 6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。
priority_queue应用
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成 堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意 默认情况下priority_queue是大堆 优先级队列默认情况下是大堆
int main()
{//优先级队列默认情况下是大堆priority_queueintq1; //默认构造q1.push(4);q1.push(1);q1.push(2);q1.push(3);q1.push(5);cout q1.size() endl;cout q1.top() endl;vectorintv{ 3, 8, 2, 6, 0, 1, 9, 5, 7, 4 };priority_queueintq2(v.begin(),v.end()); //区间构造cout q2.size() endl;cout q2.top() endl;q2.pop();cout q2.top() endl;system(pause);return 0;
}2. 如何创建小堆 第一个参数代表优先级队列里元素的类型第二个参数代表优先级队列在底层的时候把元素放到vector里面在放之前要先对优先级队列里元素进行比较怎么比较就是第三个参数优先级中元素的比较规则默认为less按照小于的方式进行比较得到的是大堆所以我们如果要建小堆就用大于的方式进行比较
vectorintv{ 3, 8, 2, 6, 0, 1, 9, 5, 7, 4 };
priority_queueint,vectorint,greaterintq2(v.begin(),v.end()); //区间构造
cout q2.size() endl;
cout q2.top() endl;3. 如果在priority_queue中放自定义类型的数据用户需要在自定义类型中提供 或者 的重载。
class Date
{
public:Date(int year, int month, int day):_year(year), _month(month), _day(day){}//自定义数据类型需要给出自己的比较规则bool operator(const Date d)const {return _day d._day;}private:int _year;int _month;int _day;
};priority_queueDateq;
Date d1(2019, 10, 18);
Date d2(2019, 10, 17);
Date d3(2019, 10, 16);//如果在优先级队列中插入的是自定义数据类型的元素插入元素期间必须进行元素的比较
//(less : greater)
//需要对自定义类型的元素进行大于或者小于的比较
//类中必须重载或者的符号
q.push(d1);
q.push(d2);
q.push(d3);有些情况下用户可能需要提供比较器 指针:虽然可以直接比较但是按结果地址给出大小堆如果想要让其按照指针所指向空间元素给出大小堆必须改变比较规则 通过仿函数的方式传比较规则
class Compare
{
public:bool operator()(Date* pLeft, Date* pRight){if (pLeft-_day pRight-_day)return true;return false;}
};priority_queueDate*vectorDate*,Compareq2;
q2.push(d3);
q2.push(d1);
q2.push(d2);
//按这种方式默认情况给出的不完全是大堆有些情况给出的是小堆
//他是把指针排成了大小堆我们需要让指针里所指向的值排成大小堆在具体问题中的应用
优先级队列最主要的应用就是解决TopK问题 可以先排降序然后数组中第k个元素的下标就是K-1
class Solution {
public:int findKthLargest(vectorint nums, int k) {//默认给出升序序列,按降序方式排//类型后面跟一个()就相当于创建了一个没有名字的对象//函数调用期间要用类对象sort(nums.begin(),nums.end(),greaterint());return nums[k-1];}
};//建大堆
priority_queueintq(nums.begin(),nums.end());
for(size_t i 0 ;i k-1; i){q.pop();}
return q.top();由于篇幅不易过长所以接下来两个知识点另外写两篇体现以下是链接
容器适配器
详解容器适配器
模拟实现
模拟实现优先级队列
