優先隊列

　　隊列是一個操作受限的線性表，數據只能在一端進入，另一端出來，具有先進先出的性質。有時在隊列中需要處理優先級的情況，即后面進入的數據需要提前出來，這里就需要優先隊列。優先隊列是至少能夠提供插入和刪除最小值這兩種操作的數據結構。對應于隊列的操作，插入相當于入隊，刪除最小相當于出隊。 　　鏈表，二叉查找樹，都可以提供插入和刪除最小這兩種操作。對于鏈表的實現，插入需要O(1)，刪除最小需要遍歷鏈表，故需要O(N)。對于二叉查找樹，這兩種操作都需要O(logN)；而且隨著不停的刪除最小的操作，二叉查找樹會變得非常不平衡；同時使用二叉查找樹有些浪費，因此很多操作根本不需要。一種較好的實現優先隊列的方式是二叉堆（下面簡稱堆）。 　　 堆

　　堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于（或不小于）其左右孩子（若存在）結點的關鍵字。首先堆是完全二叉樹（只有最下面的兩層結點度能夠小于2，并且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹），其次任意節點的左右孩子（若有）值都不小于其父親，這是小根堆，即最小的永遠在上面。相反的是大根堆，即大的在上面。 　　因為完全二叉樹有很好的規律，因此可以只用數據來存儲數據而不需要鏈表。如下圖： 　　 　　如圖保存在數組中的數據A~J，對于任意位置i，其左兒子在數組中位置為2i，其右兒子在數組中位置為2i+1，其父親位置在floor(i/2)。 　　 　　堆的插入：插入堆，那么堆中元素將加一，會在最后一個葉子后添加一個葉子，如上圖中的J后面。添加了一個葉子后，需要按照大小比較將這個值放到特定的位置，直到滿足堆條件，這是個上濾過程。 　　堆的刪除最小：刪除堆中最小的一個，對于小根堆來說就是刪除根，刪除根后，需要將下面的元素按照大小規則往上移，直到刪除最后一個葉子，這是個下濾過程。 　　建堆的時間復雜度為O(N)，刪除堆最小值的時間復雜度為O(logN),N為節點數。

定義一個堆結構并實現數據插入和刪除最小值操作：

參考： 　　優先隊列及最小堆最大堆 　　PRiority Queue(Heaps)–優先隊列（堆）

STL中的優先隊列：priority_queue

　　priority_queue為STL中實現的優先隊列結構，輸入存入隊列會自動按照大根堆的性質保存。它的模板聲明帶有三個參數： 　　priority_queue<Type, Container, Functional> Type 為數據類型，Container 為保存數據的容器，Functional 為元素比較方式。Container 必須是用數組實現的容器，比如 vector, deque 但不能用 list。STL里面默認用的是 vector，比較方式默認用 Operator< , 所以如果你把后面倆個參數缺省的話，優先隊列就是大頂堆，隊頭元素最大。 　　priority_queue<int,vector<int>，greater<int> >q3;//定義小的先出隊

常用的函數：

priority_queue定義在頭文件queue中，在此文件中還有一種數據類型queue，即單向隊列，基本操作也是上面的幾個函數，與雙向隊列deque略有差別。 基本定義：queue<int> q;

對于自己定義的數據類型作為隊列參數，用法參考：priority_queue的用法