天津市建设 中标公示网站,上海资本公司排名,苏州企业网站设计制作,国内新闻最新消息2022欢迎来到 CILMY23的博客
#x1f3c6;本篇主题为#xff1a;优先级队列priority_queue的使用和模拟实现#xff0c;巧妙利用仿函数解决优先级
#x1f3c6;个人主页#xff1a;CILMY23-CSDN博客
#x1f3c6;系列专栏#xff1a; C | C语言 | 数据结构与算法 | Linux… 欢迎来到 CILMY23的博客
本篇主题为优先级队列priority_queue的使用和模拟实现巧妙利用仿函数解决优先级
个人主页CILMY23-CSDN博客
系列专栏 C | C语言 | 数据结构与算法 | Linux | 算法专题
感谢观看支持的可以给个一键三连点赞收藏评论。如果你觉得有帮助还可以点点关注 目录
前言 优先级队列的使用
优先级队列的常用接口 实例演示
优先级队列的模拟实现
如何控制优先级 前言
上期我们讲了栈和队列的使用和模拟实现本期我们将探究priority_queue,优先级队列的使用和模拟实现并应用仿函数来解决优先级的问题。 优先级队列的使用
我们还是从官方文档看起 优先级队列是容器适配器的一种根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。此语法类似于堆在堆中可以随时插入元素并且只能检索堆的最大元素(优先级队列中位于顶部的元素)。优先级队列被设计成容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
不难看出实际上的优先级队列和使用堆没什么差别当然从接口上我们也不难看出其次是它没有单独的头文件它和queue公用一个头文件都是queue.h。
优先级队列的常用接口
接口功能bool empty() const;检测优先级队列是否为空是返回true否则返回 falseconst value_type top() const;返回优先级队列中最大(最小元素)即堆顶元素void push (const value_type val);在优先级队列中插入元素xvoid pop();删除优先级队列中最大(最小)元素即堆顶元素 实例演示
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意默认情况下priority_queue是大堆。
215. 数组中的第K个最大元素
我们可以通过这个例子来看。
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint pq;for (auto e : nums) {pq.push(e);}// 删除前K-1个元素for (int i 0; i k - 1; i) {pq.pop();}return pq.top();}
};
本题要求在一个整数数组中找到第k个最大的元素且必须设计时间复杂度为O(n)的算法。如果我们使用堆排序就可以发现时间复杂度为O(nlogn)建堆的时间代价是O(n)删除的总代价是O(klogn)因为kn故渐进时间复杂为O(nklogn)O(nlogn)。
那如果我们想实现小堆就可以使用greaterfunctional它是greater算法的头文件创建实例priority_queueint, vectorint, greaterint
优先级队列的模拟实现
首先我们先写好各类接口函数以及容器适配器。
templateclass T,class Container vectorT
class priority_queue
{
public:bool empty() const{}size_t size() const{}const T top() const{}void push(const T x){}void pop(){}private:Container _con;
};
大部分和堆的实现都类似可以参照过去的文章堆的模拟。那这里的判空大小堆顶接口函数都很容易写重点还是插入和删除这里的插入还是和以前一样先插入到末尾然后再向上调整。
void push(const T val)
{_con.push_back(val);Adjustup(_con.size() - 1);
}Adjustup(int child)
{int parent (child - 1) / 2;while (child 0){if (_con[child] _con[parent]){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}
} 在C中我们不再像过去那样造轮子确实会轻松不少利用交换函数swap和插入函数就能节省很多时间。
删除我们说堆的删除是删除堆顶数据所以我们进行首尾交换然后再进行向下调整。
void pop()
{if (_con.empty()){return ;}swap(_con.front(), _con.back());_con.pop_back();AdjustDown(0);
}void AdjustDown(int parent)
{int child parent * 2 1;while (child _con.size()){////如果左孩子比右孩子大则从右孩子开始if (child 1 _con.size() _con[child] _con[child 1]){child;}if (_con[child] _con[parent]){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}
}
注意这里在找左孩子和右孩子的时候必须要考虑到二者都在size之内否则就会越界报错啦。
如何控制优先级
过去我们控制优先级是在qsort中用函数指针解决的而在c中我们用仿函数解决。
什么是仿函数
仿函数Functor是 C 中通过重载 operator() 运算符的类或结构体其对象可以像函数一样被调用。它常用于定制算法的行为例如排序规则、比较逻辑等相比普通函数指针仿函数能携带状态成员变量灵活性更高。 例如我们在算法algorithm中使用sort我们可以利用两个仿函数来控制排序的逻辑。
struct greater
{bool operator()(int a, int b){return a b;}
};sort(vec.begin(), vec.end(), greater()); priority_queue 的仿函数 在我们的priority_queue中它默认为大堆而这里使用的是lessless表示父节点值 子节点最大堆实际就是子节点要小于父节点我们原先的逻辑是如果子节点大于父节点我们就交换所以这里我们可以把逻辑变通一下如果父节点小于子节点我们就交换两个值于是我们这里的仿函数就和库里一样了。
templateclass Tstruct less
{bool operator()(const T x,const T y){return x y;}
};//向上调整
void AdjustUp(int child)
{int parent (child - 1) / 2;while (child 0){Compare com;//子节点大于父节点//if (_con[child] _con[parent])//父节点小于子节点//if(_con[parent] _con[child])if(com(_con[parent],_con[child])){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
同理把向下调整也改造一下删除完后greater就是子节点大于父节点也就是父节点小于等于子节点我们原先的逻辑是如果父节点比子节点大我们就交换父子节点。
templateclass Tstruct greater
{bool operator()(const T x, const T y){return x y;}
};void AdjustDown(int parent)
{int child parent * 2 1;while (child _con.size()){Compare com;//如果左孩子比右孩子大则从右孩子开始//if (child 1 _con.size() _con[child] _con[child 1])//if (child 1 _con.size() _con[child 1] _con[child])if (child 1 _con.size() com(_con[child] , _con[child 1])){ child;}if (com(_con[parent] ,_con[child])){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}到这里我们的优先级队列就实现完了主要还是利用仿函数进行一个控制我们可以利用仿函数控制大堆和小堆。
