阅读量:0
目录
💡前言
优先队列(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; } 