相关疑难解决方法(0)

我查看了C++ 0x标准,发现要求make_heap不应超过3*N比较.

即堆积无序集合可以在O(N)中完成

   /*  @brief  Construct a heap over a range using comparison functor.

为什么是这样？

来源没有给我任何线索(g ++ 4.4.3)

while(true)+ __parent == 0不是线索,而是对O(N)行为的猜测

template<typename _RandomAccessIterator, typename _Compare>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
          _Compare __comp)
{

  const _DistanceType __len = __last - __first;
  _DistanceType __parent = (__len - 2) / 2;
  while (true)
    {
      _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
      std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
                 __comp);
      if (__parent == 0)
        return;
      __parent--;
    }
}

__adjust_heap看起来像一个log N方法:

while ( __secondChild < (__len - 1) …

众所周知,heapsort的最坏情况运行时为Ω(n lg n),但我很难理解为什么会这样.特别是,heapsort的第一步(制作最大堆)需要时间Θ(n).然后是n次删除.我理解为什么每个堆删除需要时间O(lg n); 重新平衡堆涉及一个向下泡沫的操作,它在堆的高度花费时间O(h),并且h = O(lg n).但是,我没有看到为什么第二步应该采用Ω(n lg n).似乎任何单个堆出列都不一定会导致节点移动到顶部以一直向下冒泡到树中.

我的问题是 - 有没有人知道heapsort的最佳案例行为的良好下限证明？