SGI STL笔记（难缠的heap算法）

stl提供了四个heap的算法：push_heap, pop_heap, make_heap, sort_heap。sgi的stl还提供了一个扩展的is_heap用来判断两个随机iterator形成的区间的是否为heap。

本文分析其中的pop_heap算法和侯捷先生的《STL源码剖析》中关于该算法的一个错误。

代码取自sgi stl 3.3，为了阅读方便，对函数顺序重新进行了排列：

// pop_heap删除__first（实际是将__first与__last-1交换），然后调用__adjust_heap调整堆。
// [first, last)必须是合法的heap。
template <class _RandomAccessIterator>
inline void pop_heap(_RandomAccessIterator __first,
                     _RandomAccessIterator __last)
{
  // 因为需要通过iterator改变元素的值，所以需要符合mutable random access iterator.
  __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  // 要求iterator指向的元素类型是可比较的（不仅仅是可以判断小于这一种情况）。
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
                 _LessThanComparable);
  // 辅助函数
  __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
}
// 一个鸡肋的辅助函数

  template <class _RandomAccessIterator, class _Tp>

inline void
__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
               _Tp*)
{
  __pop_heap(__first, __last - 1, __last - 1,
             _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
}

template <class _RandomAccessIterator, class _Tp, class _Distance>
inline void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _RandomAccessIterator __result, _Tp __value, _Distance*)
{
  // result（也就是last-1）保存first指向的元素。
  *__result = *__first;
  // 将value（原last-1位置的元素）放到合适的位置
  __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
}

template <class _RandomAccessIterator, class _Distance, class _Tp>void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,              _Distance __len, _Tp __value){
  // 自顶向下寻找__value合适的位置。  _Distance __topIndex = __holeIndex;
  // 设置右孩子索引的位置（因为index是从0计数）  _Distance __secondChild = 2 * __holeIndex   2;  while (__secondChild < __len) {
    // 如果右孩子小于左孩子，就调整__secondChild    if (*(__first   __secondChild) < *(__first   (__secondChild - 1)))      __secondChild--;
    // 将较大的那个赋给双亲    *(__first   __holeIndex) = *(__first   __secondChild);
    // 调整子树索引    __holeIndex = __secondChild;
    // 指向新子树根节点的右孩子，这种写法真是disgusting，为什么不和上面保持一致呢？    __secondChild = 2 * (__secondChild   1);  }

  // 只有左孩子，没有右孩子  if (__secondChild == __len) {
    // 直接将左子树元素赋给根节点    *(__first   __holeIndex) = *(__first   (__secondChild - 1));
    // 调整子树索引
    __holeIndex = __secondChild - 1;  }

  // 将__value赋给__holeIndex所属位置，并调整所在子树。
  // 在《STL源码剖析》中，侯先生认为下面的语句可以改为*(__first   __holeIndex) = value
  // 但是这样一来，并不能保证value所在子树符合heap的约束。  __push_heap(__first, __holeIndex, __topIndex, __value);}

template <class _RandomAccessIterator, class _Distance, class _Tp>
void
__push_heap(_RandomAccessIterator __first,
            _Distance __holeIndex, _Distance __topIndex, _Tp __value)
{
  // 可以看出，依然需要根据value和*(__first   __parent)的关系来决定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;
}

举个简单的例子，依次将10、9、8、1、2、3、7 push到vector中，它显然是一个heap，如图（家里的电脑没有visio，列位将就着看吧）：

                               10
                            /      \
                           9         8
                         /   \     /   \
                        1     2   3     7

当调用pop_heap，并在__adjust_heap处使用直接赋值的话，是这样的结果：

                               9
                            /      \
                           2         8
                         /   \     /
                        1     7   3

显然，将(__last-1)处的元素赋给其他的位置时，并不能保证该元素一定小于其双亲节点。

sgi的heap算法实现调用层次过多，代码也不够紧凑，改日补充一个个人整理的简略的heap文件，方便大家理解和调试。

整理后的heap实现（没有重载less than运算符）

namespace simple
{

template <class random_iterator>
void push_heap(random_iterator first, random_iterator last)
{
    typedef typename iterator_traits<random_iterator>::value_type value_type;
    typedef typename iterator_traits<random_iterator>::difference_type difference_type;

    // less than 1 element.
    if ((last - 1) <= first)
    {
        return ;
    }

    // value of (last -1).
    value_type value = *(last - 1);
    // index of (last -1).
    difference_type i = (last - 1) - first;
    // parent of (last - 1).
    difference_type parent = (i - 1) / 2;

    while (i > 0 && first[parent] < value)
    {
        first[i] = first[parent];
        i = parent;
        parent = (i - 1) / 2;
    }

    first[i] = value;

    return ;
}

template <class random_iterator>
void pop_heap(random_iterator first, random_iterator last)
{
    typedef typename iterator_traits<random_iterator>::value_type value_type;
    typedef typename iterator_traits<random_iterator>::difference_type difference_type;

    // before value of first.
    value_type value = *first;
    // index of first.
    difference_type i = 0;
    // left child index of first.
    difference_type left = 1;
    // right child index of first.
    difference_type right = left + 1;
    difference_type n = last - first;

    // ajust the heap
    while (right < n)
    {
        if (first[left] > first[right])
        {
            first[i] = first[left];
            i = left;
        }
        else
        {
            first[i] = first[right];
            i = right;
        }
        left = i * 2 + 1;
        right = left + 1;
    }

    if (left < n)
    {
        first[i] = first[left];
        i = left;
    }

    // find a hole for (last - 1).
    first[i] = *(last - 1);

    // insert (last - 1) into range [first, first + i + 1).
    simple::push_heap(first, first + i + 1);

    // save the before value of first.
    *(last - 1) = value;

    return ;
}

template <class random_iterator>
void make_heap(random_iterator first, random_iterator last)
{
    if (last - first <= 1)
    {
        return ;
    }

    // insert range [i, last) into heap [first, i).
    // insert (last - 1) when i equal last.
    // i begin with first + 2 since [first, first + 1) is a valid heap.
    for (random_iterator i = first + 2; i <= last; ++i)
    {
        simple::push_heap(first, i);
    }

    return ;
}

template <class random_iterator>
void sort_heap(random_iterator first, random_iterator last)
{
    if (last - first <= 1)
    {
        return ;
    }

    // pop first into (i - 1).
    // i end with first + 2 since [first, first + 1) is a sorted range.
    for (random_iterator i = last; i >= first + 2; --i)
    {
        simple::pop_heap(first, i);
    }

    return ;
}

template <class random_iterator>
bool is_heap(random_iterator first, random_iterator last)
{
    typedef typename iterator_traits<random_iterator>::difference_type difference_type;

    difference_type n = last - first;
    difference_type i = 0;
    difference_type left = 1;

    while (left < n)
    {
        if (first[i] < first[left] || first[i] < first[left + 1])
        {
            return false;
        }
        ++i;
        left += 2;
    }

    return true;
}

}; // namespace simple