【heap】是算法不是容器哦

前面是一些小Tips和关键点，以及代码里不好理解的点，后面是源码，重要的函数全部都写了满满的注释嘿嘿嘿！
为什么是这种形式呢，因为看书的时候就是讲解源码的，于是顺着读代码的时候就加了注释。

heap不归属于STL容器组件，是扮演priority queue（允许任何次序推入容器内，但取出一定是从优先权最高的元素开始取）的助手。binary max heap就适合做它的底层机制。关键：内部排序！

binary heap：完全二叉树的形态（好处：可用array存储所有节点，左右子节点为2i和2i+1，父节点i/2，称为隐式表述法）。故heap是一个array和一组heap算法，为了动态改变大小，用vector代替array。

heap分为max-heap和min-heap，STL默认前者。不提供遍历，故没有迭代器。

push_heap：上溯程序

pop_heap：去掉根节点，下溯。注意：pop取走根节点的操作实际上是将其移至底部容器vector的最后一个元素，为了维持二叉树，需要将下一层的最右节点拿掉，补充到上面的空缺。

调用方法：（以算法形式呈现）vector< int> a; make_heap(a.begin(),a.end())；
a.push_back(7); push_heap(a.begin(),a.end());
pop_heap(a.begin(),a.end());
sort_heap(a.begin(),a.end());

#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

//这组push_back()不允许指定“大小比较标准”
//first是头结点存放的下标（并不默认就是0）
template 
void __push_heap(RandomAccessIterator first, Distance holeIndex,
                 Distance topIndex, T value) {
  Distance parent = (holeIndex - 1) / 2; // 找出父节点
  while (holeIndex > topIndex && *(first + parent) < value) {
  // 当尚未到达顶端且父节点小于新值，fisrt是起始点
    *(first + holeIndex) = *(first + parent);//令洞值为父值
    holeIndex = parent;//调整洞号，向上提升至父节点
    parent = (holeIndex - 1) / 2;//新洞的父节点
  }    //持续至顶端或满足heap次序特性为止
  *(first + holeIndex) = value;//令洞值为新值，完成插入操作
}

template 
inline void __push_heap_aux(RandomAccessIterator first,
                            RandomAccessIterator last, Distance*, T*) {
  __push_heap(first, Distance((last - first) - 1), Distance(0), 
              T(*(last - 1)));
   //容器的最尾端为第一个洞号
}

template 
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  //注意此函数被调用时新元素应该已经置于底部容器的最尾端
  __push_heap_aux(first, last, distance_type(first), value_type(first));
}

//这里是指定compare排序方式的push
template 
void __push_heap(RandomAccessIterator first, Distance holeIndex,
                 Distance topIndex, T 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*, T*) {
  __push_heap(first, Distance((last - first) - 1), Distance(0), 
              T(*(last - 1)), comp);
}

template 
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,
                      Compare comp) {
  __push_heap_aux(first, last, comp, distance_type(first), value_type(first));
}

template 
void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
                   Distance len, T 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 
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                       RandomAccessIterator result, T value, Distance*) {
  *result = *first;//设定尾值为首值，于是尾值即为欲求结果
   //可由客户端稍后用pop_back取出尾值
  __adjust_heap(first, Distance(0), Distance(last - first), value);//调整，洞号为0，调整值为value（尾值）
}

template 
inline void __pop_heap_aux(RandomAccessIterator first,
                           RandomAccessIterator last, T*) {
  __pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first));
//根据heap次序，pop的为底层容器的首元素，首先设定欲调整值为尾值
//然后将首值调至尾结点(故迭代器result设为last-1)，然后调整first, last - 1
}

template 
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __pop_heap_aux(first, last, value_type(first));
}

template 
void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
                   Distance len, T 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, RandomAccessIterator last,
                       RandomAccessIterator result, T 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, T*, Compare comp) {
  __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
             distance_type(first));
}

template 
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp) {
    __pop_heap_aux(first, last, value_type(first), comp);
}

template 
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
                 Distance*) {
  if (last - first < 2) return;
  Distance len = last - first;
  Distance parent = (len - 2)/2;
    
  while (true) {
    __adjust_heap(first, parent, len, T(*(first + parent)));
    if (parent == 0) return;
    parent--;
  }
}

template 
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __make_heap(first, last, value_type(first), distance_type(first));
}

template 
void __make_heap(RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp, T*, Distance*) {
  if (last - first < 2) return;//长度为0或1
  Distance len = last - first;
  //找出第一个需要重排的子树头部（第一个非根节点）
  Distance parent = (len - 2)/2;
    
  while (true) {
    //len是为了让__adjust_heap()判断操作范围
    __adjust_heap(first, parent, len, T(*(first + parent)), comp);
    if (parent == 0) return;//根节点结束
    parent--;//向前
  }
}

template 
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last,
                      Compare comp) {
  __make_heap(first, last, comp, value_type(first), distance_type(first));
}

template 
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  while (last - first > 1) pop_heap(first, last--);
}

//持续对heap做pop操作，每次将操作范围从后往前缩减一个元素（pop把元素放尾部）
//完成后就有了一个递增序列
template 
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
               Compare comp) {
  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