STL讲解——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来自动完成此操作。

实现方法

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
归根结底：
我们就是用vector作为适配器实现一个大堆。
使用堆算法就是进行parent和child的比较，不满足条件就交换parent和child。

重要的接口：

堆的特性：pop的是堆顶，不是堆尾

代码讲解

首先声明

默认的堆是一个大堆，但是我今天设计的是一个默认小堆的函数，而且我的lesser是小堆比较，这是因为和单词进行对比更容易上手理解。（记住与实际相反就好了，实际中less是大堆，greater是小堆）

#pragma once
#include<iostream>
#include<vector>
#include<functional>
using namespace std;
namespace tom
{template <class T, class Container = vector<T>, class Compare = lesser<T> >class priority_queue{public:priority_queue():c(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last):c(first,last){int sz = c.size();int root = (sz-1)/ 2;//parent=(child-1)/2 ; child=(parent+1)*2;while (root >= 0){AdjustDown(root);root--;}}bool empty() const{return c.empty();}size_t size() const{return c.size();}const T& top() const{if (!c.empty())return c[0];//c.front();elsecout << "空堆，请插入元素！" << endl;}void push(const T& x){c.push_back(x);AdjustUP(c.size() - 1);}void pop()//堆一般都是pop头的，pop尾没啥意思{if (!empty()){swap(c.front(), c.back());//swap(c[0], c[c.size()-1]);c.pop_back();AdjustDown(0);}}private:Container c;Compare comp;};};

先构建一个命名空间这是一个良好的习惯
设计一个类priority_queue剩下的就交给vector了，因为stl会把你给的数据直接初始化的；
但是要进行堆的排序还是需要向下调整的（AdjustDown）于是乎要设计一个函数AdjustDown；
并且删除数据或者插入数据都需要调整，于是乎在设计一个函数AdjustUp进行向上调整；

适配器

	template <class T, class Container = vector<T>, class Compare = lesser<T> >class priority_queue{...}

这里的 class Container 就是一个适配器模板，c++不仅给了参数模板，还给了适配器模板，太逆天了！！！
这个适配器模板可以根据你的需求进行更改，比如改为deque，但是我们给了缺省值（默认就用vector适配器了）。

需要设计一个迭代器赋值构造其实是复用了vector的构造函数。

向上、下调整

// 向上调整void AdjustUP(int child){int parent = ((child - 1) >> 1);while (child){if (c[child]<c[parent]){swap(c[child], c[parent]);child = parent;parent = ((child - 1) >> 1);}elsereturn;}}// 向下调整void AdjustDown(int parent){int child = (parent)*2+1;//parent = child / 2 - 1;while (child < c.size()){if ((child + 1) < c.size() &&c[child + 1]<c[child]){child++;}if (c[child]<c[parent]){swap(c[child], c[parent]);parent = child;child = (parent) * 2 + 1;}elsereturn;    }  }

仿函数的构造

并不想再写一个大堆出来，因为会有代码冗余，于是乎想到了构造一个仿函数，来帮我实现大于小于的函数判断。

template<class T>struct lesser{bool operator()(const T& x, const T& y){return x < y;//我设计的与stl库设计的不一样，我把less设计成了小堆}};template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;//我设计的与stl库设计的不一样，我把great设计成了大堆}};template <class T, class Container = vector<T>, class Compare = lesser<T> >class priority_queue{...}

而且我在前面也留了扣子，在实现类模板的时候已经预留了compare函数了。

	template <class T, class Container = vector<T>, class Compare = lesser<T> >class priority_queue{...}

其他细节
其他的细节基本没什么重点了。

代码和测试代码贴出

#pragma once
#include<iostream>
#include<vector>
#include<functional>
using namespace std;
namespace tom
{template<class T>struct lesser{bool operator()(const T& x, const T& y){return x < y;//我设计的与stl库设计的不一样，我把less设计成了小堆}};template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;//我设计的与stl库设计的不一样，我把great设计成了大堆}};template <class T, class Container = vector<T>, class Compare = lesser<T> >class priority_queue{public:priority_queue():c(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last):c(first,last){int sz = c.size();int root = (sz-1)/ 2;//parent=(child-1)/2 ; child=(parent+1)*2;while (root >= 0){AdjustDown(root);root--;}}bool empty() const{return c.empty();}size_t size() const{return c.size();}const T& top() const{if (!c.empty())return c[0];//c.front();elsecout << "空堆，请插入元素！" << endl;}void push(const T& x){c.push_back(x);AdjustUP(c.size() - 1);}void pop()//堆一般都是pop头的，pop尾没啥意思{if (!empty()){swap(c.front(), c.back());//swap(c[0], c[c.size()-1]);c.pop_back();AdjustDown(0);}}// 向上调整void AdjustUP(int child){int parent = ((child - 1) >> 1);while (child){if (Compare()(c[child] , c[parent]))//if (c[child]<c[parent]){swap(c[child], c[parent]);child = parent;parent = ((child - 1) >> 1);}elsereturn;}}// 向下调整void AdjustDown(int parent){int child = (parent)*2+1;//parent = child / 2 - 1;while (child < c.size()){if ((child + 1) < c.size() &&Compare()( c[child + 1],c[child]))//if ((child + 1) < c.size() &&c[child + 1]<c[child]){child++;}if (Compare()(c[child] , c[parent]))//if (c[child]<c[parent]){swap(c[child], c[parent]);parent = child;child = (parent) * 2 + 1;}elsereturn;    }  }private:Container c;Compare comp;};};

实现一个大堆

实现一个默认的小堆

电影影评