準確來講，heap并不屬于STL容器，但它是其中一個容器priority queue必不可少的一部分，顧名思義，priority queue就是優先級佇列，允許用戶以任何次序將任何元素加入容器內，但取出時是從優先權最高的元素開始取，而優先權有兩種，可以是容器內數值最低的，也可以是數值最高的，而priority queue是選擇了數值高作為評判優先級的標準，對應實作方法就是binary max heap，其作為priority queue的底層機制，
所謂的binary heap（二叉堆），是一種完全二叉樹，也就是說，整棵二叉樹除了最底層的葉子節點外，其他節點都是被填滿的，而最底層的節點是從左至右不得有空節點的，如圖所示：
如圖所示，完全二叉樹整棵樹內沒有任何節點漏洞，這使得我們可以使用陣列來存盤一棵完全二叉樹上的所有結點，另外，如果我們陣列的索引1開始記錄節點，那么父節點與子節點在陣列中的關系就一般為：父節點在 i 處，其左子節點必位于陣列的 2i 處，其右子節點必位于陣列的 2i+1 處，這種以陣串列示樹的方式，稱為隱式表述法，我們的heap需要動態改變節點數，所以用vector是更好的選擇，由于priority queue選擇的是binary max heap做為自己的底層機制，所以也只提供了max heap的實作，所以我們接下里討論的都是大根堆（max heap），每個節點的鍵值都大于或等于其子節點的鍵值，
heap演算法
- push_heap
為了滿足完全二叉樹的條件，最新加入的元素一定要放在最下一層做為葉子節點，并填補在從左至右的第一個空格，新加入的元素并不一定適合于現有的位置，為了滿足max-heap的條件，我們需要對剛加入的元素進行一個上浮（percolate up）的操作：將新節點與其父節點比較，如果其鍵值比父節點的大，就父子交換位置，交換后新加的元素成為了父節點，此時再與它的父節點比較，如此一直上溯，直到不需對換或直到根節點為止，
push_heap函式接受兩個隨機迭代器，用來表示一個heap底部容器（vector）的頭尾，并且新元素已經插入到底部容器的最尾端，才會進入到該函式，如果引數不符合，或并無新元素插入，該函式的執行結果不可預期，
1 template <class RandomAccessIterator> 2 inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) { 3 // 注意，此函式被呼叫時，新元素應已置于底層容器的最尾端， 4 //即是新元素被加入到陣列（原本最后元素的下一位置）后，才呼叫該函式 5 __push_heap_aux(first, last, distance_type(first), value_type(first)); 6 }
7 template <class RandomAccessIterator, class Distance, class T> 8 inline void __push_heap_aux(RandomAccessIterator first, 9 RandomAccessIterator last, Distance*, T*) { 10 __push_heap(first, Distance((last - first) - 1), Distance(0), 11 T(*(last - 1))); 12 //于上個函式獲取到的迭代器所指物件型別T，用于強制轉換 13 //Distance(0)為指出最大值的索引值 14 //Distance((last - first) - 1)為指出新添值的索引值 15 }
16 template <class RandomAccessIterator, class Distance, class T> 17 void __push_heap(RandomAccessIterator first, Distance holeIndex, 18 Distance topIndex, T value) { 19 //holeIndex為指出新添值的索引值 20 //topIndex最大值的索引值 21 //value為新添值內容 22 Distance parent = (holeIndex - 1) / 2; // 找出新元素的父節點 23 while (holeIndex > topIndex && *(first + parent) < value) { 24 // 當尚未到達頂端，且父節點小于新值（不符合 heap 的次序特性），繼續上浮 25 // 由于以上使用 operator<，可知 STL heap 是一種 max-heap（大根堆）， 26 *(first + holeIndex) = *(first + parent); // 子位置設父值 27 holeIndex = parent; // percolate up：調整新添值的索引值，向上提升至父節點， 28 parent = (holeIndex - 1) / 2; // 獲取新索引值的父節點 29 } // 持續到頂端，或滿足 heap 的次序特性為止， 30 *(first + holeIndex) = value; // 令最后的索引值為新值，完成插入， 31 }
- pop_heap
最大值在根節點處，pop操作取走根節點（其實是把它轉移到vector的尾端節點上），為了滿足完全二叉樹的條件，必須割舍最底層最右邊的節點，把其值拿出來放至一臨時變數里，然后該位置放根節點的值（最后會被pop_back()給移除），
1 template <class RandomAccessIterator> 2 inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) { 3 __pop_heap_aux(first, last, value_type(first)); 4 } 5 6 template <class RandomAccessIterator, class T> 7 inline void __pop_heap_aux(RandomAccessIterator first, 8 RandomAccessIterator last, T*) { 9 __pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first)); 10 // 設定準條調整的值為尾值，然后將首值調至 11 // 尾節點（所以以上將迭代器 result 設為 last-1），然后重整 [first, last-1)， 12 // 使之重新成一個合格的 heap， 13 } 14 15 template <class RandomAccessIterator, class T, class Distance> 16 inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, 17 RandomAccessIterator result, T value, Distance*) { 18 *result = *first; // 設定尾值為首值，于是尾值即為要求的結果， 19 // 可由客端稍后再呼叫 pop_back() 取出尾值， 20 __adjust_heap(first, Distance(0), Distance(last - first), value); 21 // 以上重新調整 heap，要調整的索引值為 0（亦即樹根處），欲調整值為 value（原尾值）， 22 } 23 24 template <class RandomAccessIterator, class Distance, class T> 25 void __adjust_heap(RandomAccessIterator first, Distance holeIndex, 26 Distance len, T value) { 27 //holeIndex：要調整的索引值，從樹根處出發 28 //len：所有元素個數（不包括被調整到尾節點的首節點），即[0, len) 29 //value：記錄了原最底層最右邊的節點的值 30 Distance topIndex = holeIndex; 31 Distance secondChild = 2 * holeIndex + 2; // 調整的索引值的右子節點 32 while (secondChild < len) { 33 // 比較這左右兩個子值，然后以 secondChild 代表較大子節點， 34 if (*(first + secondChild) < *(first + (secondChild - 1))) 35 secondChild--; 36 // Percolate down：令較大子值代替要調整索引值處的值，再令調整的索引值下移至較大子節點處， 37 *(first + holeIndex) = *(first + secondChild); 38 holeIndex = secondChild; 39 // 繼續找出要調整的索引值的右子節點 40 secondChild = 2 * (secondChild + 1); 41 } 42 if (secondChild == len) { // 相等，說明沒有右子節點（不是說沒有，而是被準備pop掉的元素占用了，見*result = *first;），只有左子節點 43 // Percolate down：令左子值代替要調整索引值處的值，再令要調整的索引值下移至左子節點處， 44 *(first + holeIndex) = *(first + (secondChild - 1)); 45 holeIndex = secondChild - 1; 46 } 47 48 // 此時可能尚未滿足次序特性，再執行一次上浮操作 49 __push_heap(first, holeIndex, topIndex, value); 50 }
注意，pop_heap之后，最大元素只是被放置于底部容器的最尾端，尚未被取走，如果要取其值，可使用底部容器的back()函式，如果要移除它，可使用底部容器所提供的pop_back()函式，
- sort_heap
既然每次呼叫pop_heap可獲得heap中鍵值最大的元素，如果持續對整個heap做pop_heap操作，且每次的操作范圍都從后向前縮減一個元素，那么當整個程式執行完畢，我們便有了一個遞增序列，sort_heap便是如此做的，該函式接受兩個迭代器，用來表示heap的首尾，如果并非首尾，該函式的執行結果不可預期，注意，排序過后，底層容器里的就不再是一個合法的heap了，
1 template <class RandomAccessIterator> 2 void sort_heap(RandomAccessIterator first, RandomAccessIterator last) { 3 // 以下，每執行一次 pop_heap()，極大值即被放在尾端， 4 // 尾端自減后（往左移動一格）再執行一次 pop_heap()，次極值又被放在新尾端，一直下去，最后即得 5 // 排序結果， 6 while (last - first > 1) 7 pop_heap(first, last--); // 每執行 pop_heap() 一次，操作范圍即退縮一格， 8 }
- make_heap
這個演算法用來將一段現有的資料轉化為一個heap，把一段資料轉換為heap的要點就是找到最后一個擁有子節點的節點，例如：
假設這是一個普通陣列，并無heap特性，那么要想其轉化為一個heap，切入點就是找到最后一個擁有子節點的節點，上圖而言就是E點，以E節點為首的子樹，對該子樹進行下沉操作和上浮操作，即先交換E跟J的值，再對J進行上浮操作，這樣以E節點為首的子樹就符合heap特性了，然后自減，來到了D節點（倒二擁有子節點的節點），同樣對以D節點為首的子樹進行下沉和上浮操作；然后再自減，直至到達根節點為止，這樣整個陣列就符合heap特性了，那么問題來了？怎么在一個普通陣列中找到最后一個擁有子節點的節點的索引值呢？可以證明的是，如果有一長度為n的陣列，那么最后一個擁有子節點的節點的索引值就是 (n - 2) / 2 ，這是陣列從索引0開始的情況，
1 // 將 [first,last) 排列為一個 heap， 2 template <class RandomAccessIterator> 3 inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) { 4 __make_heap(first, last, value_type(first), distance_type(first)); 5 } 6 7 template <class RandomAccessIterator, class T, class Distance> 8 void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*, 9 Distance*) { 10 if (last - first < 2) return; // 如果長度為 0 或 1，不必重新排列， 11 Distance len = last - first; 12 // 找出第一個需要重排的子樹頭部，以 parent 標示出，由于任何葉子節點都不需執行 13 // perlocate down（下沉），所以有以下計算， 14 Distance parent = (len - 2) / 2; 15 16 while (true) { 17 // 重排以 parent 為首的子樹，len 是為了讓 __adjust_heap() 判斷操作范圍 18 __adjust_heap(first, parent, len, T(*(first + parent))); 19 if (parent == 0) return; // 直至根節點，就結束， 20 parent--; // 未到根節點，就將（即將重排的子樹的）索引值向前一個節點 21 } 22 }
heap沒有迭代器，heap的所有元素都必須遵循特別的排列規則，所以heap不提供遍歷功能，也不提供迭代器，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/87986.html
標籤：C++
上一篇：Struct結構體