常见的微网站平台有哪些,沈阳网站制作全网性,做电影网站用什么空间,反诈app开发公司✨✨ 欢迎大家来到小伞的大讲堂✨✨ #x1f388;#x1f388;养成好习惯#xff0c;先赞后看哦~#x1f388;#x1f388; 所属专栏#xff1a;C学习 小伞的主页#xff1a;xiaosan_blog 1. priority_queue的介绍和使用
priority_queue文档介绍 优先级队列的实现的关键… ✨✨ 欢迎大家来到小伞的大讲堂✨✨ 养成好习惯先赞后看哦~ 所属专栏C学习 小伞的主页xiaosan_blog 1. priority_queue的介绍和使用
priority_queue文档介绍 优先级队列的实现的关键取决于数据结构的堆如果忘记了就回去看看吧 【数据结构】详解堆 1. 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。 3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。 4. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素 5. 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue 类实例化指定容器类则使用vector。 6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。 1.1 priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意默认情况下priority_queue是大堆。
函数声明接口说明priority_queue()/priority_queue(first,last)构造一个空的优先级队列empty( )检测优先级队列是否为空是返回true否返回falsetop( )返回优先级队列的最大值(最小值)即堆顶元素push(x)在优先级队列中插入xpop()删除优先级队列中的最大(最小)元素即堆顶元素
注意:
1.在默认情况下priority_queue默认为大堆 #includeiostream
#include vector
#include queueusing namespace std;
void TestPriorityQueue()
{vectorint v{ 3,2,7,6,0,4,1,9,8,5 };priority_queueint q1(v.begin(), v.end());while (!q1.empty()){cout q1.top() ;q1.pop();}cout endl;priority_queueint, vectorint, greaterint q2(v.begin(), v.end());while (!q2.empty()){cout q2.top() ;q2.pop();}
}
int main()
{TestPriorityQueue();return 0;
} 2. 如果在priority_queue中放自定义类型的数据用户需要在自定义类型中提供 或者 的重载 class Date
{
public :
Date(int year 1900, int month 1, int day 1): _year(year), _month(month), _day(day)
{}
bool operator(const Date d)const
{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);
}
bool operator(const Date d)const
{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);
}
friend ostream operator(ostream _cout, const Date d)
{_cout d._year - d._month - d._day;return _cout;
}
private:int _year;int _month;int _day;
};void TestPriorityQueue()
{// 大堆需要用户在自定义类型中提供的重载priority_queueDate q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout q1.top() endl;// 如果要创建小堆需要用户提供的重载priority_queueDate, vectorDate, greaterDate q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout q2.top() endl;
} 3.可以使用仿函数进行大堆小堆的排序 仿函数实质是一个类是一个什么类呢 是一种重载了函数调用运算符operator()的类或结构体它可以使一个类的使用看上去像一个函数。仿函数可以接受参数并返回值可以用于STL算法中的函数对象参数也可以用于函数指针的替代。 仿函数的主要作用包括 ①提供一种灵活的方式来实现函数对象可以根据实际需求定制自己的函数对象比如排序、查找等算法。 ②封装函数参数使得算法可以接受不同类型的参数增加算法的通用性。③保存状态在多次调用之间保持状态避免每次调用时都需要重新计算。 ④替代函数指针因为函数指针只能指向全局函数或静态成员函数而仿函数可以指向任意类型的函数包括成员函数和非静态成员函数。 templateclass T
class Less
{
public:bool operator()(const T x,const T y){return x y;}
};templateclass T
class Greater
{
public:bool operator()(const T x, const T y){return x y;}
};templateclass T,class Compare
void BubbleSort(vectorT v,Compare com)
{int i 0, j 0;for (i 0; i v.size(); i){int flag 0;for (j 1; j v.size() - i; j){if (com(v[j], v[j - 1])){swap(v[j-1],v[j]);flag 1;}}if (flag 0){break;}}
}int main()
{vectorint v;v.push_back(5);v.push_back(7);v.push_back(8);v.push_back(1);v.push_back(0);v.push_back(2);v.push_back(6);v.push_back(9);BubbleSort(v, Lessint());//此处是匿名对象传参的也可以先创建Less less;auto it1 v.begin();while (it1 ! v.end()){cout *it1 ;it1;}return 0;
} 1.2 priority_queue的模拟实现 #define _CRT_SECURE_NO_WARNINGS 1 #includeiostream #includevector #includefunctional using namespace std; //仿函数 template class T class Less { public: bool operator ()(const T x, const T y) { return x y; } }; template class T class Greater { public: bool operator ()(const T x, const T y) { return x y; } }; namespace sui { template class T, class Container vectorT, class Compare class GreaterT class priority_queue { public: bool empty() const { return c.empty(); } size_t size() const { return c.size(); } T top() const { return c[0]; } void AdjustUp(int child) { Compare com; int parent (child - 1) / 2; while (child 0) { if (com(c[parent], c[child])) { swap(c[parent], c[child]); child parent; parent (child - 1) / 2; } else { break; } } } void push(const T x) { c.push_back(x); AdjustUp(c.size() - 1); } void AdjustDown(int parent) { size_t child parent * 2 1;//假设左孩子小 //建大堆 Compare com; while (child c.size()) { //如果右孩子大child为右孩子 if (child 1 c.size() com(c[child], c[child 1])) { child; } //如果父亲的值小于孩子 if (com(c[parent], c[child])) { swap(c[parent], c[child]); parent child; child parent * 2 1; } else { break; } } } void pop() { swap(c[0], c[c.size() - 1]); c.pop_back(); AdjustDown(0); } private: Container c; }; };
