pop_heap算法 （将根节点置于容器尾部后重调heap结构）

算法描述

置根节点于容器尾部，并调整heap结构使其满足max-heap.

算法的核心是根节点为空洞后heap结构的调整，而不是取最大值（最大值就是根节点）！

根节点为空洞后，为了满足max-heap结构，要割舍最下层最右边的叶节点，重新安插它的位置，即调整heap结构。

注：根节点即最大元素只是被置放于底部容器的最尾端，尚未被取走，可通过back()操作取其值，可通过pop_back()操作移除。

如何重新调整结构呢？

根节点为空洞后，执行percolate down（下溯）程序：将空洞节点和其较大子节点对调，并持续下放，直到叶节点为止。

然后将被割舍的节点至于“已达到叶层的空洞节点”，再对它进行一次percolate up（上溯）程序，即可。

// 下面的result就是根节点！并未被取走。

// 以下這組 __pop_heap() 不允許指定「大小比較標準」
template <class RandomAccessIterator, class T, class Distance>
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);
  // 以上欲重新調整 heap，洞號為 0（亦即樹根處），欲調整值為 value（原尾值）。
}

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動作的結果
  // 應為底層容器的第一個元素。因此，首先設定欲調整值為尾值，然後將首值調至 
  // 尾節點（所以以上將迭代器result設為last-1）。然後重整 [first, last-1)，
  // 使之重新成一個合格的 heap。
}

 

/*下面才是算法核心*/

根节点为空洞后，执行percolate down（下溯）程序：将空洞节点和其较大子节点对调，并持续下放，直到叶节点为止。

然后将被割舍的节点至于“已达到叶层的空洞节点”，再对它进行一次percolate up（上溯）程序，即可。

void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
                   Distance len, T value) {
  Distance topIndex = holeIndex;
  Distance secondChild = 2 * holeIndex + 2;	// 洞節點之右子節點
  while (secondChild < len) {
    // 比較洞節點之左右兩個子值，然後以 secondChild 代表較大子節點。
    if (*(first + secondChild) < *(first + (secondChild - 1)))
      secondChild--;   
    // Percolate down：令較大子值為洞值，再令洞號下移至較大子節點處。
    *(first + holeIndex) = *(first + secondChild);  
    holeIndex = secondChild;
    // 找出新洞節點的右子節點
    secondChild = 2 * (secondChild + 1);
  }
  if (secondChild == len) { // 沒有右子節點，只有左子節點
    // Percolate down：令左子值為洞值，再令洞號下移至左子節點處。
    *(first + holeIndex) = *(first + (secondChild - 1));
    holeIndex = secondChild - 1;
  }
  // 將欲調整值填入目前的洞號內。注意，此時肯定滿足次序特性。
  // 依侯捷之見，下面直接改為 *(first + holeIndex) = value; 應該可以。

  // fys：侯捷说直接改是不可以的，在侯捷新书里澄清了此处。
  __push_heap(first, holeIndex, topIndex, value);
}