怎么查询一个网站有没有做竞价,网站更换域名备案吗,新乡市做网站的公司,沈阳建站多少钱STL之priority_queue的使用及其模拟实现仿函数 1.priority_queue的介绍2.priority_queue的使用3.priority_queue的模拟实现3.1解析细节3.2仿函数3.3具体实现 1.priority_queue的介绍
优先队列是一种容器适配器#xff0c;根据严格的弱排序标准#xff0c;它的第一个元素总是… STL之priority_queue的使用及其模拟实现仿函数 1.priority_queue的介绍2.priority_queue的使用3.priority_queue的模拟实现3.1解析细节3.2仿函数3.3具体实现 1.priority_queue的介绍
优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元 素)。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问并支持以下操作 empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指 定容器类则使用vector。需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。
2.priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成 堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意 默认情况下priority_queue是大堆。
函数声明接口说明priority_queue()/priority_queue(first,last)构造一个空的优先级队列empty( )检测优先级队列是否为空是返回true否则返回falsetop( )返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素
【注意】
默认情况下priority_queue是大堆如果在priority_queue中放自定义类型的数据用户需要在自定义类型中提供 或者 的重载。
#include vector
#include queue
#include functional // greater算法的头文件
void TestPriorityQueue()
{// 默认情况下创建的是大堆其底层按照小于号比较vectorint v{ 3,2,7,6,0,4,1,9,8,5 };priority_queueint q1;for (auto e : v)q1.push(e);cout q1.top() endl;// 如果要创建小堆将第三个模板参数换成greater比较方式priority_queueint, vectorint, greaterint q2(v.begin(), v.end());cout q2.top() endl;
}3.priority_queue的模拟实现
3.1解析细节
回顾一下我们之前学习二叉树的时候当时我们实现了向上调整和向下调整这两个都可以实现堆排序。当我们要插入一个数据的时候是头插还是尾插呢因为priority_queue的底层是堆也就是二叉树但是这个二叉树的物理结构是数组逻辑上是二叉树所以如果我们选择头插的话就会打乱原来的二叉树结构导致父子变兄弟兄弟变叔侄。所以这里我们要选择尾插同时还要保持priority_queue的特性在每次插入一个数据的时候还用进行向上调整。但我们要删除一个数据的时候因为priority_queue是个优先级队列肯定是删除最大/最小的也就是堆顶的数据也就是头删那我们可以直接进行头删吗显然是不能的因为这样做同样也会导致原来的二叉树结构从而导致父子变兄弟兄弟变叔侄。所以这里的办法是讲头上的数据与尾上的数据进行交换后在进行尾删最后在进行向上调整。以上是我们回顾数据结构二叉树阶段学习的知识点如果还有不懂的地方可以翻阅前期二叉树讲解部分在哪里有系统的讲解。
3.2仿函数
在我们实现向上调整/向下调整的时候我们只能进行单一的或者的比较也就是实现一种方案但是如果我们想实现升序和降序的时候就要写两份并且分开调用这个办法明显比较挫。我们在C语言阶段通常用到的是回调函数但是这个办法的缺点就是调用的时候比较麻烦实现起来也比较麻烦。
void adjust_up(int child)
{int faster (child - 1) / 2;while (child 0){if (_con[child] _con[faster]){std::swap(_con[child], _con[faster]);child faster;faster (child - 1) / 2;}else{break;}}
}void adjust_down(int faster)
{int child faster * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child 1] _con[child]){child;}if (_con[child]_con[faster]){std::swap(_con[faster], _con[child]);faster child;child faster * 2 1; }else{break;}}
}所以在C中引入了仿函数的概念 所谓仿函数简单点说就是一个重载了()的一个函数。 使用起来跟调用函数很像但又不是函数所以叫做仿函数
class fun
{
public:bool operator()(in x, int y){return x y;}
};fun f
cout f(1, 2) endl;//这个样子看起来很像是一个函数调用实际上是f.operator()(1, 2)这样调用的。3.3具体实现
#pragma once
#include vector
namespace qfw
{templateclass Tclass less{public:bool operator()(T x, T y){return x y;}};templateclass Tclass greater{public:bool operator()(T x, T y){return x y;}};template class T, class Container vectorT, class Comper lessTclass priority_queue{public:void adjust_up(int child){int faster (child - 1) / 2;while (child 0){if (_cmp(_con[child] , _con[faster])){std::swap(_con[child], _con[faster]);child faster;faster (child - 1) / 2;}else{break;}}}void adjust_down(int faster){int child faster * 2 1;while (child _con.size()){if (child 1 _con.size() _cmp(_con[child 1] , _con[child])){child;}if (_cmp(_con[child],_con[faster])){std::swap(_con[faster], _con[child]);faster child;child faster * 2 1; }else{break;}}}priority_queue()//这里要有个空的默认构造原因是下面构造了一个priority_queue(InputIterator first, InputIterator last)有参构造//但是当实例化对象的时候没有传参数的时候据选哟调用默认构造但是类的特点就是如果定义了有参构造就不会//使用系统给的默认构造所以这里要自己写一个默认构造。{}template class InputIteratorpriority_queue(InputIterator first, InputIterator last){while (first ! last){push(*first);first;}}void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;Comper _cmp;};
}
