前程无忧网杭州网站建设类岗位,短视频推广app,深圳建网站哪个公司,网站系统免费目录 前言priority_queue的使用简单使用在OJ中的使用 priority_queue的模拟实现基本功能仿函数在这里插入图片描述 前言 上一节我们说了stack和queue这两种容器适配器#xff0c;而priority_queue#xff08;优先级队列#xff09;同样也是属于容器适配器#xff0c;它会优… 目录 前言priority_queue的使用简单使用在OJ中的使用 priority_queue的模拟实现基本功能仿函数在这里插入图片描述 前言 上一节我们说了stack和queue这两种容器适配器而priority_queue优先级队列同样也是属于容器适配器它会优先处理级别较高的值如数字最大的其实也就是数据结构中的堆。即物理结构上是数组逻辑结构上是一颗完全二叉树。
priority_queue的使用
简单使用 库里面的priority_queuecplusplus–priority_queue 优先级队列是一种容器适配器根据某种严格的弱排序标准使得它的第一个元素总是它所包含的元素中最大的。 也就类似于堆其中元素可以随时插入并且只能检索堆顶元素优先级队列中位于顶部的元素。 我们可以先来查看一下priority_queue的类型 我们使用typeid来查看一个变量的类型。
#includeiostream
#includequeue//优先级队列存在于此头文件中
#includevector
using namespace std;int main()
{priority_queueint pq;cout typeid(pq).name() endl;//查看类型return 0;
}由图该模板中由两个逗号隔开代表的意思分别是
int所存储的数据类型class std::vectorint,class std::allocatorint 底层所使用的容器struct std::lessint比较方式默认是less即小于比较决定谁的优先级更高。
priority_queue的接口也不多就以下几个
函数说明接口说明empty()检测是否为空size()返回元素个数top()返回优先级队列中最大最小元素即堆顶元素push(x)在优先级队列中插入xpop()删除优先级队列中最大最小元素即堆顶元素
使用也很简单
#includeiostream
#includequeue
#includevector
using namespace std;int main()
{priority_queueint pq;//cout typeid(pq).name() endl;pq.push(5);pq.push(8);pq.push(3);pq.push(1);pq.push(9);while (!pq.empty())//输出默认大堆底层按小于号排序{cout pq.top() ;pq.pop();}cout endl;vectorint v { 8,3,6,1,9,4,5 };/*priority_queueint,vectorint,greaterint pq1;for (auto e : v){pq1.push(e);}*///直接使用迭代器构造priority_queueint, vectorint, greaterint pq1(v.begin(), v.end());while (!pq1.empty())//输出默认大堆底层按小于号排序{cout pq1.top() ;pq1.pop();}cout endl;return 0;
}结果如下 可以看到一旦我把默认的less比较方式换成了greater int 它就能实现小堆。 由于比较方式是在第三个参数所以如果需要修改就要把第二个参数一起写上。这就是为什么中间还要写vector int 的原因。 在OJ中的使用
Leetcode.数组中第k个大的元素 题目如下 给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 题目的意思还是比较容易理解的。我们优先能想到的就是将数组中的值进行排序然后去重但是任意一种排序方式的时间复杂度都超过了 O(n) 此时我们就能想到用堆它既能去重又能排序则就可以使用优先级队列来解决。 将所有数放入优先级队列中默认是大堆此时不断去除堆顶元素将前k-1个删掉再取堆顶元素即可。 代码如下
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint pq(nums.begin(), nums.end());for(int i 1; i k; i){pq.pop();}return pq.top();}
};priority_queue的模拟实现 priority_queue优先级队列属于容器适配器的一种它和stack和queue一样都不需要自己去实现功能只需要调用底层容器的功能即可但是为了符合堆的规则在插入和删除时还是要用到向上调整和向下调整来实现。 我们先来看一下优先级队列的一个框架为方便理解我们先将模板中的第三个参数给去除了
namespace emm//使用命名空间防止与库里面的发生冲突
{templateclass T, class container vectorint//默认底层容器为vectorclass priority_queue{pubilc:private:container _con;};
}基本功能 对于其判空取大小以及取堆顶元素都可以直接复用底层容器的实现即可。
bool empty() const
{return _con.empty();
}
size_t size() const
{return _con.size();
}
const T top() const
{return _con.front();
}当我想要插入一个元素我需要先尾插这一个数据然后根据堆的规则进行向上调整。
void push(const T val)
{_con.push_back(val);AdjustUp(size() - 1);
}
void AdjustUp(int child)//大堆
{int parent (child - 1) / 2;while (child 0){if (_con[parent] _con[child])//遵循库里面小于是大堆//如果孩子节点大于父亲节点则交换{swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}可以通过测试来看看 运行结果可以看出它是一个大堆。 当我想pop即删除堆顶元素时就要用到向下调整法我们不能直接将堆顶元素删除那样会破坏堆的规则所以要先将堆顶元素与最后一个元素进行交换然后将其删除最后利用向下调整为大堆。 代码如下
void pop()
{swap(_con[0], _con[_con.size() - 1]);//先交换_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[parent] _con[child])//遵循库里面小于是大堆{swap(_con[parent], _con[child]);parent child;child parent * 2 1;}elsebreak;}
}这样输出就是排好序的数组了 此时我们将构造函数写上
//强制生成默认构造
priority_queue() default;template class InputIterator
priority_queue(InputIterator first, InputIterator last)//迭代器区间构造
{while (first ! last){push(*first);first;}
}仿函数 当我们按照上面正常写法想把建大堆改成建小堆时要把向上调整和向下调整中的小于号都改为大于号这样操作较为繁琐那么有没有简单一点的操作呢答案是有的也就是仿函数。顾名思义就是对象可以像函数一样调用。 例如 当然括号里面带有参数也是可以的。 此时我们就可以写出两个比较大小的仿函数
templateclass T
struct less
{bool operator()(const T x, const T y){return x y;}
};
templateclass T
struct greater
{bool operator()(const T x, const T y){return x y;}
};这样就可以使得比较大小可以像函数一样去使用 此时可以将priority_queue中的模板参数变为3个而参数3的缺省值就是less
templateclass T, class container vectorint,class Compare lessint此时向上调整和向下调整就变为了
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[child], _con[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}void AdjustDown(int parent)
{Compare com;//实例化一个对象int 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[child1])){child;}//if (_con[parent] _con[child])//遵循库里面小于是大堆if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}elsebreak;}
}如果我们想要切换成小堆就按正常操作写模版实例化时将参数变为greater int 即可。
vectorint v { 8,3,6,1,9,4,5 };
emm::priority_queueint pq2(v.begin(), v.end());
while (!pq2.empty())
{cout pq2.top() ;pq2.pop();
}
cout endl;emm::priority_queueint, vectorint, greaterint pq3(v.begin(), v.end());
while (!pq3.empty())//变为小堆按大于号排序
{cout pq3.top() ;pq3.pop();
}
cout endl;感谢大家观看如果大家喜欢希望大家一键三连支持一下如有表述不正确也欢迎大家批评指正。
