priority_queue的介紹

通常用堆來實現，能在O(log n)的時間復雜度內插入和提取最高（或最低）優先級的元素。

1. 優先隊列是一種容器適配器，根據嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大的(默認情況)。
2. 此上下文類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素(優先隊列中位于頂部的元素)。
3. 優先隊列被實現為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從特定容器的“尾部”彈出，其稱為優先隊列的頂部。
4. 底層容器可以是任何標準容器類模板，也可以是其他特定設計的容器類。容器應該可以通過隨機訪問迭代器訪問，并支持以下操作
   empty()：檢測容器是否為空
   size()：返回容器中有效元素個數
   front()：返回容器中第一個元素的引用
   push_back()：在容器尾部插入元素
   pop_back()：刪除容器尾部元素
5. 標準容器類vector和deque滿足這些需求。默認情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用vector。
6. 需要支持隨機訪問迭代器，以便始終在內部保持堆結構。容器適配器通過在需要時自動調用算法函數make_heap、push_heap和pop_heap來自動完成此操作。

弱排序標準是一種在數學和編程中用于定義元素之間排序關系的二元關系。它要求關系滿足以下三個主要性質：
1.自反性：對于任何元素a，a與自身是相等的。
2.傳遞性：如果a小于b，且b小于c，則a小于c。
3.連通性：對于任何兩個元素a和b，要么a小于b，要么b小于a

priority_queue的使用

1.默認情況下是大堆，其底層按照less比較；若創建小堆，將第三個模板參數換成greater的比較方式；
2.如果在priority_queue中放自定義類型的數據，用戶需要在自定義類型中提供> 或者< 的重載。

數組中第k大的元素

大堆方法：第三個模板參數直接使用less排序，利用前置–的特性，k–
將優先級隊列中的前k-1個元素刪除掉

小堆方法：第三個模板參數要傳入greater排序函數，運用topk問題思想，創建前k個元素的小堆，從數組的第k個元素開始遍歷。如果當前元素大于堆頂元素（堆頂是最小值），則移除堆頂元素，并將當前元素加入堆。最后，堆頂元素即為數組中第k大的元素。

priority_queue的模擬實現

仿函數

又稱函數對象，是類模板，通過重載()運算符，使得類模板的對象可以像函數一樣被調用。
區分：函數模板要傳對象，類模板要傳參數是類型，不能加括號

向下調整

void Adjustdown(int parent)
{Compare com;int child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child],_con[child + 1])){child++;}if (com(_con[parent],_con[child])){swap(_con[parent], _con[child]);parent = child;child = 2 * parent + 1;}elsebreak;}
}

通過比較器 Compare 確定堆的類型。用于從父節點開始向下調整堆結構，確保堆的性質得到滿足。
作用：維護堆的性質，確保插入或移除操作后堆的結構仍然有效。
應用場景：插入新元素后或移除堆頂元素后調用。

向上調整

void Adjustup(int child)
{Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent],_con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 2) / 2;}else{break;}}
}

通過比較器 Compare 確定堆的類型。用于從子節點開始向上調整堆結構，確保堆的性質得到滿足。
作用：維護堆的性質，確保插入新元素后堆的結構仍然有效。
應用場景：插入新元素后調用。

構造函數

復制元素：將迭代器范圍內的所有元素復制到內部容器 _con 中。
構建堆：從最后一個非葉子節點開始，運用向下調整法逐步向上調整堆結構，確保堆的性質得到滿足。

刪除

交換堆頂元素與末尾元素，然后調用尾刪函數，或者直接size–實現刪除功能，再從堆頂即下標為0的位置開始向下調整來滿足堆序

插入

插入新元素后，從最后索引位置size()-1來向上調整滿足堆序。

自定義類測試(日期類)

	class Date{public: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);}friend ostream& operator<<(ostream& _cout, const Date& d);private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}struct LessPDate{bool operator()(const Date* p1, const Date* p2){return *p1 < *p2;}};
}

void test_priority_queue2()
{priority_queue<Date*, vector<Date*>, LessPDate> pq;pq.push(new Date(2024, 6, 7));pq.push(new Date(2025, 1, 19));pq.push(new Date(2025, 10, 24));while (!pq.empty()){cout << *pq.top() << " ";pq.pop();}cout << endl;//測試仿函數的調用，與日期類無關Less<int>lessfunc;cout << lessfunc(10, 24) << endl;cout << lessfunc.operator()(10, 24) << endl;
}

優先級隊列的定義：priority_queue<Date*, vector<Date*>, LessPDate> 表示優先級隊列中存儲的是 Date 類型的指針，底層容器是 vector，比較器是 LessPDate。
插入元素：通過 push 方法插入三個 Date 對象。
輸出元素：通過 while 循環依次輸出隊列中的元素，直到隊列為空。

整體代碼

#pragma once
#include<vector>
#include<functional>//仿函數/函數對象
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;}
};namespace ee
{template<class T,class Container=vector<T>, class Compare=less<T>>class priority_queue{private:void Adjustdown(int parent){Compare com;int child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child],_con[child + 1])){child++;}if (com(_con[parent],_con[child])){swap(_con[parent], _con[child]);parent = child;child = 2 * parent + 1;}elsebreak;}}void Adjustup(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent],_con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 2) / 2;}else{break;}}}public:priority_queue(){}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--){Adjustdown(i);}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();Adjustdown(0);}void push(const T& x){_con.push_back(x);Adjustup(_con.size() - 1);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};

反向迭代器

顧名思義是用于反向遍歷的工具。反向迭代器通常通過容器的 rbegin() 和 rend() 方法獲取。rbegin() 返回指向容器最后一個元素下一個位置的反向迭代器(end)，而 rend() 返回指向容器第一個元素的反向迭代器(begin)。

namespace ee
{template<class Iterator,class ref,class ptr>struct ReverseIterator{typedef ReverseIterator<Iterator, ref, ptr> self;Iterator _it;ReverseIterator(Iterator it):_it(it){ }ref operator*(){Iterator tmp = _it;return *(--tmp);}ptr operator->(){//返回解引用對象的地址return &(operator*());}self& operator++()//前置++{--_it;return *this;}self& operator--(){++_it;return *this;}bool operator!=(const self& s)const{return _it != s._it;}};
}

一般采用鏡像對稱的方式來模擬實現，即rbegin對應end，rend對應begin。
在重載*運算符時需要注意解引用的是迭代器當前指向的前一個位置，因為rbegin是最后元素的下一個位置，有可能為空會造成非法訪問，或者是哨兵位頭節點的位置。
++和–分別實現自減和自增的操作來滿足反向迭代器的功能。

若不使用鏡像對稱的方式來模擬實現反向迭代器，那么*操作符的重載就要跟隨發生變化。

vector中適配

記得包含ReverseIterator.h頭文件即可

list中適配