priority_queue的作用

priority_queue翻譯過來就是優先級隊列，是stl提供的一個容器適配器，也就是我們數據結構中學到的棧，是一種常用的數據結構，特點是利用類似二叉樹的結構讓父節點元素比子節點大，從而使對頂元素最大（小）。

priority_queue的接口

構造函數

explicit priority_queue (const Compare& comp = Compare(),const Container& ctnr = Container());
template <class InputIterator>priority_queue (InputIterator first, InputIterator last,const Compare& comp = Compare(),const Container& ctnr = Container());

可以用默認構造和迭代器構造，支持指定容器和仿函數對象。

empty

bool empty() const;

堆的判空。

size

size_type size() const;

返回堆的元素數。

top

const value_type& top() const;

返回堆頂元素。

push

void push (const value_type& val);

入堆。

pop

void pop();

出對頂的元素。

swap

void swap (priority_queue& x) noexcept (/*see below*/);

priority_queue自己的交換函數。

priority_queue的實現

#include<iostream>#include<vector>using namespace std;namespace jiunian
{template<class T, class container = vector<T>, class compare = less<T>>class priority_queue{public:typedef priority_queue<T, container> Self;priority_queue(){}template<class Iterator>priority_queue(Iterator begin, Iterator end){Iterator cur = begin;while (cur != end) con.push_back(*(cur++));int pos = size() / 2 - 1;while (pos >= 0) adjustdown(pos--);}bool empty() const{return con.empty();}size_t size() const{return con.size();}const T& top() const{return con.front();}void push(const T& val){con.push_back(val);adjustup(con.size() - 1);}void pop(){std::swap(con.front(), con.back());con.pop_back();adjustdown(0);}void swap(priority_queue& x){con.swap(x.con);}Self operator=(Self x){con = x.con;comp = x.comp;return *this;}private:void adjustdown(int pos)//向下調整{int parent = pos;int child = parent * 2 + 1;if (child + 1 < con.size() && comp(con[child] , con[child + 1])) ++child;while(child < con.size()){if (comp(con[parent], con[child])){std::swap(con[child], con[parent]);parent = child;child = parent * 2 + 1;if (child + 1 < con.size() && comp(con[child], con[child + 1])) ++child;}else{break;}}}void adjustup(int pos)//向上調整{int child = pos;int parent = (child + 1) / 2 - 1;while (parent >= 0){if (comp(con[parent], con[child])){std::swap(con[child], con[parent]);child = parent;parent = (child + 1) / 2 - 1;}else{break;}}}container con;compare comp;};
}

仿函數（函數對象）是什么？

仿函數又稱函數對象，是指其本質雖然是對象，但是用起來就像函數一樣，一個簡單的仿函數長下面這樣：

template<class T>
class compareruler
{bool operator()(const T& a, const T& b){return a < b;}
};

仿函數通過重載()運算符使其使用起來就像函數一樣，依舊以上面這個仿函數為例，它的用法如下

	compareruler<int> com;int a = 0;int b = 1;cout << com(a, b) << endl;

不看上面的對象初始化就會誤以為com是函數了。這就是仿函數，那說了這么多，仿函數有什么用呢？學習過模板的都知道，c++提倡泛型編程，即一段代碼多種用途，通過模板與模板實例化使一段代碼生成多段代碼，鼓勵用戶自定義，提高編程效率。而仿函數更是使泛型編程更進一步，仿函數可以自定義模板編程中的策略模式，使用戶使用起來更加自由，比如在堆的實現過程中就可以自定義兩數之間的比較交換規則實現大堆小堆的切換，這也是我提前介紹一下仿函數的原因。

向上調整算法（adjustup）

void adjustup(int pos)//向上調整
{int child = pos;int parent = (child + 1) / 2 - 1;while (parent >= 0){if (comp(con[parent], con[child])){std::swap(con[child], con[parent]);child = parent;parent = (child + 1) / 2 - 1;}else{break;}}
}

向上調整算法是堆的核心算法之一，其原理是將指定元素通過與其父結點比較，若不符合當前堆的排列規則（大堆小堆）就交換，符合就停止，不斷地循環這個過程直到根節點，從而將指定元素排到合適的位置。具體的實現過程就是先指定結點，將指定的結點視為子節點，算出子結點的父節點，將兩者進行比較，比較邏輯由仿函數給出。若仿函數返回true就交換，之后將換完的父節點視為子節點，再次計算父節點不斷循環；若仿函數返回false就說明到合適的位置了，停止循環即可。過程中要時刻注意越界問題。

向下調整算法（adjustdown）

void adjustdown(int pos)//向下調整
{int parent = pos;int child = parent * 2 + 1;if (child + 1 < con.size() && comp(con[child] , con[child + 1])) ++child;while(child < con.size()){if (comp(con[parent], con[child])){std::swap(con[child], con[parent]);parent = child;child = parent * 2 + 1;if (child + 1 < con.size() && comp(con[child], con[child + 1])) ++child;}else{break;}}
}

向下調整算法也是堆的核心算法之一，其原理是將指定元素通過與其最大的（大堆，小堆相反）子結點比較，若不符合當前堆的排列規則（大堆小堆）就交換，符合就停止，不斷地循環這個過程直到不能向下為止，從而將指定元素排到合適的位置。具體的實現過程就是先指定結點，將指定的結點視為父節點，算出父結點的子節點中最大的一個，將兩者進行比較，比較邏輯由仿函數給出。若仿函數返回true就交換，之后將換完的子節點視為父節點，再次計算子節點不斷循環；若仿函數返回false就說明到合適的位置了，停止循環即可。過程中要時刻注意越界問題。

迭代器構造

		template<class Iterator>priority_queue(Iterator begin, Iterator end){Iterator cur = begin;while (cur != end) con.push_back(*(cur++));int pos = size() / 2 - 1;while (pos >= 0) adjustdown(pos--);}

迭代其構造的思路有兩種，一種是先全部拷進堆中，再排序，第二種是一個個push進去。效率差不多，我使用的第一種，因為難寫一點，使用第一種寫法需要注意使用向下調整算法比向上調整更優秀。為什么呢？使用向上調整算法就要從最上方也就是根節點開始把推遍歷一遍才行，而使用向下調整算法則反之，要從堆的最下面的最后一個元素開始遍歷對一遍。其中向上和向下的算法中單趟的時間復雜度都是logN,這樣看來兩者都是一樣的，但是注意，兩者都是有優化的空間的。當使用向上調整算法時，根節點因為沒有父結點所以沒有比的必要，可以優化掉一個；而使用向下調整算法時最下面一排的元素（滿二叉樹就是最下面一排，不是滿二叉樹就是最下面一排加最下面第二排部分，反正就是沒有子節點的結點也就是葉子節點）因為沒有子節點所以也沒有比的必要，可以優化掉整整一排，要知道最后一排的結點數占了二叉樹差不多一半，優化巨大，所以要用向下調整算法從最后一個有子結點的結點開始遍歷，找這個結點的方式也很簡單，最后一個有子結點的結點就是最后一個元素的父結點。

push

void push(const T& val)
{con.push_back(val);adjustup(con.size() - 1);
}

先入到容器的結尾，再用向上調整算法跳到合適的位置就行。

pop

void pop()
{std::swap(con.front(), con.back());con.pop_back();adjustdown(0);
}

由于我們這的堆是依靠容器中的位置模擬的二叉樹，所以對于相對位置有著強邏輯，堆頂的元素不能直接頭刪，我們先將堆頂元素與最后一個元素交換，之后尾刪，相當于刪除堆頂在找了個替位的，之后對堆頂這個替位的使用向下調整算法調到合適的位置就行了。

由于priority_queue本質是一個容器適配器，其他的函數就只是對適配器接口的一些封裝了，很簡單，這里不過多贅述。