优先队列是一个特殊的队列,普通队列是先进先出(FIFO)的,而优先队列是根据元素的大小(优先级)决定元素的出队顺序。
目录
- C++ STL的优先队列
- 自定义比较行为
- 函数对象
- 使用STL定义的函数对象
- 重载比较运算符
- 自定义函数对象
- 自己实现优先队列
C++ STL的优先队列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| #include <queue> #include <iostream>
int main() { std::priority_queue<int> pq; pq.push(1); pq.push(10); pq.push(20); pq.push(18); pq.push(3); pq.push(12); int size = pq.size();
for (int i=0; i < size; i++) { std::cout<<pq.top()<<' '; pq.pop(); } std::cout<<std::endl; return 0; }
|
priority_queue默认是从大到小排序,是因为priority_queue使用了一个默认的比较行为,下面介绍如何自定义比较行为从而按照我们的意愿得到想要的结果。
自定义比较行为
函数对象
先让我们看一下优先队列在STL中的说明。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
template<typename _Tp, typename _Sequence = vector<_Tp>, typename _Compare = less<typename _Sequence::value_type> > class priority_queue {}
|
可以看到priority_queue类模板实际有三个参数.
- _Tp: 元素类型,就是我们存放在优先队列中的元素类型。
- _Sequence: 元素序列, 默认是vector<_Tp>。
- _Compare: 比较函数对象, 默认是less<_Sequence::value_type>。
前两个模板参数很好理解,第三个参数比较特殊, _Compare
是一个函数对象(也叫仿函数)。函数对象是一个行为类似于函数的对象,也是通过类来定义的。函数对象可以使得函数功能更加的泛化,STL的算法中很多都使用了函数对象,允许用户可以通过函数对象自定义函数的行为。比如:sort函数接收一个函数对象允许自定义比较行为。
priority_queue默认的函数对象是less,less的定义如下:
1 2 3 4 5 6 7 8 9
| template<typename _Tp> struct less : public binary_function<_Tp, _Tp, bool> { _GLIBCXX14_CONSTEXPR bool operator()(const _Tp& __x, const _Tp& __y) const { return __x < __y; } };
|
less
就是一个函数对象类,其继承了binary_function
。类内自定义了一个函数operate()
,所有的函数对象都是通过operate()
发挥作用的。在以函数对象为参数的函数内部通过调用函数对象的operate()
方法实现函数行为的泛化。
1 2 3 4 5 6
| void algorithm(arg1, arg2,..,,functorObj) { ... functorObj(); ... }
|
通过functorObj() 便可以调用函数对象的operate()
方法,这种语法类似于Python
的callable对象(定义了 __call__ 方法的对象)。我们通过重写operate()
或者编写新的operate()
方法就可以定制算法的行为。
使用STL定义的函数对象
STL标准库定义了多个用于比较的函数对象,如less
、less_equal
、greater
、greater_equal
等
1 2
| std::priority_queue<int, std::vector<int>, greater<int>> pq; std::priority_queue<int, std::vector<int>, less<int>> pq;
|
因为priority_queue定义的最后两个参数都是默认参数,如果需要传入第三个参数,那么第二参数也需要传入。
重载比较运算符
我们可以看到less等函数对象都是通过模板实现的,且在operate()
方法使用的是比较运算符。因此可以通过重载类的比较运算符定制priority_queue的行为。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| struct Test { int num; char c; bool operator > (const Test& obj) const { return this->num > obj.num; }
bool operator < (const Test& obj) const { return this->num < obj.num; }
}Test;
int main() { priority_queue<Test, vector<Test>, less<Test>> pq1; priority_queue<Test, vector<Test>, greater<Test>> pq2;
return 0; }
|
自定义函数对象
因为priority_queue第三个参数需要的是一个函数对象,我们可以定义自己定义一个函数对象定制priority_queue的行为。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| struct QueueCmp { bool operator()(const vector<int> &v1, const vector<int> &v2)const { return v1[0] > v2[0]; } };
int main() { priority_queue<vector<int>, vector<vector<int>>, QueueCmp> pq;
return 0; }
|
自己实现优先队列
优先队列实际上是一个堆, 在STL中,优先队列默认是一个大顶堆, 从排序角度看, 就是降序排序(从大到小),因此可以通过堆的相关算法实现优先队列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
| #include <iostream> #include <vector> #include <cmath>
template<class T> class PriorityQueue { private: std::vector<T> data;
public: PriorityQueue() {
} bool empty() const { return data.size()? false:true; }
int size() const { return data.size(); }
T top() const { if (!this->empty()) { return this->data[0]; } return 0; } void push(T data) { this->pushHeap(data); }
void pop() { this->popHeap(); }
private: void popHeap() { this->data.erase(this->data.begin()); this->adjustHeap(0, this->data.size()); }
void adjustHeap(int i, int length) { for(int child = 2*i+1; child < length; child = 2*i+1) { if(child + 1 < length && this->data[child+1] > this->data[child]) { child += 1; } if(this->data[child] > this->data[i]) { this->swap(this->data[child], this->data[i]); i = child; } else { break; } } }
void pushHeap(T data) { this->data.push_back(data); int end = this->data.size()-1;
for(int i=floor(end*0.5 - 0.5); i>=0; i=floor(i*0.5 - 0.5)) { this->adjustHeap(i, end+1); } }
void swap(T &a, T &b) { T temp = a; a = b; b = temp; } };
int main() { PriorityQueue<int> pq; pq.push(1); pq.push(10); pq.push(20); pq.push(18); pq.push(3); pq.push(12);
int size = pq.size();
for (int i=0; i < size; i++) { std::cout<<pq.top()<<' '; pq.pop(); } std::cout<<std::endl; return 0; }
|