北京优化词网站,高邮做网站,梧州论坛看点,织梦免费网站模块下载地址前言
上一期我们对stack和queue进行了使用的介绍#xff0c;以及对底层的模拟实现#xff01;以及容器适配器做了介绍#xff0c;本期我们在来介绍一个容器适配器priority_queue#xff01;
本期内容介绍 priority_queue的使用 仿函数介绍 priority_queue的模拟实现 什么…前言
上一期我们对stack和queue进行了使用的介绍以及对底层的模拟实现以及容器适配器做了介绍本期我们在来介绍一个容器适配器priority_queue
本期内容介绍 priority_queue的使用 仿函数介绍 priority_queue的模拟实现 什么是priority_queue? priority_queue称为优先级队列实际上就是堆如果忘了什么是堆 请点击这里它也是容器适配器底层默认的容器是vector默认是大堆 常用的接口介绍
empty 判断是否为空 size 元素的个数 top 获取堆顶元素 注意堆顶元素是不允许修改的如果修改了会影响整个堆的结构所以用const修饰 push 插入一个新元素 pop 删除堆顶的元素 OK用一下
void test()
{priority_queueint pq;pq.push(2);pq.push(15);pq.push(-1);pq.push(90);size_t sz pq.size();cout sz endl;bool empty pq.empty();cout empty endl;int top pq.top();cout top endl;while (!pq.empty()){cout pq.top() ;pq.pop();}
} priority_queue在是很有用的例如TopK问题和堆排序。堆排序不在介绍在数据结构已经详细的介绍了这里拿个题目来再次理解一下TopK
数组中第K大元素 它的题目意思就是让你找出第K大的元素但是要求时间度杂度O(N)! 思路这里有三种 第三种最优。 1、利用排序数组然后返回倒数k个元素即可 2、借助堆 3、快速选择算法算法专栏介绍 我们这里就先介绍前两种
1、利用排序数组然后返回倒数k个元素即可时间复杂度不符合
class Solution {
public:int findKthLargest(vectorint nums, int k) {sort(nums.begin(), nums.end());return nums[nums.size() -k ];}
}; 这里虽然过了但是这个代码的时间复杂度是O(N*logN)不符合
2、借助堆
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint pq(nums.begin(), nums.end());//将数组的元素放到堆里面for(int i k; i 1; i--)//将前k-1个弹出堆{pq.pop();}return pq.top();//返回堆顶的元素}
}; OK这就过了但是时间复杂度也是不行的也还是O(N*logN)。最优解在后续的算法专栏会介绍这主要是主要是演示一下堆在OJ中的用法~
仿函数介绍 仿函数是一种类它的对象可以向函数一样被调用。他是一种可调用对象可以向像函数一样接收参数并返回结果通常情况仿函数是通过一个类实现operator ()来实现的 例如上面刚介绍的priority_queue: 这里的less就是一个仿函数还有就是sort: OK举个仿函数的例子
struct cmp
{bool operator()(const int a, const int b){return a b;}
};//class cmp
//{
//public:
// bool operator()(const int a, const int b)
// {
// return a b;
// }
//};void test()
{cmp cm;int result1 cm(3, 5);int result2 cm.operator()(3, 5);int result3 cmp()(3, 5);
} 第一种和第二种本质是同一种第二种是第一种的显示调用第三种是匿名对象调用当然这里的struct可以是class但注意的是如果是class你必须吧权限设置为public 仿函数的用途 仿函数的用途我目前碰到的有两种后面遇见了在补充 1、STL算法库中的某些算法来用 仿函数定义他们的行为例如sort等 2、容器的自定义行为例如priority_queue指定大小堆等 #include algorithm
templateclass T
struct Compare
{bool operator() (const T a, const T b){return a b;}
};void test()
{ vectorint v { 1,3,0,12,43,5,9 };sort(v.begin(), v.end());//默认是升序for (const auto e : v){cout e ;}cout endl;sort(v.begin(), v.end(), Compareint());//降序 --》用匿名对象Compareint cmp;sort(v.begin(), v.end(), cmp);//降序 --》用实名对象for (const auto e : v){cout e ;}cout endl;
} 大堆和小堆
void test()
{vectorint v { 0,12,43,5,9 };priority_queueint pq1(v.begin(), v.end());//默认大堆while (!pq1.empty()){cout pq1.top() ;pq1.pop();}cout endl;priority_queueint, vectorint, greaterint pq2(v.begin(), v.end());//指定为小堆while (!pq2.empty()){cout pq2.top() ;pq2.pop();}cout endl;
} 这里priority_queue默认是less template class T, class Container vectorT, class Compare lesstypename Container::value_type class priority_queue; 如果要切换为小堆就得指定仿函数为greater,但是我们知道参数是倒着从右往左传递的所以这里要指定为小堆的话还要指定它的底层适配的容器~一般是vector也可以是deque priority_queue的模拟实现
priority_queue()
{}bool empty() const
{return _con.empty();
}size_t size() const
{return _con.size();
}const T top() const
{return _con.front();
} 这几个不在多说很简单直接调用默认容器的相关接口即可~主要介绍一下这里的插入、删除和用用一段迭代器区间构造 push 先插入到适配容器的尾部然后进行向上调整向上调整不了解的点击上面介绍对那个文章的链接回忆一下 另外注意的是这里我们不再是以前的大于小于比较了而是用仿函数 void adjust_up(size_t child)
{size_t parent (child - 1) / 2;while (child 0){if (cmp()(_con[parent], _con[child]))//孩子比父亲大小交换{swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;//否则结束掉}}
}
void push(const T val)
{_con.push_back(val);adjust_up(_con.size() - 1);
}
pop 先交换堆顶数据和最后一个数据然后删除掉堆顶数据进行向下调整~向下调整和向上调整一样详细见数据结构那里 另外注意的是这里我们不再是以前的大于小于比较了而是用仿函数 void adjust_down(size_t parent)
{size_t child parent * 2 1;//假设第一个孩子就是要交换的孩子while (child _con.size()){if (child 1 _con.size() cmp()(_con[child], _con[child 1]))//假设错了{child;//调整}if (cmp()(_con[parent], _con[child]))//孩子比父亲大小{swap(_con[parent], _con[child]);//交换parent child;child parent * 2 1;}else{break;//否则结束掉}}
}
void pop()
{swap(_con.front(), _con.back());_con.pop_back();adjust_down(0);
}
迭代器区间构造 这里其实注意的就一点当把数据给到适配器的容器后要保证是堆结构所以就要建堆建堆的方式有两种详见数据结构那里向上调整建堆 和 向下调整建堆 templateclass Iterator
priority_queue(Iterator first, Iterator last):_con(first, last)
{int sz _con.size();//向下调整建堆 O(N)for (int i (sz - 1) / 2; i 0; i--){adjust_down(i);}//向下调整建堆 O(N*logN)//for (int i 1; i sz; i)//{// adjust_up(i);//}
}
全部源码
#pragma once#include vectornamespace cp
{templateclass Tstruct less{bool operator()(const T a, const T b){return a b;}};templateclass Tstruct greater{bool operator()(const T a, const T b){return a b;}};templateclass T, class Con std::vectorT, class cmp lessTclass priority_queue{public:priority_queue() {}templateclass Iteratorpriority_queue(Iterator first, Iterator last):_con(first, last){int sz _con.size();//向下调整建堆 O(N)for (int i (sz - 1) / 2; i 0; i--){adjust_down(i);}//向下调整建堆 O(N*logN)//for (int i 1; i sz; i)//{// adjust_up(i);//}}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);adjust_up(_con.size() - 1);}void pop(){swap(_con.front(), _con.back());_con.pop_back();adjust_down(0);}private:void adjust_up(size_t child){size_t parent (child - 1) / 2;while (child 0){if (cmp()(_con[parent], _con[child]))//孩子比父亲大小交换{swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;//否则结束掉}}}void adjust_down(size_t parent){size_t child parent * 2 1;//假设第一个孩子就是要交换的孩子while (child _con.size()){if (child 1 _con.size() cmp()(_con[child], _con[child 1]))//假设错了{child;//调整}if (cmp()(_con[parent], _con[child]))//孩子比父亲大小{swap(_con[parent], _con[child]);//交换parent child;child parent * 2 1;}else{break;//否则结束掉}}}private:Con _con;};
}
OK验证一下 OK没有问题本期内容就分享到这里好兄弟我们下期再见 结束语无人问津的日子更应该加倍努力
