目录
?前言一，优先级队列的使用二，仿函数1，什么是仿函数2，仿函数的简单示例 三，优先级队列的底层剖析
?前言
优先队列(priority_queue)是一种容器适配器，默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
注意：使用优先级队列要包含头文件 < queue >。
一，优先级队列的使用
代码实现如下：
这里的建堆一般有两种方式：
(1) 一种是一个一个push进vector容器再进行向上调整建堆
(2) 另一种是直接用迭代器区间构造直接建堆(推荐用这种)。
#include <iostream>#include <queue>#include <functional>using namespace std;void test_priority_queue(){vector<int> v = { 6,0,3,5,4,7,9,1,2,8 };//默认升序//priority_queue<int> pq(v.begin(), v.end());//一个一个尾插建堆priority_queue<int, vector<int>, greater<int>> pq;for (auto e : v){pq.push(e);}//迭代器区间构造，直接建堆//priority_queue<int,vector<int>,greater<int>> pq(v.begin(), v.end());while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}int main(){test_priority_queue();return 0;}注意：优先级队列默认的大堆，降序排列，如果要升序，就要换仿函数。下图中第三个模板参数就是传仿函数。
使用算法库里的 less 和 greater 算法，需要包含头文件< functional >
二，仿函数
1，什么是仿函数
仿函数也叫函数对象，是一个重载了 operator() 的类，可以使得类的对象像函数一样使用。
2，仿函数的简单示例
operator()并没有参数的个数和返回值，所以使用是十分灵活的。
struct Func1{//无参无返回值void operator()(){cout << "Func调用" << endl;}};struct Func2{//有参无返回值void operator()(int n){while (n--){cout << "Func调用" << endl;}}};int main(){Func1 f1;f1(); //使得对象像函数一样使用f1.operator()(); //显示调用cout << endl;Func2 f2;f2(3); //使得对象像函数一样使用return 0;}
三，优先级队列的底层剖析
namespace ling{template<class T>class myless{public: bool operator()(const T& x, const T& y) { return x < y; }};template<class T>class mygreater{public: bool operator()(const T& x, const T& y) { return x > y; }};template <class T, class Container = vector<T>, class Compare = myless<T>>class priority_queue{public: priority_queue() = default;//迭代器区间构造 template <class InputIterator> priority_queue(InputIterator first, InputIterator last) { while (first != last) { con.push_back(*first); ++first; } //建堆 for (int i = (con.size() - 1 - 1) / 2; i >= 0; i--) { Adjust_down(i); } } bool empty() const { return con.empty(); } size_t size() const { return con.size(); }// 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性 const T& top()const { return con[0]; } //向上调整 void Adjust_up(int child) { int parent = (child - 1) / 2; while (child > 0) { //if (con[parent] < con[child]) if(comp(con[parent], con[child])) { swap(con[parent], con[child]); 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) { int child = parent * 2 + 1; while (child < con.size()) { if (child + 1 < con.size() && comp(con[child], con[child + 1])) { child += 1; } //if (con[parent] < con[child]) if(comp(con[parent], con[child])) { swap(con[parent], con[child]); parent = child; child = parent * 2 + 1; } else { break; } } } void pop() { swap(con[0], con[con.size() - 1]); con.pop_back(); Adjust_down(0); }private: Container con; Compare comp;};}测试代码：
void TestQueuePriority(){ling::priority_queue<int> q1;q1.push(5);q1.push(1);q1.push(4);q1.push(2);q1.push(3);q1.push(6);cout << q1.top() << endl;q1.pop();q1.pop();cout << q1.top() << endl;vector<int> v{ 5,1,4,2,3,6 };ling::priority_queue<int, vector<int>, ling::greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl;q2.pop();q2.pop();cout << q2.top() << endl;}