免费门户网站建设,wordpress 图床 插件,wordpress主题 导出,长春网络传媒做网站骗钱文章目录 模拟priority_queue性质#xff1a;成员函数#xff1a;向上调整、向下调整push/pop/empty/top/size/empty成员变量 仿函数struct和class练习题堆的一些性质 模拟priority_queue
性质#xff1a;
是容器适配器#xff1b; 底层逻辑是堆#xff0c;适配器是vect… 文章目录 模拟priority_queue性质成员函数向上调整、向下调整push/pop/empty/top/size/empty成员变量 仿函数struct和class练习题堆的一些性质 模拟priority_queue
性质
是容器适配器 底层逻辑是堆适配器是vector 默认情况下是大堆从大到小排第一个最大最后一个最小
成员函数
向上调整、向下调整
时间复杂度就是堆的时间复杂度 //向上调整,时间复杂度是o(logn)void AdjustUp(int child){int parent (child - 1) / 2;while (child){if (compare(_con[parent], _con[child])){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}//向下调整void AdjustDown(int parent){int child (parent * 2) 1;while (child _con.size()){//左右孩子种选出大的一个,每次循环都要选if (_con[child] _con[child 1] child 1 _con.size()) {child;}if (_con[parent] _con[child]){swap(_con[child], _con[parent]);parent child;child (parent * 2) 1;}else(){break;}}}push/pop/empty/top/size/empty void push(const T x){_con.push_back(x);AdjustUp(_con.size() - 1);}//删除头void pop(){//头和尾部交换swapswap(_con[0], _con[_con.size() - 1]);_con.pop_back(); //向下调整AdjustDown(0);T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}成员变量 仿函数
他的对象可以像函数那样使用比如调用他的operator(); 优先级序列通过仿函数来控制大堆还是小堆 这里有个设计的坑就是大堆用的是Less,就是大堆用的x1 x2那个
仿函数怎么用的 就是仿函数的成员函数operator(),如下图的compare(),compare就是一个对象然后调用他的operator();
struct和class
出了默认访问限定符不一样、其他都是一样的 部分共有、部分私有用class 都是共有用struct;
练习题
数组中第k个最大元素
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint q1;for(auto e : nums){q1.push(e);//这个时间复杂度为o(logn)}//整体为时间复杂读为o(o*logn)for(int i 1; i k; i){q1.pop();}return q1.top();}
};第一种效率太低 第二种先建立一个k个元素的priority_queue其次用后面的push进来最后得到的top元素正好是第k大的 priority_queue,push进去自己排序大到小
class Solution {
public:int findKthLargest(vectorint nums, int k) {//解法1/*priority_queueint q1;for(auto e : nums){q1.push(e);//这个时间复杂度为o(logn)}//整体为时间复杂读为o(o*logn)for(int i 1; i k; i){q1.pop();}*///解法2priority_queueint, vectorint, greaterint minHeap;size_t i 0;for(; i k; i)minHeap.push(nums[i]);for(; i nums.size(); i)//这个i是接着上面的继续往下{if(nums[i] minHeap.top()){minHeap.pop();minHeap.push(nums[i]);}}return minHeap.top();}
};堆的一些性质
下角标减1再除2就是父级的下角标 就是一个数组只不过看成完全二叉树了 下角标parent (child -1) / 2 时间复杂度logn
