优先级队列

priority_queue:

头文件就是queue

第一个是模版，第二个是容器适配器，第三个是仿函数

仿函数传less，出来是大堆

仿函数传greater，出来是小堆

底层是大堆，优先级高的“大”，在堆顶，取出来的有序，存的无序，pop堆顶

传类型： 

//priority_queue<int> pq; // 小堆 //A::priority_queue<int, deque<int>> pq; //A::priority_queue<int, vector<int>> pq; // 大堆 //A::priority_queue<int> pq; // 小堆 A::priority_queue<int, vector<int>, A::greater<int>> pq; pq.push(2); pq.push(1); pq.push(4); pq.push(3); pq.push(7); pq.push(8); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl;

传对象： 自动推演参数类型

// 仿函数 vector<int> v = { 3,1,7,4,6,3 }; // 默认升序 sort(v.begin(), v.end()); for (auto e : v) { cout << e << " "; } cout << endl; // 降序 > //greater<int> gt;//有名对象 //sort(v.begin(), v.end(), gt); sort(v.begin(), v.end(), greater<int>());//使用匿名对象 for (auto e : v) { cout << e << " "; } cout << endl;

仿函数：

一个类只要重载了operator( )就叫仿函数，也就是说这个类的对象可以像函数一样使用，省略函数名，直接由对象调用

// 所有数据都公有，一般就用struct // 有些公有，有些私有，一般就用class // // 仿函数/函数对象 // 仿函数的对象可以像函数一样的去使用 template<class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; int main(){ Less<int> lessfunc; cout << lessfunc(1, 2) << endl;//有名对象 cout << lessfunc.operator()(1, 2) << endl; cout << Less<int>()(1, 2) << endl;//匿名对象 cout << Less<int>().operator()(1, 2) << endl; vector<int> v; v[0]; v.operator[](0); } 优先级队列内部实现：

容器适配器也可以用deque

C用函数指针控制，比较大小的函数

//仿函数 template<class T> class less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> class greater { public: bool operator()(const T& x, const T& y) { return x > y; } }; //堆是完全二叉树，用的是数组实现的，所以这里优先级队列也用vector //大堆 template<class T, class Container = vector<T>, class Compare = less<T>> class priority_queue { public: void adjust_up(size_t child) { Compare com; int parent = (child - 1) / 2; while (child > 0) { //if (_con[child] > _con[parent]) //if (_con[parent] < _con[child]) if (com(_con[parent], _con[child]))//less { 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(size_t parent) { Compare com; size_t child = parent * 2 + 1; while (child < _con.size()) { //if (child + 1 < _con.size() && _con[child + 1] > _con[child]) //if (child + 1 < _con.size() && _con[child] < _con[child + 1]) if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))//less { ++child; } //if (_con[child] > _con[parent]) //if (_con[parent] < _con[child]) if (com(_con[parent], _con[child])) { 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); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } const T& top() { return _con[0]; } private: Container _con; }; //使用 // 小堆 A::priority_queue<int, vector<int>, A::greater<int>> pq; pq.push(2); pq.push(1); pq.push(4); pq.push(3); pq.push(7); pq.push(8); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; 日期类： class Date { public: friend ostream& operator<<(ostream& _cout, const Date& d); Date(int year = 1900, int month = 1, int day = 1) : _year(year) , _month(month) , _day(day) {} bool operator<(const Date& d)const { return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day); } bool operator>(const Date& d)const { return (_year > d._year) || (_year == d._year && _month > d._month) || (_year == d._year && _month == d._month && _day > d._day); } private: int _year; int _month; int _day; }; ostream& operator<<(ostream& _cout, const Date& d) { _cout << d._year << "-" << d._month << "-" << d._day; return _cout; } //运算符重载必须至少有一个自定义类型 //这里两个都是内置类型，指针，所以不能这样重载 //bool operator<(const Date* d1, const Date* d2) //{ // return true; //} class GreaterPDate { public: bool operator()(const Date* p1, const Date* p2) { return *p1 > *p2; } }; void test_priority_queue2() { A::priority_queue<Date, vector<Date>, A::greater<Date>> pq; Date d1(2024, 4, 8); pq.push(d1);//有名对象 pq.push(Date(2024, 4, 10));//匿名对象 pq.push({ 2024, 2, 15 });//隐式类型转换（临时对象） while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; //如果优先级队列里存的是指针 //可以重新写一个GreaterPDate，否则push之后比较的就是括号里东西的大小，也就是Date*，new的地址 //但是如果运算符重载必须至少有一个自定义类型，不能重载Date*也就是指针的比较大小 A::priority_queue<Date*, vector<Date*>, GreaterPDate> pqptr; pqptr.push(new Date(2024, 4, 14)); pqptr.push(new Date(2024, 4, 11)); pqptr.push(new Date(2024, 4, 15)); while (!pqptr.empty()) { cout << *(pqptr.top()) << " "; pqptr.pop(); } cout << endl; } 商品类： struct Goods { string _name; // 名字 double _price; // 价格 int _evaluate; // 评价 Goods(const char* str, double price, int evaluate) :_name(str) , _price(price) , _evaluate(evaluate) {} }; struct ComparePriceLess { bool operator()(const Goods& gl, const Goods& gr) { return gl._price < gr._price; } }; struct ComparePriceGreater { bool operator()(const Goods& gl, const Goods& gr) { return gl._price > gr._price; } }; struct CompareEvaluateLess { bool operator()(const Goods& gl, const Goods& gr) { return gl._evaluate < gr._evaluate; } }; struct CompareEvaluateGreater { bool operator()(const Goods& gl, const Goods& gr) { return gl._evaluate > gr._evaluate; } }; int main() { vector<Goods> v = { { "苹果", 2.1, 5 }, { "香蕉", 3, 4 }, { "橙子", 2.2, 3 }, { "菠萝", 1.5, 4 } }; sort(v.begin(), v.end(), ComparePriceLess()); sort(v.begin(), v.end(), ComparePriceGreater()); sort(v.begin(), v.end(), CompareEvaluateLess()); sort(v.begin(), v.end(), CompareEvaluateGreater()); }