STL之优先级队列（堆）的模拟实现与仿函数(8千字长文详解！)

STL之优先级队列（堆）的模拟实现与仿函数

优先级队列的概念

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来自动完成此操作
   list不支持随机访问！所以不能当做其标准容器类！
   

priority_queue的接口介绍

pop：删除堆顶的数据

top：取出堆顶的数据

push：向堆插入数据

size：返回堆里面的元素个数

empty：判断堆是否为空

swap：交换两个堆

优先级队列的构造函数

可以使用迭代器进行初始化！

但是这个迭代器是一个随机迭代器！

//简单使用
#pragma once
#include <queue>
#include<iostream>
#include <functional>//less和greater的头文件
using namespace std;
int main()
{//大堆priority_queue <int> pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);while (!pq.empty()){cout << pq.top() << ' ';pq.pop();}cout << endl;//小堆priority_queue <int,vector<int>,greater<int>> pq1;pq1.push(3);pq1.push(1);pq1.push(2);pq1.push(5);while (!pq1.empty()){cout << pq1.top() << ' ';pq1.pop();}cout << endl;return 0;
} 

priority_queue模拟实现

容器适配器是不需要迭代器的！如果有了迭代器是不能保证最大/最小的先出！

类成员

namespace MySTL
{template<class T,class Container = std::vector<T>>class priority_queue{private:Container _con;};
}

构造函数

namespace MySTL
{template<class T,class Container = std::vector<T>>class priority_queue{public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator first,InputIterator last):_con(first,last)//直接调用vector的构造{//此时还不是堆！//向下调整建堆！for (int i = (_con.size() - 2) / 2; i >= 0; i++){adjust_down(i);}}private:Container _con;};
}

向下调整算法——正常实现

namespace MySTL
{template<class T,class Container = std::vector<T>>class priority_queue{private:void adjust_down(size_t parent){size_t  child = parent*2 +1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1])child++;if (_con[parent] < _con[child])//建大堆{std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;//没有更大的了，退出}}}private:Container _con;};
}

向下调整算法的核心将父节点和自己的两个子节点对比，找到其中一个最大（大堆）的或者最小（小堆）的子节点！然后比较，如果是建大堆，若父节点比子节点还要小，那么交换！如果是建小堆，若父节点比子节点还要大，那么交换！，直到父节点比最大子节点还要大（大堆），或者是比最小的子节点还要小（小堆）则跳出循环！或者直接调整到最后一个节点！

push

namespace MySTL
{template<class T,class Container = std::vector<T>>class priority_queue{public:void push(const T& value){//插入后要保持堆的结构！//要进行向上调整！_con.push_back(value);adjust_up(_con.size()-1);}private:Container _con;};
}

向上调整——正常实现

namespace MySTL
{template<class T,class Container = std::vector<T>>class priority_queue{private:void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent])//建大堆！{std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}private:Container _con;};
}
//这里如果使用parent>0，那么因为子节点还在下一个位置，则无法调整根节点
//如果是parent>=0 因为parent =（0-1）/2 仍然为0，则就会出现死循环！

向上调整，就是将现在子节点和父节点对比一下！然后如果是建大堆，若子节点大于父节点那么进行交换！

如果是建小堆，若子节点小于父节点，那么也交换！

结束条件：直到根节点是孩子，或者建大堆的时候，孩子比父亲小（建小堆的时候，孩子比父亲大！）

向上调整算最好使用孩子作为循环借宿的条件！

pop

namespace MySTL
{template<class T,class Container = std::vector<T>>class priority_queue{public:void pop(){//交换std::swap(_con[0], _con[_con.size()-1]);//删除最后一个元素_con.pop_back();//向下调整算法！adjust_down(0);}private:void adjust_down(size_t parent){size_t  child = parent*2 +1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1])child++;if (_con[parent] < _con[child])//建大堆{std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;//没有更大的了，退出}}}private:Container _con;};
}

int main()
{MySTL::priority_queue <int> pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);while (!pq.empty()){cout << pq.top() << ' ';pq.pop();}cout << endl;return 0;
}

仿函数/函数对象

仿函数的概念

首先仿函数究竟是什么呢？——是一个类！仿函数的类型对象我们叫做函数对象！

template<class T>
struct less
{bool operator()(const T& x,const T& y){return x < y;}
};
template<class T>
struct greater
{bool operator()(const T& x,const T& y){return x > y;}
};

仿函数的要求是要重载()，()这也是一个运算符！例如像是我们去调用pq1.pop()的函数，后面的()就是一个函数调用符！

int main()
{less<int> lessFunc;lessFunc(0, 1);return 0;
}

如果不看上面的类的定义，单看后面的lessFunc(0,1)，这就是一个函数调用！函数名是lessFunc——但是现在实际上是一个类！这就是为什么这个叫做仿函数！这个对象叫做函数对象！指的就是这个对象能像函数一样被使用！

但是这个其实也是一个函数调用

lessFunc(0, 1);//将这个转换为一个运算符重载！
lessFunc.operator()(0, 1);//等价于上面上面的！

仿函数的作用

那么仿函数究竟有什么作用呢？看起来和一般的函数区别？而且还多了一个封装！看起来更加的麻烦了！

我们可以举一个例子来看

//这是C语言的一个冒泡排序！
void BubbleSort(int* a, int size,bool(*cmp)(int,int))
{for (int i = 0; i < size; i++){int exchange = 0;for(int j = 1.;j<size-i;j++){if (cmp(a[j-1],a[j])){std::swap(a[j - 1], a[j]);exchange = 1;}}if (!exchange){break;}}
}

我们可以 看到在C语言中，如果我们想要解决升序降序的问题，我们就要传一个函数指针过来！——如果不用函数指针那么我们就只能重新写一个函数了！

那么在C++中的类里面我们是否也可以传一个函数指针呢？可以！但是这样子不好看！C++的设计都是在尽量的不去使用指针！

所以仿函数这时候就派上用场了！

template <class T,class Compare>
void BubbleSort(T* a, int size,Compare com)//因为Compare其实是一个类所以要显示实例化！而不是模板函数一样是推演实例化！所以要多加一个参数
{for (int i = 0; i < size; i++){int exchange = 0;for(int j = 1.;j<size-i;j++){//if (a[j] < a[j - 1])if (com(a[j], a[j - 1])){std::swap(a[j - 1], a[j]);exchange = 1;}}if (!exchange){break;}}
}int main()
{less<int> lessFunc;int a[] = { 1,5,7,8,94,24,5,3,56,7 ,90 };BubbleSort(a, sizeof(a) / sizeof(a[0]), lessFunc);//升序排序//BubbleSort(a, sizeof(a) / sizeof(a[0]), less<int>());//怎么写也是可以的！因为是一个匿名对象！如果这个函数对象是要使用一次的话！可以直接使用！匿名对象！for (auto& e : a){std::cout << e << " ";}std::cout << std::endl;greater<int> greaterFunc;int b[] = { 1,5,7,8,94,24,5,3,56,7 ,90 };BubbleSort(b, sizeof(b) / sizeof(b[0]), greaterFunc);//降序排序！//BubbleSort(b, sizeof(b) / sizeof(b[0]), greater<int>());for (auto& e : b){std::cout << e << " ";}return 0;
}

less和greater就是我们刚刚写的仿函数！

从我们实现代码的角度来说，这是一个泛型，是一个逻辑泛型——即com是一个逻辑！如果需要升序就传一个lessFunc，如果要降序就传一个greaterFunc

类型泛型就是不限类型！逻辑泛型就是不限逻辑！

仿函数一般都是传值，因为仿函数的拷贝代价很小！仿函数里面没有成员变量！所以只有一个字节作为标记位！

但是如果想要传引用也行！

void BubbleSort(T* a, int size,const Compare& com)//也是可以传引用的！但是要加上const否则就无法接收匿名对象！因为匿名对象具有常性
{for (int i = 0; i < size; i++){int exchange = 0;for(int j = 1.;j<size-i;j++){//if (a[j] < a[j - 1])if (com(a[j], a[j - 1]))//因为是const对象调用所以仿函数内部都要加上const{std::swap(a[j - 1], a[j]);exchange = 1;}}if (!exchange){break;}}
}

template<class T>
struct less
{bool operator()(const T& x,const T& y)const//加上const让const对象能够调用！{return x < y;}
};
template<class T>
struct greater
{bool operator()(const T& x,const T& y)const{return x > y;}
};

我们也可以看到传引用其实很麻烦！所以没有什么必要！

使用仿函数来实现优先级队列的逻辑判断

我们上面的优先级队列要么只能是大堆！要么只能是小堆！不够泛用！原因就是因为我们的逻辑是写死的！但是学会了仿函数之后！我们也可以实现逻辑泛型了！

新增模板参数

	template<class T, class Container = std::vector<T>,class Compare = less<T>> class priority_queue{public:// functionsprivate:Container _con;};
}

加上第三个模板参数仿函数！

使用仿函数实现泛型的向下调整算法与向上调整算法

namespace MySTL
{template<class T>struct less{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = std::vector<T>,class Compare = less<T>>class priority_queue{public://functionsprivate:void adjust_up(size_t child){size_t parent = (child - 1) / 2;Compare com;while (child > 0){//if (_con[child] > _con[parent])//建大堆！//if (_con[parent] < _con[child])//建大堆！if(com(_con[parent], _con[child]))//我们要与库保持一致要小于实现大堆！那么就要parent在前，就是与上面的逻辑一样{std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t  child = parent*2 +1;Compare com;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child] <  _con[child + 1]))if (child + 1 < _con.size() && com(_con[child], _con[child + 1])))//我们要与库保持一致要小于实现大堆！那么就要child在前child++;//if (_con[parent] < _con[child])//建大堆if(com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;//没有更大的了，退出}}}private:Container _con;};
}

测试用例

int main()
{//大堆MySTL::priority_queue <int> pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);while (!pq.empty()){cout << pq.top() << ' ';pq.pop();}cout << endl;//小堆MySTL::priority_queue <int, vector<int>, greater<int>> pq1;pq1.push(3);pq1.push(1);pq1.push(2);pq1.push(5);while (!pq1.empty()){cout << pq1.top() << ' ';pq1.pop();}cout << endl;return 0;
}

优先级队列模拟——最终版代码

namespace MySTL
{template<class T>struct less{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = std::vector<T>,class Compare = less<T>>class priority_queue{public:priority_queue()//无参构造{}template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last)//直接调用vector的构造{//此时还不是堆！//向下调整建堆！for (int i = (_con.size() - 2) / 2; i >= 0; i++){adjust_down(i);}}void push(const T& value){_con.push_back(value);adjust_up(_con.size()-1);}void pop(){//交换std::swap(_con[0], _con[_con.size()-1]);//删除最后一个元素_con.pop_back();//向下调整算法！adjust_down(0);}const T& top() const{return _con[0];}bool empty() const{return _con.empty();}size_t size()const{return _con.size();}private:void adjust_up(size_t child){size_t parent = (child - 1) / 2;Compare com;while (child > 0){//if (_con[child] > _con[parent])//建大堆！//if (_con[parent] < _con[child])//建大堆！if(com(_con[parent], _con[child]))//我们要与库保持一致要小于实现大堆！那么就要parent在前{std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t  child = parent*2 +1;Compare com;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child] <  _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))//我们要与库保持一致要小于实现大堆！那么就要child在前child++;//if (_con[parent] < _con[child])//建大堆if(com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;//没有更大的了，退出}}}private:Container _con;};
}

仿函数的应用

要知道我们优先级队列的类型可以不只是库里面的类型！还可以是自定义类型！

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;
};

如果一个自定义类型是支持比较大小的！那么仿函数greater和less都是可以使用的！里面的>与< 本质也是调用的是Date类的运算符重载！

void testpriorityqueue()
{priority_queue<Date> q1;//默认是大堆q1.push(Date(2010, 1, 1));q1.push(Date(2010, 1, 2));q1.push(Date(2010, 1, 3));cout << q1.top() << endl;priority_queue<Date,vector<Date>,greater<Date>> q2;//默认是大堆q2.push(Date(2010, 1, 1));q2.push(Date(2010, 1, 2));q2.push(Date(2010, 1, 3));cout << q2.top() << endl;}
int main()
{testpriorityqueue();return 0;
}

现在如果我们传入的是这个自定义类型的指针呢？

void testpriorityqueue()
{//大堆priority_queue<Date*> q3;q3.push(new Date(2010, 1, 1));q3.push(new Date(2010, 1, 2));q3.push(new Date(2010, 1, 3)); cout << *q3.top() << endl;//小堆priority_queue<Date*,vector<Date*>,greater<Date*>> q4;/q4.push(new Date(2010, 1, 1));q4.push(new Date(2010, 1, 2));q4.push(new Date(2010, 1, 3));cout << *q4.top() << endl;
}
int main()
{testpriorityqueue();return 0;
}

我们发现这时候堆的比较好像就失效了!这是为什么呢？因为我们传过去的是date类的地址！此时我们传入的仿函数是用地址的大小去比较的！谁地址谁大！谁地址小谁小！

因为每次地址是随机的！所以每次的结果都会在改变！

那么现在的结果已经不符合我们预期了！怎么办？

我们就可以重新写一个关Date* 的仿函数！

struct PDateCompare_greater
{bool operator()(const Date* x,const Date* y){return *x > *y;}
};
struct PDateCompare_less
{bool operator()(const Date* x,const Date* y){return *x < *y;}
};
void testpriorityqueue()
{//大堆//priority_queue<Date*> q3;priority_queue<Date*,vector<Date*>,PDateCompare_less> q3;q3.push(new Date(2010, 1, 1));q3.push(new Date(2010, 1, 2));q3.push(new Date(2010, 1, 3)); cout << *q3.top() << endl;//小堆priority_queue<Date*,vector<Date*>,PDateCompare_greater> q4;q4.push(new Date(2010, 1, 1));q4.push(new Date(2010, 1, 2));q4.push(new Date(2010, 1, 3));cout << *q4.top() << endl;
}
int main()
{testpriorityqueue();return 0;
}

如果比较的方式不是我们想要的！那么我们就可以通过自己写一个仿函数来完成，甚至如果自定义类不支持> 与< 重载我们也可以写一个仿函数来完成大小的比较！

STL中实现的比较

STL中的建堆算法

STL中的建堆算法是在algorithm这个头文件中！

• push_heap将一个元素插入堆中
• pop_heap将一个元素从堆中移除
• make_heap 从一个范围内的元素中创建一个堆
• sort_heap 堆排序！
• if_heap 判定一个范围内的元素是不是堆
• is_heap_until 找到第一个不按堆规则的元素