学步园

       堆一般是一种隐式表述（implicit representation），简单的说堆是由另外一种容器实现的。由于堆中的操作都基于搜寻父节点，子节点。如果用数组的话，那么不需要额外的存储空间就可以轻松实现。左子节点标号=父节点标号*2+1；右子节点标号=父节点标号*2+2；父节点标号=（子节点标号-1）/2。如果在用一种小技巧，将标号0处元素保留（或设为无限大（小）值），从而忽略根节点的话，计算式将改为左子节点标号
= 父节点标号*2；右子节点标号 = 父节点标号*2+1；父节点标号 = 子节点标号/2。另外堆要求数组长度动态，所以用vector实现。

       接下来分析最大堆的各种操作（最小堆类似）。理解了上溯和下溯基本堆的操作都可以理解了。

push_heap()是在一个最大堆中插入元素，元素先插在最尾端，然后进行上溯。所以复杂度为O（lgn）

__adjust_heap()这个函数维持最大堆的性质，进行下溯就可以了,而STL中不知道为什么最终的赋值采用了插入操作再做一次上溯。但不管怎么样复杂度为O（lgn）。但是这里还有个问题，为什么只进行下溯就可以了？因为__adjust_heap（）是个内部函数，客户端无法调用，看下面其他函数调用__adjust_heap()

的时刻就清楚了。

pop_heap()弹出最大元素，实现的方式就是先保存尾元素值，然后根节点值赋给尾元素，根变为一个洞然后洞号和值（尾值）都有了，调用__adjust_heap()重整堆，这里必然是下溯，符合__adjust_heap()算法。所以复杂度为O（lgn）。注意pop_heap()只是移动元素，并不弹出，要继续调用vector：：push_back()。

make_heap()建堆是在未排序的数组上进行的，由最后一个非叶子节点开始，循环调用__adjust_heap()此时是往上循环的，所以只要进行下溯，符合__adjust_heap()算法。这里要分析make_heap()的复杂度，简单地想线性元素个数调用__adjust_heap()复杂度因为O（nlgn）。这是一个上界，但是不够精确，因为调用__adjust_heap()的节点高度不一样。这里要提到一个小性质：一个n元素堆的高度为lgn，在任意高度h上，至多有n/(2^h+1)（取上界）个节点。那么复杂度为n/(2^h+1)O(h)在0至lgn间求和，最终得O（n）。

sort_heap()很简单，从头至尾循环调用pop_heap()，复杂度O（nlgn）。

   以下见STL源码，分析已有详细注释。

//以下这组 push_heap()不允许指定“大小比较标准”
template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  // 注意！！！此函数调用的时候，元素以至于容器尾端。
  __push_heap_aux(first, last, distance_type(first), value_type(first));
}

template <class RandomAccessIterator, class Distance, class T>
inline void __push_heap_aux(RandomAccessIterator first,
                            RandomAccessIterator last, Distance*, T*) {
  __push_heap(first, Distance((last - first) - 1), Distance(0), 
              T(*(last - 1)));
  // 以上根据 implicit representation heap 的结构特性：新值必至于底层
  // 容器的最尾端，此即第一个洞号：(last-first)–1。
}

template <class RandomAccessIterator, class Distance, class T>
void __push_heap(RandomAccessIterator first, Distance holeIndex,
                 Distance topIndex, T value) {
  Distance parent = (holeIndex - 1) / 2;	// 父节点标号
  while (holeIndex > topIndex && *(first + parent) < value) {
    // 尚未到达顶端且父节点值小于新值（这不符合最大堆的特性）
    // 由于以上使用 operator<，可知 STL heap 是一种max-heap
    *(first + holeIndex) = *(first + parent);	
    holeIndex = parent; // 上溯：父节点标号为洞号
    parent = (holeIndex - 1) / 2;	// 新洞的父节点标号
  }    // 持续至顶端或满足最大堆特性为止。
  *(first + holeIndex) = value;	// 另洞值为新值，完成拆入操作。
}

// 以下这组 push_heap()允许指定“大小比较标准”
template <class RandomAccessIterator, class Compare>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,
                      Compare comp) {
  __push_heap_aux(first, last, comp, distance_type(first), value_type(first));
}

template <class RandomAccessIterator, class Compare, class Distance, class T>
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 <class RandomAccessIterator, class Distance, class T, class Compare>
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;
}



// 以下这个 __adjust_heap()不允许指定“大小比较标准”
template <class RandomAccessIterator, class Distance, class T>
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--; //左子结点大，洞号为左子结点标号
    // Percolate down：另较大值为洞值，再令洞号下移为较大值标号
    *(first + holeIndex) = *(first + secondChild);  
    holeIndex = secondChild;
    // 找出新洞结点的右子节点
    secondChild = 2 * (secondChild + 1);
  }
if (secondChild == len) { // 因为secondChild为标号，而标号等于长度的话
  //那么就是该洞节点无右子结点但有左子结点
    // Percolate down
    *(first + holeIndex) = *(first + (secondChild - 1));
    holeIndex = secondChild - 1;
  }
// 将欲调整值填入洞号内。
//!!!!!!注意，此时肯定满足次序特性。
//下面直接改为 *(first + holeIndex) = value; 应该可以。
//这里__push_heap的话还要进行一次上溯
  __push_heap(first, holeIndex, topIndex, value);
}

// 以下这个 __adjust_heap()允许指定“大小比较标准”
template <class RandomAccessIterator, class Distance, class T, class Compare>
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);
}
// 以下这组pop_heap()不允许指定“大小比较标准”
template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __pop_heap_aux(first, last, value_type(first));
}

template <class RandomAccessIterator, class T>
inline void __pop_heap_aux(RandomAccessIterator first,
                           RandomAccessIterator last, T*) {
  __pop_heap(first, last-1, last-1, T(*(last-1)), distance_type(first));
  // 以上，根据 implicit representation heap 的次序特性，pop动作的结果
  // 应为底层容器的第一个值（标号0的根节点）。因此，首先设定欲调整的值是尾值，然後將首值调至
// 尾节点（所以以上将迭代器result设为last-1）。然后重整 [first, last-1)。这里有个细节
// 因为最后要重整，需要传入重整节点值，第四个参数，生成了一个原堆尾节点值的临时变量！！
}

template <class RandomAccessIterator, class T, class Distance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                       RandomAccessIterator result, T value, Distance*) {
  *result = *first; //设定尾值为根节点值，即为欲求结果
// pop_heap是没有返回值的。之后可由客户端以底层容器的pop_back() 取出尾值。
  __adjust_heap(first, Distance(0), Distance(last - first), value);
  // 以上重新调整 heap，洞号为 0（根节点），欲调整值为value（原尾值）。
}


// 以下这组 __pop_heap()允许指定“大小比较标准”
template <class RandomAccessIterator, class T, class Compare, class Distance>
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 <class RandomAccessIterator, class T, class Compare>
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 <class RandomAccessIterator, class Compare>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp) {
    __pop_heap_aux(first, last, value_type(first), comp);
}

// 以下这组 make_heap()不允许指定“大小比较标准”。
// 将 [first,last) 排列为一个max-heap。
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __make_heap(first, last, value_type(first), distance_type(first));
}

template <class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
                 Distance*) {
  if (last - first < 2) return;	// 如果長度為 0 或 1，不必重新排列。
  Distance len = last - first;
//找出第一個需要重排的子樹頭部，以 parent 標示出。
//由于任何叶子节点都不需执行下溯
  //所以有以下计算，parent 命名不佳，名为 holeIndex 更好。
  Distance parent = (len - 2)/2; 
//为什么是这个算式？？由于STL中第一个节点的标号为0，所以求节点的父节点算式为（n-1）/2，
//而这里len为长度，len-1是最后一个叶子节点的标号。
  while (true) {
    // 重排以parent为首的子树。len 是为了让 __adjust_heap() 判断操作范围
    __adjust_heap(first, parent, len, T(*(first + parent)));
    if (parent == 0) return;	// 走完根节点，就结束。
    parent--;					
  }
}


// 以下这组 make_heap()允许指定“大小比较标准”。
template <class RandomAccessIterator, class Compare>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last,
                      Compare comp) {
  __make_heap(first, last, comp, value_type(first), distance_type(first));
}

template <class RandomAccessIterator, class Compare, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp, 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)), comp);
    if (parent == 0) return;
    parent--;
  }
}


// 以下这个 sort_heap()不允许指定“大小比较标准”
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  // 以下，每执行一次 pop_heap()，极值（在STL heap中为极大值）即被放在尾端。
  // 扣除尾端再执行一次 pop_heap()，次极值又被放在新尾端。一直下去，最后即得
  // 排序结果。
  while (last - first > 1)
     pop_heap(first, last--); // 每执行 pop_heap() 一次，操作范围即退缩一格。
}

// 以下这个 sort_heap()允许指定“大小比较标准”
template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
               Compare comp) {
  while (last - first > 1)
     pop_heap(first, last--, comp);
}