_RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __value, _Compare __comp, _Distance*) { *__result = *__first; __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value, __comp); } template
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
inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp); } template
void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*, _Distance*) { if (__last - __first < 2) return; _Distance __len = __last - __first; ///由于__adjust_heap的要求,必须从最底层开始逐层向上调整. _Distance __parent = (__len - 2)/2; ///此时它的两个孩子分别为__len-1,len while (true) { __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent))); if (__parent == 0) return; __parent--; } } template
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
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
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)); } template
void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable); ///由于pop_heap函数并未正真将结点删除,此函数得以实现 while (__last - __first > 1) pop_heap(__first, __last--); } template
void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); while (__last - __first > 1) pop_heap(__first, __last--, __comp); }
|