c++堆

　　heap并不屬于STL容器元件，它分為 max heap 和min heap，在預設情況下，max-heap是優先隊列（priority queue）的底層實作機制。

而這個實作機制中的max-heap實際上是以一個vector表現的完全二叉樹（complete binary tree）。

　　二叉堆（binary heap）就是i一種完全二叉樹。也即是。整棵二叉樹除了最底層的葉節點以外，都是填滿的，而最低層的葉子結點必須是從左到右不留白隙。

至于max-heap和min-heap，前者的任何一個父親結點都必須大于等于他的任意子結點，而後者相反。

下面我們利用數組來隐式表達這棵數：

　　第0号元素保留，從arry[1]開始儲存A，這時候我們可以輕易的看到：

　　位于位置i的某個結點arry[i]，他的左子結點必然在arry[2*i]中，右子結點必然位于arry[2*i+1]，其父親結點必然位于arry[i/2]處。

　　這種數組表達的方式我們 稱為 隐式表達。

　　當然由于arry大小是靜态的，不能動态添加元素，我們可以使用vector來實作。

heap-算法：

1. push_heap()，新添加一個元素在末尾，然後重新調整堆序。也就是把元素添加在底層vector的end()處。

該算法必須是在一個已經滿足堆序的條件下，添加元素。該函數接受兩個随機疊代器，分别表示first,end,區間範圍。

關鍵是我們執行一個siftup()函數，上溯函數來重新調整堆序。具體的函數機理很簡單，可以參考我的程式設計珠玑裡面堆的實作的文章。

2. pop_heap()，這個算法跟push_heap類似，參數一樣。不同的是我們把堆頂元素取出來，放到了數組或者是vector的末尾，用原來末尾元素去替代，

然後end疊代器減1，執行siftdown()下溯函數來重新調整堆序。

注意算法執行完畢後，最大的元素并沒有被取走，而是放于底層容器的末尾。如果要取走，則可以使用底部容器（vector）提供的pop_back()函數。

3. sort_heap()，既然每次pop_heap可以獲得堆中最大的元素，那麼我們持續對整個heap做pop_heap操作，每次将操作的範圍向前縮減一個元素。

當整個程式執行完畢後，我們得到一個非降的序列。

同理，sort_heap(RamdomAccessIteraor first,RamdomAccessIteraor end)接受兩個随機疊代器作為參數。表示操作的範圍。

注意這個排序執行的前提是，在一個堆上執行。執行完之後序列也就失去了堆的性質。

 4.一道很經典的題目就是在1億個數中找到最大的前100個數，這是一道堆應用題，找最大的前100個數，那麼我們就建立一個大小為100的最小化堆，每來一個元素就與堆頂元素比較，因為堆頂元素是目前前100大數中的最小數，前來的元素如果比該元素大，那麼就把原來的堆頂替換掉并重新調整堆。