最近越来越觉得自己总结的事情越来越流水账,因此,我需要提高我总结内容的精度。所以可能会导致写博客的时间会延长一些。
之前从没用过优先队列,刷算法题目的时候才开始了解的,所以做个总结。什么情况下使用呢?比如当你需要获取到最大最小值元素,而又不想用最大最小堆的原生实现,STL 提供给你更加简单的库,就是 priority_queue,其时间复杂度也只有 o(nlogn)。
根据元素的优先级被读取,这个优先级取决于你设置的排序函数,如果你没设置,缺省的排序法则则是利用 operator < 形成降序排列,也就是从大到小排列的大顶堆,第一个自然就是最大的元素。还有如果你没设置保存数据的容器 Container 的话,默认用的是 vector。
- namespace std {
- template < class T ,
- class Container = vector ,
- class Compare = less <typename Container::value_type> >
- class priority_queue ;
- }
priority_queue 提供了三个基本函数,分别是:
注意,pop 并不会返回元素,top 才会返回堆顶的元素。
STL 提供了仿函数 greater<>,less<>,简化了自己再定义排序函数的过程。如果你想使用自己定义的结构,而不想使用基本数据类型,也是 ok 的,不过你需要在你自定义的类中重载运算符,比如:
- class Student
- {
- int id;
- char name[20];
- bool gender;
- bool operator < (Student &a) const
- {
- return id > a.id;
- }
- };
这是一个找输入流的中间值的题目,用最大最小堆实现。
- priority_queue < int,
- vector < int > ,
- less < int >> maxHeap; //存储小的值,值越大,优先级越高
- priority_queue < int,
- vector < int > ,
- greater < int >> minHeap; //存储大的值,值越小,优先级越高
- /**
- * 完全不需要判断各种判断
- * 不过一定要注意minHeap和maxHeap的优先级顺序,避免弄反了
- */
- void addNum3(int num) {
- minHeap.push(num);
- maxHeap.push(minHeap.top());
- minHeap.pop();
- // 平衡
- if (minHeap.size() < maxHeap.size()) {
- minHeap.push(maxHeap.top());
- maxHeap.pop();
- }
- }
- double findMedian3() {
- return maxHeap.size() == minHeap.size() ? (double)(maxHeap.top() + minHeap.top()) / 2.0 : (double) minHeap.top() / 1.0;
- }
- void test() {
- this - >addNum3(1);
- this - >addNum3(2);
- cout << this - >findMedian3() << endl;
- this - >addNum2(3);
- cout << this - >findMedian3() << endl;
- }
显然,我们可以看出 priority_queue 的底层实现是堆实现的。里面的 c 就是你自己提供的容器 Container。
- void push(value_type&& _Val)
- { // insert element at beginning
- c.push_back(_STD move(_Val));
- push_heap(c.begin(), c.end(), comp);
- }
- template<class... _Valty>
- void emplace(_Valty&&... _Val)
- { // insert element at beginning
- c.emplace_back(_STD forward<_Valty>(_Val)...);
- push_heap(c.begin(), c.end(), comp);
- }
- bool empty() const
- { // test if queue is empty
- return (c.empty());
- }
- size_type size() const
- { // return length of queue
- return (c.size());
- }
- const_reference top() const
- { // return highest-priority element
- return (c.front());
- }
- void push(const value_type& _Val)
- { // insert value in priority order
- c.push_back(_Val);
- push_heap(c.begin(), c.end(), comp);
- }
- void pop()
- { // erase highest-priority element
- pop_heap(c.begin(), c.end(), comp);
- c.pop_back();
- }
来源: http://www.cnblogs.com/George1994/p/6477198.html