今天来简单分享一下写一个极简版的优先级队列。
1.什么是优先级队列？？？
优先级队列属于STL中队列的一种，虽然包含在队列容器里，但它并不是真正的队列。
在本质上，优先级队列更像一个堆，默认是大堆。
链接：LINK
下面我们简单来认识一下优先级队列的基本使用。
2.优先级队列的基本使用与理解
优先级队列的主要接口有下面这些：
// 优先级队列，默认底层是大堆。 priority_queue<int> ps; ps.push(2); ps.push(3); ps.push(4); ps.push(1); while (!ps.empty()) { cout << ps.top() << " "; ps.pop(); }
那可以让他变成小堆吗？当然可以。但是需要用到仿函数。
// 优先级队列，可以用仿函数置为小堆 priority_queue<int, vector<int>, greater<int>> pq; pq.push(2); pq.push(3); pq.push(4); pq.push(1); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }
这里区分两个概念：取出结果是有序与真正排序的区别。
在上面优先级队列中，我们发现while+top取出的数据是有序的，这是因为我们每次取得都是堆顶元素。至于怎么弄的，可以参考C数据结构钟堆删除数据时候得操作，首尾交换，然后size–，我觉得应该是相同的操作。
// 我们发现sort默认排序为升序。 vector<int> v = { 1,3,4,2 }; vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; } cout << endl; sort(v.begin(), v.end()); it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; }
为了让sort变成升序，我们也可以用仿函数进行设置。
vector<int> v = { 1,3,4,2 }; vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; } cout << endl; sort(v.begin(), v.end(), greater<int>()); it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; }
重点区分一个地方：模板参数与函数参数的需要
priority_queue<int, vector<int>, greater<int>> pq;
sort(v.begin(), v.end(), greater<int>());我们发现两个greater一个带括号一个不带，这是什么情况呢？
要注意优先级队列是一种模板，需要的是类型进行实例化，而sort是模板实例化出来的一种函数，需要迭代器区间和具体的比较仿函数对象，而不是仅仅一个仿函数类型就行。
3.优先级队列的模拟实现
#pragma once #include<vector> #include<iostream> using namespace std; template<typename T> struct Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template<typename T> struct Greater { public: bool operator()(const T& x, const T& y) { return x > y; } }; template<class T, class Container = vector<T>, class Compare = Greater<T>> class periority_queue { private: Container _con; public: void adjust_up(int child) { Compare com; int parent = (child - 1) / 2; while (child > 0) { if (com(_con[child], _con[parent])) { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void push(const T& x) { _con.push_back(x); adjust_up(_con.size() - 1); } void adjust_down(int parent) { Compare com; int child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && com(_con[child + 1], _con[child])) { child = child + 1; } if (com(_con[child], _con[parent])) { swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } const T& top() { return _con[0]; } };
其实大部分接口实现都是复用vector的，但是插入和删除接口的逻辑还需要重点看一下。整体没什么难点，需要注意的是我们实现用了一个comper的东西去控制是建小堆/大堆。
comper传的是仿函数类型。我们在向上/向下调整算法中使用这个仿函数类型生成了仿函数(函数对象)进行控制。
引入仿函数的意义：
在本实例中，仿函数是用来控制是建大堆/小堆的，我们C语言可以传函数指针来控制，这个CPP的话比较习惯用仿函数，说白了就是传入一个特殊类对象来控制，感觉无论是C语言的传函数指针还是CPP传仿函数如果控制得当都挺好用，当然前提是C语言那个指针得玩的明白。CPP这个算是一种难度降低吧，毕竟函数指针有时候会弄错。
EOF
