最大堆heap · STL源碼剖析

### 前言 ? 在STL中，heap并不是一種容器，而是一種算法，任何能夠提供隨機訪問迭代器的容器都能支持heap的操作。heap不需要遍歷內容，所以沒有屬于自己的迭代器。本文介紹的heap是基于vector容器的操作；有關[《最大堆和最小堆》](http://blog.csdn.net/chenhanzhun/article/details/21086973)的介紹請往前文查看。本文介紹的源碼出自SGI STL中<stl_heap.h>文件。 ### heap算法 ? 由于前面博文介紹過最大堆和最小堆的思想與實現步驟，這里不介紹了，直接進行源碼剖析： ~~~ //在STL中，heap不作為容器，只是提供了關于Heap操作的算法。 //heap沒有自己的迭代器，只要支持RandomAccessIterator的容器都可以作為Heap容器 #ifndef __SGI_STL_INTERNAL_HEAP_H #define __SGI_STL_INTERNAL_HEAP_H __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma set woff 1209 #endif // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap. //堆中添加元素；關于push_heap操作的原型有兩個 //注意: push_heap()操作之前必須保證新添加的元素已經加入到容器末尾 //********************************* //* 第一個版本使用operator<操作 //* template< class RandomIt > //* void push_heap( RandomIt first, RandomIt last ); //********************************* //* 第二個版本使用比較函數comp //* template< class RandomIt, class Compare > //* void push_heap( RandomIt first, RandomIt last,Compare comp ); //********************************* //* 比較函數comp：comparison function which returns ?true if the first argument is less than the second. //* The signature of the comparison function should be equivalent to the following: //* bool cmp(const Type1 &a, const Type2 &b); //********************************* template <class _RandomAccessIterator, class _Distance, class _Tp> void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __value) {//當前節點標號為__holeIndex- 1即為新插入元素標號，因為根節點標號是從0開始，所以這里要-1 _Distance __parent = (__holeIndex - 1) / 2;//找出當前節點的父節點 //尚未達到根節點,且所插入數據value大于父節點的關鍵字值 while (__holeIndex > __topIndex && *(__first + __parent) < __value) { *(__first + __holeIndex) = *(__first + __parent);//交換當前節點元素與其父節點元素的值 __holeIndex = __parent;//更新當前節點標號，上溯 __parent = (__holeIndex - 1) / 2;//更新父節點 } //持續達到根節點，或滿足heap的性質 *(__first + __holeIndex) = __value;//插入正確的位置 } template <class _RandomAccessIterator, class _Distance, class _Tp> inline void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance*, _Tp*) { //__last - __first) - 1表示插入后元素的個數，也是容器的最后一個下標數字 //新插入的元素必須位于容器的末尾 __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), _Tp(*(__last - 1))); } //第一個版本push_heap默認是operator<操作 template <class _RandomAccessIterator> inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable); __push_heap_aux(__first, __last, __DISTANCE_TYPE(__first), __VALUE_TYPE(__first)); } template <class _RandomAccessIterator, class _Distance, class _Tp, class _Compare> void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __value, _Compare __comp) { _Distance __parent = (__holeIndex - 1) / 2; while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) { *(__first + __holeIndex) = *(__first + __parent); __holeIndex = __parent; __parent = (__holeIndex - 1) / 2; } *(__first + __holeIndex) = __value; } template <class _RandomAccessIterator, class _Compare, class _Distance, class _Tp> inline void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _Distance*, _Tp*) { __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), _Tp(*(__last - 1)), __comp); } //第二個版本push_heap自定義比較操作函數comp template <class _RandomAccessIterator, class _Compare> inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __push_heap_aux(__first, __last, __comp, __DISTANCE_TYPE(__first), __VALUE_TYPE(__first)); } //注意: pop_heap()操作, 執行完操作后要自己將容器尾元素彈出 //default (1): // template <class RandomAccessIterator> // void pop_heap (RandomAccessIterator first, RandomAccessIterator last); //custom (2): // template <class RandomAccessIterator, class Compare> // void pop_heap (RandomAccessIterator first, RandomAccessIterator last, // Compare comp); //************************************* template <class _RandomAccessIterator, class _Distance, class _Tp> void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value) { _Distance __topIndex = __holeIndex;//根節點標號 _Distance __secondChild = 2 * __holeIndex + 2;//獲取子節點 while (__secondChild < __len) {//若子節點標號比總的標號數小 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; } __push_heap(__first, __holeIndex, __topIndex, __value); } template <class _RandomAccessIterator, class _Tp, class _Distance> inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __value, _Distance*) { *__result = *__first;//把原始堆的根節點元素放在容器的末尾 //調整剩下的節點元素，使其成為新的heap __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value); } template <class _RandomAccessIterator, class _Tp> inline void __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) { __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __DISTANCE_TYPE(__first)); } template <class _RandomAccessIterator> inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable); __pop_heap_aux(__first, __last, __VALUE_TYPE(__first)); } template <class _RandomAccessIterator, class _Distance, class _Tp, class _Compare> void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value, _Compare __comp) { _Distance __topIndex = __holeIndex; _Distance __secondChild = 2 * __holeIndex + 2; while (__secondChild < __len) { if (__comp(*(__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; } __push_heap(__first, __holeIndex, __topIndex, __value, __comp); } template <class _RandomAccessIterator, class _Tp, class _Compare, class _Distance> inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __value, _Compare __comp, _Distance*) { *__result = *__first; __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value, __comp); } template <class _RandomAccessIterator, class _Tp, class _Compare> inline void __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*, _Compare __comp) { __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp, __DISTANCE_TYPE(__first)); } template <class _RandomAccessIterator, class _Compare> inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp); } //創建堆 //default(1): // template <class RandomAccessIterator> // void make_heap (RandomAccessIterator first, RandomAccessIterator last); //custom (2): // template <class RandomAccessIterator, class Compare> // void make_heap (RandomAccessIterator first, RandomAccessIterator last,Compare comp ); //**************************************** template <class _RandomAccessIterator, class _Tp, class _Distance> void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*, _Distance*) { if (__last - __first < 2) return; _Distance __len = __last - __first; _Distance __parent = (__len - 2)/2; while (true) { __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent))); if (__parent == 0) return; __parent--; } } template <class _RandomAccessIterator> inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable); __make_heap(__first, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } template <class _RandomAccessIterator, class _Compare, class _Tp, class _Distance> void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _Tp*, _Distance*) { if (__last - __first < 2) return; _Distance __len = __last - __first; _Distance __parent = (__len - 2)/2; while (true) { __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)), __comp); if (__parent == 0) return; __parent--; } } template <class _RandomAccessIterator, class _Compare> inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __make_heap(__first, __last, __comp, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } //排序堆里面的內容 //default(1): // template <class RandomAccessIterator> // void sort_heap (RandomAccessIterator first, RandomAccessIterator last); //custom (2): // template <class RandomAccessIterator, class Compare> // void sort_heap (RandomAccessIterator first, RandomAccessIterator last, // Compare comp); //************************************** template <class _RandomAccessIterator> void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable); while (__last - __first > 1) pop_heap(__first, __last--);//每次取出根節點元素，直到heap為空 } template <class _RandomAccessIterator, class _Compare> void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); while (__last - __first > 1) pop_heap(__first, __last--, __comp); } #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma reset woff 1209 #endif __STL_END_NAMESPACE #endif /* __SGI_STL_INTERNAL_HEAP_H */ // Local Variables: // mode:C++ // End: ~~~ ? 舉例說明heap的操作： ~~~ #include <iostream> // std::cout #include <algorithm> // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap #include <vector> // std::vector int main () { int myints[] = {10,20,30,5,15}; std::vector<int> v(myints,myints+5); std::make_heap (v.begin(),v.end()); std::cout << "initial max heap : " << v.front() << '\n'; std::pop_heap (v.begin(),v.end()); v.pop_back(); std::cout << "max heap after pop : " << v.front() << '\n'; v.push_back(99); std::push_heap (v.begin(),v.end()); std::cout << "max heap after push: " << v.front() << '\n'; std::sort_heap (v.begin(),v.end()); std::cout << "final sorted range :"; for (unsigned i=0; i<v.size(); i++) std::cout << ' ' << v[i]; std::cout << '\n'; return 0; } Output: initial max heap : 30 max heap after pop : 20 max heap after push: 99 final sorted range : 5 10 15 20 99 ~~~ 參考資料：《STL源碼剖析》侯捷