如何能标准:: make_heap实现最多3N的比较，同时使？ [英] How can std::make_heap be implemented while making at most 3N comparisons?

问题描述

我看着到的C ++ 0x标准，发现make_heap应该做的不超过3 * N比较的要求。

I looked in to the C++0x standard and found the requirement that make_heap should do no more than 3*N comparisons.

即。 heapify的无序集合可以在O（N）来完成

I.e. heapify an unordered collection can be done in O(N)

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

这是为什么？

Why is this?

该人士没有给我的线索（G ++ 4.4.3）

The source gives me no clues (g++ 4.4.3)

的，而（真）+ __parent == 0并不线索，而是代表O猜测（N）的行为

The while (true) + __parent == 0 are not clues but rather a guess for O(N) behaviour

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看起来像一个日志N法：

__adjust_heap looks like a log N method:

while ( __secondChild < (__len - 1) / 2)
{
    __secondChild = 2 * (__secondChild + 1);

是一个沼泽标准日志N至我。

Is a bog standard log N to me.

  template<typename _RandomAccessIterator, typename _Distance,
       typename _Tp, typename _Compare>
    void
    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
          _Distance __len, _Tp __value, _Compare __comp)
    {
      const _Distance __topIndex = __holeIndex;
      _Distance __secondChild = __holeIndex;
      while (__secondChild < (__len - 1) / 2)
      {
        __secondChild = 2 * (__secondChild + 1);
          if (__comp(*(__first + __secondChild),
             *(__first + (__secondChild - 1))))
          __secondChild--;
          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
          __holeIndex = __secondChild;
      }
      if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
      {
        __secondChild = 2 * (__secondChild + 1);
        *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
                             + (__secondChild - 1)));
        __holeIndex = __secondChild - 1;
      }
      std::__push_heap(__first, __holeIndex, __topIndex, 
               _GLIBCXX_MOVE(__value), __comp);      
      }

任何线索，这是为什么O＆LT; pciated = 3N将AP $ P $
编辑：

Any clues to why this is O <= 3N will be appreciated.

实验结果：

这实际实现使用

• ＆LT; 2N为heapifying堆比较
• ＆LT; 1.5N在相反的顺序heapifying堆。

推荐答案

@templatetypedef已经给出的一个很好的回答为什么 build_heap 是 O（N）的。也有在 CLRS 时，第二版第6章一个证明。

@templatetypedef has already given a good answer for why the asymptotic run time of build_heap is O(n). There is also a proof in chapter 6 of CLRS, 2nd edition.

至于为什么C ++标准要求，在大多数的 3N 的比较是使用：

As for why the C++ standard requires that at most 3n comparisons are used:

这是我的实验（见下文code），看来确实低于的 2N 的需要比较。事实上，这些讲义包含一个证明 build_heap 只使用 2（N-⌈logn⌉）的比较。

From my experiments (see code below), it appears that actually less than 2n comparisons are needed. In fact, these lecture notes contain a proof that build_heap only uses 2(n-⌈log n⌉) comparisons.

绑定的从标准似乎比​​需要更多的慷慨。

The bound from the standard seems to be more generous than required.

def parent(i):
    return i/2

def left(i):
    return 2*i

def right(i):
    return 2*i+1

def heapify_cost(n, i):
    most = 0
    if left(i) <= n:
        most = 1 + heapify_cost(n, left(i))
    if right(i) <= n:
        most = 1 + max(most, heapify_cost(n, right(i)))
    return most

def build_heap_cost(n):
    return sum(heapify_cost(n, i) for i in xrange(n/2, 1, -1))

的一些结果：

n                     10  20  50  100  1000  10000
build_heap_cost(n)     9  26  83  180  1967  19960

这篇关于如何能标准:: make_heap实现最多3N的比较，同时使？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！