C++ heap學習

1. C++并沒有一個叫heap的STL

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

2. 關于heap的一些說明與操作如下：

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

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

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

《在這裡值得一提的是》，heap對于map/unordered_map的排序（大小排序方式）是根據key值來排序的。

操作們：

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

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

關鍵是我們執行一個siftup()函數，上溯函數來重新調整堆序。

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

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

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

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

sort_heap（） 算法：接受兩個随機疊代器作為參數。表示操作的範圍。

make_heap()算法：建立一個堆。很簡單吧。接受的參數同上。

3. 代碼與執行個體結果如下：

代碼：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void show(vector<int> hehe){
    for(int i=0;i!=hehe.size();i++)cout<<hehe[i]<<" ";
    cout<<endl;
}

int main()
{
    int ia[9]={0,1,2,3,4,8,9,3,5};
    vector<int> ivec(ia,ia+9);
    
    make_heap(ivec.begin(),ivec.end());
    show(ivec);
    
    ivec.push_back(7);
    push_heap(ivec.begin(),ivec.end());//這裡可以用make_heap替換。
    show(ivec);
    
    pop_heap(ivec.begin(),ivec.end());
    show(ivec);
    cout<<ivec.back()<<endl;
    ivec.pop_back();
    show(ivec);
    
    sort_heap(ivec.begin(),ivec.end());
    show(ivec);
    
    return 0;
}
           

結果:

9 5 8 3 4 0 2 1 3 
9 7 8 3 5 0 2 1 3 4 
8 7 4 3 5 0 2 1 3 9 
9
8 7 4 3 5 0 2 1 3 
0 1 2 3 3 4 5 7 8 
Program ended with exit code: 0