优先级队列
优先级队列 priority_queue 是一种容器适配器,听起来是队列,其实它的底层数据结构是堆,所谓的优先级为默认越大的数优先级越高,即默认为大堆。
使用方式如下面的代码:
#include<iostream> #include<queue> using namespace std; int main() { priority_queue<int> q; priority_queue<int, vector<int>> p; priority_queue<int, vector<int>, less<int>> pq; priority_queue<int, vector<int>, greater<int>> qp; q.push(3); q.push(1); q.push(4); q.push(8); q.push(2); while (!q.empty()) { cout << q.top() << ' '; q.pop(); } cout << endl; return 0; }
其中前三行实例化的对象是等价的,都是建大堆,即 class Container 的默认适配容器是 vector,class Compare 默认的仿函数是 less,只有传了默认适配器后才能传仿函数类或类模板。
仿函数 less(return x < y) 在堆的排序算法中比较部分起的作用是建大堆,greater (return x > y)在堆的排序算法中是建小堆,这与日常认知恰好相反。
优先级队列的底层是堆,那么它的插入和删除的时间复杂度就和堆一样,为 O(logN)
仿函数
仿函数的使用可以使优先级队列的使用者随意控制大小堆,通过参数来传递
所谓仿函数,其实是一个类,但它实例化出的对象可以像函数一样去使用,这个功能在C++中其实是为了替换函数指针的,那么它到底是咋样的?
那么在这,它就起到了比较两个数大小的作用
当然,它也可以配合模板来使用
那么,这么简单的功能,如何在优先级队列中做到改变大小堆的功能呢?
首先,写两个仿函数的类模板,分别用来作堆中 父亲 大于孩子结点 和 父亲 小于孩子结点的比较,在 priority_queue类的模板中添加一个模板参数,用于接收一个类模板
控制传过去的参数为 Less 和 Greater ,用这个模板参数Compare 接收,Compare实例化出的对象即可起到比较两个数大小的作用。若传过来的参数为 Less类模板,即可判断一个数是否小于另一个数;若传过来的参数为 Greater,即可判断一个数是否大于另一个数。
实例化对象 _com
在比较父子结点大小的时候即可使用
所以,当传递模板参数为 Less 的时候,即可控制堆为大堆;当传递模板参数为 Greater 的时候,即可控制堆为小堆。使用下面的代码来测试:
void test1() { zyb::Priority_queue<int, vector<int>, Less<int>> pq; pq.push(1); pq.push(9); pq.push(4); pq.push(3); while (!pq.empty()) { cout << pq.top() << ' '; pq.pop(); } cout << endl; zyb::Priority_queue<int, vector<int>, Greater<int>> p; p.push(1); p.push(9); p.push(4); p.push(3); while (!p.empty()) { cout << p.top() << ' '; p.pop(); } cout << endl; } int main() { test1(); return 0; }
运行结果如下,成功的通过传递的参数不同建立了大堆和小堆
priority_queue 实现源码
命名空间应该自己定义。
#pragma once #include<vector> using namespace std; template<class T> class Greater { public: bool operator()(const T& x, const T& y) { return x > y; } }; template<class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; namespace zyb { template<class T, class Container = vector<T>,class Compare = Less<T>> class Priority_queue { public: Priority_queue() {} Compare _com; void adjust_up(int child) { size_t parent = (child - 1) / 2; while (child > 0) { if (_com(_con[parent],_con[child])) { swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(int parent) { int child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && _com(_con[child],_con[parent])) { child = child + 1; } if (_com(_con[parent],_con[child])) { swap(_con[parent], _con[child]); parent = child; child = 2 * parent + 1; } else { break; } } } 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); } size_t size() { return _con.size(); } T& top() { return _con[0]; } bool empty() { return _con.empty(); } private: Container _con; }; }
从下面官方的定义就可以知道了,为什么传第三个参数的时候,必须先传第二个参数,第二个参数中包含着要比较数据的类型,第三个仿函数模板类型是跟容器里数据类型有关的!