priority_queue的适用和模拟实现

priority_queuq的介绍1.优先级队列:priority queue是一个容器适配器的类型他被特别设计乘第一个元素总是所有元素中最大的根据一些严格弱排序的标准(这个好像是调整顺序的时候会让数据相对性改变)这个容器非常类似于堆他的元素在任何的时间都能被插入并且只能检索最大堆元素优先级队列被实现成容器适配器容器适配器即将特定容器类封装为其底层容器类并且提供一些特殊的接口让访问他的元素。数据从尾部bakc删除其称为优先级队列的顶部底层的容器可以是任何标准的容器类模板或者一些其他被特定设计的容器类容器可以通过随机迭代器访问并且支持下面的操作下面还有一堆不想翻译了自己去看把反正意思就是跟堆一毛一样帅哥靓女们看这里这里很重要2.接口其实也没啥看的这玩意就跟用堆实现一些接口一样还是很简单的特别注意他的构造函数3.仿函数仿函数这里比较有意思仿函数是重载了()的一个类---这里听着名字以为是函数我去太坑了但其实他是类priority_queue这个构造用仿函数的目的啊是为了控制比较如果你想写一个建小堆的如果我们不知道仿函数的时候我们就得要搞两个类出来但是但是我们有仿函数就直接作为这个类的成员我去太方便了说实话直接控制比较的大小(我们比较的时候也用仿函数重载的()去比较)这样我们就能控制参数来控制大小堆了后面也有很多这东西的讲解----还是比较实用的4.else如果这里存储自定义类型的变量---就必须要确保自定义类型重载了比较相关的运算符#define _CRT_SECURE_NO_WARNINGS 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; }看到没我随便ctrlc ctrlv就从小白变成了编程高手啊啊啊学的太慢好难受有没有什么芯片直接插我脑门里直接学习大量编程让我直接精通c 啊哈哈哈priority_queue的模拟实现同志们加油我去ctrl c ctrl v了namespace w { templateclass T class greater { public: bool operator()(const T left, const T right) { return left right; } }; templateclass T class less { public: bool operator()(const T left, const T right) { return left right; } }; template class T, class Container vectorT, class Compare lessT class priority_queue { public: priority_queue() :c() {} template class InputIterator priority_queue(InputIterator first, InputIterator last) :c(first,last) { int count c.size(); int root (count - 2) / 2; for (; root 0; --root) { AdjustDown(root); } } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } const T top() const { return c.front(); } void push(const T x) { c.push_back(x); AdjustUp(c.size() - 1); } void pop() { if (empty()) { return; } std::swap(c.front(), c.back()); c.pop_back(); AdjustDown(0); } private: void AdjustUp(int child) { while (child) { int parent ((child - 1) 1); if (comp(c[parent], c[child])) { std::swap(c[parent], c[child]); child parent; } else break; } } void AdjustDown(int parent) { int child parent * 2 1; while (child c.size()) { if (child 1 c.size() comp(c[child], c[child 1])) { child 1; } if (comp(c[parent], c[child])) { std::swap(c[parent], c[child]); parent child; child parent * 2 1; } else break; } } Container c; Compare comp; }; } int main() { vectorint v { 4,8,1,6,2,9,5 }; w::priority_queueint pq(v.begin(), v.end()); while (!pq.empty()) { cout pq.top() ; pq.pop(); }coutendl; return 0; }还是简单说一说吧这里我觉得有三个地方需要自己理解一下1.就是AdjustUp这个函数呢根堆的向上调整是一样的我们把数组当成一颗树我们需要传的是child结点的下标--我们看去跟他的parent(下标就是(child-1)/2),去比较一下。如果child比parent大的时候就往上调整。刚开始学堆的时候一位这逻辑很难现在看看也就那样2.AdjustDown这函数和向上调整唯一的区别是传的参数要是父亲向下调整的时候就需要判断两个孩子谁大谁小让两个孩子更大的(如果都大于parent)换上去要关注这个避免数组越界3.就是迭代器构造这里的逻辑呢就是要找到最后一个孩子的父亲结点让后向下调整调整完之后去找上一个父亲不断走向下调整最后走到头的时候这个数组也就符合堆的规则了。话说这个jojo飙马野郎根本不够看啊快点更新