///STL中使用的是大顶堆
/// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
template 
  
   
void
__push_heap(_RandomAccessIterator __first,
            _Distance __holeIndex, _Distance __topIndex, _Tp __value)
{
  _Distance __parent = (__holeIndex - 1) / 2;

  ///逐层上溯,查找要插入的位置
  while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
    *(__first + __holeIndex) = *(__first + __parent);
    __holeIndex = __parent;
    __parent = (__holeIndex - 1) / 2;
  }

  ///找到位置,插入
  *(__first + __holeIndex) = __value;
}

template 
   
     inline void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance*, _Tp*) { __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), _Tp(*(__last - 1))); } template 
    
      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 
     
       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 
      
        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); } template 
       
         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)); } ///将__holeIndex处的结点摘掉,并保持合法的大顶堆状态,然后插入__value ///执行此函数前,必须保证以__holeIndex为根节点构成的完全二叉树符合大顶堆的定义 template 
        
          void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value) { _Distance __topIndex = __holeIndex; _Distance __secondChild = 2 * __holeIndex + 2; ///向下遍历,从__holeIndex中找出两个孩子中较大的一个填入__holeIndex,并令__holeIndex ///等于该孩子,继续执行,直至__holeIndex无孩子或者只有一个孩子(为了占被摘取的那个节点的位置) while (__secondChild < __len) { if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) __secondChild--; *(__first + __holeIndex) = *(__first + __secondChild); __holeIndex = __secondChild; __secondChild = 2 * (__secondChild + 1); } if (__secondChild == __len) { ///__holeIndex只有一个孩子,补充上去 *(__first + __holeIndex) = *(__first + (__secondChild - 1)); __holeIndex = __secondChild - 1; } ///至此,大顶堆合法,插入__value __push_heap(__first, __holeIndex, __topIndex, __value); } template 
         
           inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __value, _Distance*) { ///该函数并未删除弹出的那个元素,而只是将它移动到最后面 *__result = *__first; __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value); } template 
          
            inline void __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) { __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __DISTANCE_TYPE(__first)); } template 
           
             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 
            
              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 
             
               inline void __pop_heap(_RandomAccessIterator __first,