• heap不屬于STL容器的組件，屬于幕后角色，是priority_queue的助手
• priority_queue 允許用戶以任何次序將任何元素推入容器內，但是取出的時候需要從優先級最高(也就是數值最高)的元素開始取，這種思想是基于heap的函數實現
• 如果使用list作為?priority_queue 的底層實現機制，元素的插入操作可以使用常數的時間，但是不好找 極值，需要進行線性掃描和遍歷；如果考慮到大小這個關鍵因素，進行元素的排序，隨后進行元素之間的銜接，降低了元素的插入效率
• 使用binary search tree作為priority的底層機制，這樣對于元素的插入和取極值就有O(logN)的表現；但是缺點是：1，binary search tree需要具備足夠的隨機性；2，binary search tree實現很難；
• binary heap是一種 complate binary tree(完全二叉樹)，除了最底層葉節點之外都是處于飽和的狀態，而最底層的葉節點從左只有不得有空隙，示例如下

• ?complate binary tree(完全二叉樹)整棵樹內部沒有任何的節點漏洞
• 好處：1，使用array存儲所有的節點，保留#0 元素的位置 (將其設為無限大或者無限小),那么當?complate binary tree(完全二叉樹)的某個節點位于array數組中的i處的時候，其左子樹節點必然位于array的 2i 處，其右子樹的節點必然位于array的 2*i+1 的位置。 ( 這里的 / 表示取整數)，通過保留#0 的操作，可以使用array
• 輕而易舉實現出complate binary tree。使用數組的方式表達完全二叉樹的方式 稱為隱式 表述法
• 考慮到array無法動態的改變大小，使用vector代替array實現 完全二叉樹
• 根據元素的排列方式 heap分為max-heap和min-heap，前者每個節點的鍵值 都大于或者等于其子節點的鍵值?；后者 每個節點的鍵值都小于或者等于其每個子節點的鍵值
• max-heap 最大值在根節點，其總是位于底層的array或者vector的開頭；
• min-heap 最小值在根節點，其總是位于底層的array或者vector的開頭；
• STL 供應的是 max-heap 本文所有的heap都按照 max-heap處理

heap的算法

push_heap 算法

• 新加入的元素一定是放在最下一層作為葉節點，并填補從左到右的第一個空格，也就是底層vector()的end()處

• ?執行上溯程序，將新節點和父接地那記性比較，如果大于父節點，就進行父子對換，如此一直上溯，直到不需要對換或者直到遇到根節點為止
• 接收兩個迭代器表示heap的底部操作(vector)的頭尾，并且新的元素插入到底部容器的最尾端，如果不符合這兩個條件，那么push_heap的結果是不可預期的
• distance_type?方便的決定某個迭代器的類型 參考鏈接如下
• STL源碼剖析 5中迭代器型別_CHYabc123456hh的博客-CSDN博客

template<class RandomAccessIterator> inline void push_heap(RandomAccessIterator first,RandomAccessIterator last){//函數被調用的時候 新元素應已經置于底部容器的最尾端//distance_type 用于判斷迭代器的類型，從而判定是否進行偏特化操作__push_heap_aux(first,last,distance_type(first),value_type(first)); }template <class RandomAccessIterator,class Distance,class T> inline void __push_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance *,T*){//根據implicit representation heap的結構特性，新值必須置于底部容器的最尾端，即第一個洞號(last-first)-1__push_heap(first,Distance((last-first)-1),Distance(0),T(*(last-1))); }//以下這組push_back() 不允許指定 "大小比較的標準" template <class RandomAccessIterator,class Distance, class T> void __push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value){Distance parent = (holeIndex - 1)/2; //找出父節點//當holeIndex并沒有到達頂峰的同時 父節點還小于新值 （不符合heap的次序特性）//使用operator < 進行元素的比較，因此STL heap是一種max-heap//父節點是動態變化的//每次是和value進行比較，因此不需要進行父子元素值的對調，直接讓子元素接管父親的數值while(holeIndex > topIndex && *(first + parent) < value){*(first + holeIndex) = *(first + parent); //令洞值為父值,也就是孩子賦予了父親的數值，父親位置holeIndex = parent; //調整洞號，向上提升至父節點parent = (holeIndex - 1)/2;//新洞的父節點}//持續至頂端，或者滿足 heap的次序特性為止*(first + holeIndex) = value;//令新洞為新的數值，完成插入操作 }

pop_heap() 算法

• 彈出最大元素，根節點缺失需要使用最末尾的元素進行彌補，然后執行下放程序，將根節點的數值和最大的葉子節點進行互換，以此類推，直到這個洞的鍵值大于左右兩個子節點，或者下放至葉子節點為止

• pop_heap代碼?

//這個堆沒有指定 大小比較的標準 template <class RandomAccessIterator,class T,class Distance> inline void __pop_heap(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result,T value,Distance *){*result = *first; //設定尾值為首值，也就是此刻的尾值為先前的根節點//可以通過底層容器的 pop_back()取出尾值//重新調整 heap 洞號為0(即樹根處)，將其數值設定為 value(先前的尾節點的數值)__adjust_heap(first,Distance(0),Distance(last-first),value); }//這個堆沒有指定 大小比較的標準 template <class RandomAccessIterator,class Distance,class T> void __adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T value){Distance topIndex = holeIndex;Distance secondChild = 2 * holeIndex +2;//洞節點的右子節點while(secondChild < len){//比較洞節點的左右兩個孩子的數值，然后以secondChild代表較大的子節點if (*(first + secondChild) < *(first + secondChild -1)){secondChild--;}//令較大的子值為洞值 再令洞號下降至較大的子節點處*(first + holeIndex) = *(first + secondChild);holeIndex = secondChild;//找出新洞節點的右子節點secondChild = 2 * (secondChild + 1);}if (secondChild == len){//沒有右邊節點 只有左邊的節點//將左子值設為洞值 再令洞號下移至 左子節點處*(first+holeIndex) = *(first + secondChild - 1);holeIndex = secondChild - 1;}*(first + holeIndex) = value; }

• pop_heap之后，最大元素將被放置于底部容器的最尾端，并沒有被取走。可以使用底部容器提供的back()函數獲取這個數值，也可以使用vector提供的pop_back()函數將其移除

sort_heap()

• pop_heap可以獲得heap中鍵值最大的元素，持續使用pop_heap,不斷得到最大的元素，就可以實現排序。需要注意的是每沒用一次pop_heap都需要將操作范圍從后向前縮減一個元素。
• sort_heap()函數接收兩個迭代器，用來表現一個heap底部容器的頭尾。如果不符合這個條件，sort_heap的排序結果未可預期。
• *排序過后的heap已經被破壞，不再是一個合法的堆了，相當于操作底層的元素，修改了元素，破壞性是無法修改的

template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first,RandomAccessIterator last){//每執行一次pop_heap(),極值(在STL heap中為極大值)就會被放在尾端//扣除尾端再次執行pop_heap()，次極值又被放在新的尾端，按照上述流程一直執行，最后得到排序結果while (last - first > 1){std::pop_heap(first,last--);//每次執行pop_heap()一次，操作范圍即縮減一格} }

?

make_heap()

• ?這個函數的目的是為了將一段現有的數據將其轉化為堆的形式，主要依據就是complate binary tree 的隱式表述

template <class RandomAccessIterator,class T,class Distance> void __make_heap(RandomAccessIterator first,RandomAccessIterator last,T*,Distance *){if (last - first < 2){ //如果長度為0或者為1，不需要重新排列return;}Distance len = last - first;//找出第一個需要重新排列的子樹的頭部，以parent標定//考慮到任何節點不需要執行perlocate down，因此使用hole Index進行命名更好Distance parent = (len - 2)/2;while (true){//重新排列以parent為首的子樹//len的目的是為了讓__adjust_heap() 判斷操作的范圍__adjust_heap(first,parent,len,T(*(first + parent)));if (parent == 0){return; //走完根節點 結束}parent--; // (即將重拍子樹的)頭部向前一個節點} }

heap沒有迭代器

• ?heap不提供遍歷的功能，也不提供迭代器

測試用例

int main(){int ia[9] = {0,1,2,3,4,8,9,3,5};std::vector<int> i_vec(ia,ia+9);std::make_heap(i_vec.begin(),i_vec.end());for (int i = 0; i < i_vec.size(); ++i) {std::cout << i_vec[i] << ' '; //9 5 8 3 4 0 2 3 1}std::cout << std::endl;i_vec.push_back(7);std::push_heap(i_vec.begin(),i_vec.end());for (int i = 0; i < i_vec.size(); ++i) {std::cout << i_vec[i] << ' '; //9 7 8 3 5 0 2 3 1 4}std::cout << std::endl;std::pop_heap(i_vec.begin(),i_vec.end());std::cout << i_vec.back() << std::endl; //9 return but no removei_vec.pop_back(); //remove last elem and no returnfor (int i = 0; i < i_vec.size(); ++i) {std::cout << i_vec[i] << ' '; //8 7 4 3 5 0 2 3 1}std::cout << std::endl;std::sort_heap(i_vec.begin(),i_vec.end());for (int i = 0; i < i_vec.size(); ++i) {std::cout << i_vec[i] << ' '; //0 1 2 3 3 4 5 7 8}std::cout << std::endl;{//test heap (底層使用array實現)int ia[9] = {0,1,2,3,4,8,9,3,5};std::make_heap(ia,ia+9);//array不能動態的改變大小，因此不可以對滿載的array進行push_heap()操作//需要先在array的尾端增加一個元素std::sort_heap(ia,ia+9);for (int i = 0; i < 9; ++i) {std::cout << ia[i] << ' '; //0 1 2 3 3 4 5 8 9}std::cout << std::endl;//經過排序之后的heap 不再是一個合法的heap//重新再做一個heapstd::make_heap(ia,ia+9);std::pop_heap(ia,ia+9);std::cout << ia[8] << std::endl; //8} }

總結

以上是生活随笔為你收集整理的STL 源码剖析 heap堆的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。