priority_queue介绍
pri_que是一个容器适配器，它的底层是其他容器，并由这些容器再封装而来。类似于heap的结构。默认为大堆。
逻辑实现
框架
namespace xty { template<class T, class Container = vector<T>, class Compare = less<T>> class priority_queue { bool empty() { return _con.empty(); } size_t size() { return _con.size(); } const T& top() { return _con.front(); } void push(const T& x) { _con.push_back(x); adjust_up(_con.size() - 1); } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } private: Container _con; }; }
调整算法
因为优先级队列是以堆为结构实现的，因此插入删除要保持堆的结构，需要adjust_up()和adjust_down()两个算法。
adjust_up()
向上调整，由堆底一直调整到堆顶。
void adjust_up(int child) { int parent = (child - 1) / 2; while (child > 0) { if (_con[child] > _con[parent]) { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }
adjust_down()
向下调整，由堆顶一直向下调整直到叶子。
void adjust_down(int parent) { size_t child = 2 * parent + 1; while (child < _con.size()) { if (child + 1 < _con.size() && _con[child + 1] > _con[child]) { child++; } if (_con[child] > _con[parent]) { swap(_con[child], _con[parent]); parent = child; child = 2 * parent + 1; } else { break; } } }
仿函数/比较函数
我们观察到库的模板参数给了三个，其中第一个参数是数据类型，第二个参数是模板容器，第三个参数就是仿函数（用户可以自己制定比较规则！），默认为大堆less。
template<class T, class Container = vector<T>, class Compare = less<T>>
接下来我们实现一个比较类：
template<class T> struct less { bool operator() (const T& x, const T& y) { return x > y; } }; template<class T> struct grater { bool operator() (const T& x, const T& y) { return x < y; } };
然后我们微调调整函数的逻辑将if的内容改成比较函数：
因为使用方法酷似函数，因此它叫仿函数 ！
void adjust_up(int child) { Compare com; //实例化比较函数 int parent = (child - 1) / 2; while (child > 0) { if (com(_con[child], _con[parent])) /*if (_con[child] > _con[parent])*/ { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(int parent) { Compare com; //实例化比较函数 size_t child = 2 * parent + 1; while (child < _con.size()) { if (child + 1 < _con.size() && com(_con[child + 1], _con[child])) { child++; } if (com(_con[child], _con[parent])) { swap(_con[child], _con[parent]); parent = child; child = 2 * parent + 1; } else { break; } } }
仿函数特性
有了仿函数的功能后，我们可以自己定义比较类型，使程序设计更加灵活。
看下面一段代码：
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 test_priority_queue2() { // 大堆，需要用户在自定义类型中提供<<的重载 //priority_queue<Date> q1; priority_queue<Date, vector<Date>, greater<Date>> q1; q1.push(Date(2018, 10, 29)); q1.push(Date(2018, 10, 30)); q1.push(Date(2018, 10, 28)); cout << q1.top() << endl; }
首先这段测试代码结果是唯一的：
而如果我们增加另一种格式的代码呢？
class PDateLess { public: bool operator()(const Date* p1, const Date* p2) { return *p1 < *p2; } }; class PDateGreater { public: bool operator()(const Date* p1, const Date* p2) { return *p1 > *p2; } }; void test_priority_queue2() { //priority_queue<Date*, vector<Date*>, PDateLess> q2; priority_queue<Date*, vector<Date*>, PDateGreater> q2; q2.push(new Date(2018, 10, 29)); q2.push(new Date(2018, 10, 30)); q2.push(new Date(2018, 10, 28)); cout << *(q2.top()) << endl; }
这段代码如果不写仿函数，结果是不唯一的，因为比较的是指针，重写仿函数后，答案就唯一了！！可以看见，仿函数可以使我们比较数据更加灵活！
构造函数
显然我们没有写构造函数，程序并没有报错，是因为：
- 我们不写构造函数，编译器会默认生成一个。而成员函数是自定义类型，会调用自定义类型的构造函数，所以程序没有问题运行。
- 当我们写了构造函数之后，编译器就不会再默认生成了，需要我们自己写。
迭代器区间构造
因为自己显示写了构造函数，编译器不再默认生成默认构造函数，需要自己再显示补一个默认构造！
//默认构造 priority_queue(){} template<class InputIterator> priority_queue(InputIterator first, InputIterator last) { Container _con; while (first!= last) { push(*first); first++; } }
完整优先级队列代码
namespace xty { template<class T> struct less { bool operator() (const T& x, const T& y) { return x > y; } }; template<class T> struct grater { bool operator() (const T& x, const T& y) { return x < y; } }; template<class T, class Container = vector<T>, class Compare = less<T>> class priority_queue { public: void adjust_up(int child) { Compare com; //实例化比较函数 int parent = (child - 1) / 2; while (child > 0) { if (com(_con[child], _con[parent])) /*if (_con[child] > _con[parent])*/ { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(int parent) { Compare com; //实例化比较函数 size_t child = 2 * parent + 1; while (child < _con.size()) { if (child + 1 < _con.size() && com(_con[child + 1], _con[child])) { child++; } if (com(_con[child], _con[parent])) { swap(_con[child], _con[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } const T& top() { return _con.front(); } void push(const T& x) { _con.push_back(x); adjust_up(_con.size() - 1); } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } priority_queue(){} template<class InputIterator> priority_queue(InputIterator first, InputIterator last) { Container _con; while (first!= last) { push(*first); first++; } } private: Container _con; }; }
