虚拟主机做视频网站可以吗,招聘网站怎么做市场,全网获客营销系统,建设网站费用分析一、priority_queue的介绍和使用
1.1 priority_queue的介绍
1.优先队列是一种容器适配器#xff0c;根据严格的弱排序标准#xff0c;它的第一个元素总是它所包含的元素中最大的。
2.优先队列类似于堆#xff0c; 在堆中可以随时插入元素#xff0c; 并且只能检索最大堆…一、priority_queue的介绍和使用
1.1 priority_queue的介绍
1.优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。
2.优先队列类似于堆 在堆中可以随时插入元素 并且只能检索最大堆元素优先队列中位于顶部的元素。
3.优先队列被实现为容器适配器容器适配器即将特定的容器类封装作为其底层容器queue提供一组特定的成员函数来访问其元素元素从特定容器的尾部弹出这里称为优先队列的顶部。
4.底层容器可以是任何标准容器类模版也可以是其他特定设计的容器类容器应该可以通过随机访问和迭代器访问需要支持一下操作 empty() : 判断容器是否为空 size() : 返回容器中的有效元素个数 front() : 返回容器中的第一个元素的引用 push_back() : 在容器中尾插元素 pop_back() : 在容器中尾删元素
5.标准容器类vector和deque满足这些需求默认情况下如果没有指定底层容器的话就默认使用vector作为优先队列的底层容器。
6.需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap、和pop_heap来自动完成此操作。
1.2 priority_queue的使用
优先级队列默认使用vector作为求底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以使用priority_queue来替代。
注意默认情况下priority_queue是大堆。
函数声明接口说明priority_queue()/priority_queue(first, last)构造一个空的优先级队列empty()检测优先级队列是否为空是的话就返回true否则返回falsetop()返回优先级队列中最大最小的元素即堆顶元素默认是大堆返回最大元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大最小元素即删除堆顶元素
下面我们来看下优先队列的使用实例
#includeiostream
#includevector
#includequeue
//greater算法的头文件
#includefunctionalusing namespace std;void test1()
{//默认情况下是建大堆priority_queueint q1;vectorint arr{ 1, 3, 4, 5, 6 , 7, 9, };for (auto e : arr){q1.push(e);}while (!q1.empty()){cout q1.top() ;q1.pop();}cout endl;//将第三个模版参数换成great比较方式就是建小堆priority_queueint, vectorint, greaterint q2(arr.begin(), arr.end());while (!q2.empty()){cout q2.top() ;q2.pop();}cout endl;}int main()
{test1();return 0;
}二、OJ练习
leetcode215,数组中的第k个最大元素
题目 我们先看题意是让我们找出数组nums中的第k个最大的元素看到样例2中我们发现相同的数也会被算进k里面因此我们在这题上面就可以利用我们的优先级队列我们将优先级队列中的前k -1 个元素给pop出去那么剩下的元素中堆顶元素就是我们的第k个最大元素。
下面是这道题的参考代码
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint q1(nums.begin(), nums.end());//将前k - 1个元素pop掉就是第k个最大元素while(--k) q1.pop();//直接返回优先级队列的堆顶元素即可return q1.top();}
};三、 priority_queue的模拟实现
3.1 仿函数的概念
仿函数又称为函数对象重载了operator()的类类的对象可以向函数一样使用。
operator() 的特点参数个数和返回值是根据需求定的很灵活。
3.2 仿函数的实现
3.2.1 判断小于的仿函数
下面是我们的判断小于的仿函数的代码
//判断小于的仿函数
templateclass T
class myless
{
public:bool operator() (T x, T y){return x y;}
};我们定义了一个重载了operator() 的类类里面就只有一个重载函数。我们可以通过这种方式来模拟出一个函数。
3.2.2 判断大于的仿函数
下面是我们判断大于的仿函数的代码
//判断大于的仿函数
templateclass T
class mygreater
{
public:bool operator() (T x, T y){return x y;}
};这是我们判断大于的仿函数和判断小于的仿函数的原理相同也是使用了一个类模版然后再里面重载了一个operator() 函数用来模拟函数的效果。
3.3 构造以及建堆调整操作
3.3.1 构造函数
这里的构造函数我们先实现默认的无参构造
//无参构造
priority_queue():c(), comp()
{}将类里面的两个成员变量给一个空值 c是底层容器comp是用来比较的仿函数。实现建堆的调整函数后我们在来实现我们的迭代器构造函数。
3.3.2 向上调整建堆
下面是我们进行维持优先级队列的顺序的函数之一向上调整算法
//向上调整建堆
void Adjust_up(int child)
{int parent (child - 1) / 2;while (child 0){//if (c[parent] c[child])if(comp(c[parent], c[child])){swap(c[parent], c[child]);}child parent;parent (child - 1) / 2;}
}我们首先要知道用数组模拟堆也就是优先级队列它的子节点和父亲节点的下标之间的关系在向上建堆操作中我们是从下往上的我们需要知道parent和child之间的关系它们之间的关系就是 parent (child - 1) / 2 , 这里的比较我们可以使用仿函数来比较也可以直接实用大于和小于号比较但是建议使用仿函数因为仿函数的通用性高 当我们的父节点小于我们的子节点时我们就将他们交换位置然后将父节点的位置给到子节点然后重新计算父节点相当于是更新子节点和父节点。
3.3.3 向下调整建堆
下面是我们的向下调整算法
//向下调整建堆
void Adjust_down(int parent)
{int child parent * 2 1;if (child 1 c.size() c[child] c[child 1]){child;}while (child c.size()){//if (c[parent] c[child])if(comp(c[parent], c[child])){swap(c[parent], c[child]);}parent child;child parent * 2 1;}
}向下建堆的效率要比向上调整建堆的效率要高很多 在我们的迭代器区间构造和我们的pop函数中可以使用我们的向下调整算法来维持优先队列的结构。原理和向上调整建堆基本相同向下调整算法是传入parent的值然后计算出child的值child和parent的关系式是child parent * 2 1 然后我们选出最大的左右子节点中较大的那个子节点对parent和child进行比较如果parent的值小于child的值的话就将它们调换位置然后将child的下标给给parent然后再计算child的下标相当于更新位置。
3.3.4 使用迭代器区间进行构造
下面是我们的实例代码 //迭代器区间构造template class InputIteratorpriority_queue(InputIterator first, InputIterator last):c(),comp(){while (first ! last){c.push_back(*first);first;}for (int i (c.size() - 1 - 1) / 2; i 0; i--){Adjust_down(i);}}这里我们直接将这个迭代器区间中的值通过迭代器遍历逐个放进我们的底层容器中即可然后通过我们的向下调整算法进行建堆。
3.4 priority_queue中的容量以及访问访问修改操作
3.4.1 容量相关的接口
我们容量相关的接口有size和emptysize的作用是返回有效数据的个数empty的作用是判断队列中是否为空。
下面来看我们的size接口
//返回有效数据个数
size_t size() const
{return c.size();
}对于我们的size接口就直接返回我们底层容器的size接口的值即可。
再来看下我们的empty接口 //判断优先队列里面是否为空bool empty() const{return c.empty();}与size接口同理empty接口也是直接返回我们的底层容器的接口即可。
3.4.2 访问和修改
关于访问和修改操作的接口有top, push, pop
下面依次来看这些接口:
top: //返回队头元素T top() {return c[0];}const T top() const{return c[0];}top 接口的作用是返回我们的队头元素我们的底层容器是动态数组vector我们就直接返回数组的第一个元素即可。
push
//入队操作
//尾插入队执行向上调整操作
void push(const T x)
{c.push_back(x);Adjust_up(c.size() - 1);
}对于入队操作我们直接尾插进数组即可尾插之后执行向上调整操作。
pop
//出队操作
//先交换最后一个元素和第一个元素的位置
//尾删出队执行向下调整操作
void pop()
{swap(c[0], c[size() - 1]);c.pop_back();Adjust_down(0);
}对于我们pop接口的作用时将堆顶元素给pop出去我们将堆顶元素和数组最后一个元素进行交换位置然后进行尾删最后执行向下调整操作维持堆的结构即可。 这就是这篇文章的全部内容了希望大家能从以上内容中对优先级队列有一定的理解。 对于入队操作我们直接尾插进数组即可尾插之后执行向上调整操作。popC
//出队操作
//先交换最后一个元素和第一个元素的位置
//尾删出队执行向下调整操作
void pop()
{swap(c[0], c[size() - 1]);c.pop_back();Adjust_down(0);
}对于我们pop接口的作用时将堆顶元素给pop出去我们将堆顶元素和数组最后一个元素进行交换位置然后进行尾删最后执行向下调整操作维持堆的结构即可。 这就是这篇文章的全部内容了希望大家能从以上内容中对优先级队列有一定的理解。
