std::make_heap如何实现，同时最多只进行3N次比较？

Question

std::make_heap如何实现，同时最多只进行3N次比较？

29

我查阅了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) / 2)
{
    __secondChild = 2 * (__secondChild + 1);

对我来说，这是标准的O(log N)。

  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 <= 3N的线索。
编辑：

实验结果:

这个实际的实现：

用 <2N 来进行堆化（heapifying）
用<1.5N来反向堆化（heapifying）。

- Captain Giraffe

请说明并解释您发布的来源支持您的猜想的原因。我不是说它不支持，只是我懒得翻阅它。 - user2100815

1

你可能想看一下Wikipedia上关于为什么heapify是O(n)的解释。 - trutheality

@truth 那个3的因子从哪里来的？ - Captain Giraffe

1

@Mike：它在“构建堆”部分。 - trutheality

@trutheality 啊，这个方程的大局观... 哦天啊。+1 不拿这个开玩笑。 - Mike Miller

显示剩余2条评论

2个回答

17

@templatetypedef 已经为为何 build_heap 的渐近运行时间为 O(n) 给出了很好的答案。此外，第二版CLRS第6章中也有一个证明。

至于为什么C++标准规定最多只能使用3n次比较：

通过我的实验（见下面的代码），似乎实际上只需要不到2n次比较。事实上，这些讲义包含一个证明，即

 build_heap 仅使用 2（n-⌈log n⌉）次比较。
标准中的限制似乎比所需的限制更宽松。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

- hammar

1

很高兴看到Python被应用在意料之外的地方。感谢你提供示例代码！ - Noctis Skytower

谢谢您发布讲义笔记。第7页展示了一个非常简明的证明。 - foges

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

使用巧妙的算法和分析，可以在O（n）时间内创建一个包含n个元素的二叉堆。以下是如何工作的简要介绍，假设您具有显式节点和显式左右子指针，但是一旦将其压缩到数组中，此分析仍然完全有效。

算法如下。首先将大约一半的节点视为单例最大堆-因为只有一个元素，所以仅包含该元素的树必须自动成为最大堆。现在，将这些树两两配对。对于每对树，取一个尚未使用过的值并执行以下算法：

1. 将新节点设置为堆的根，使其左右子指针指向两个最大堆。 2. 当此节点的子节点较大时，与其较大的子节点交换。我的说法是，此过程最终产生一个包含两个输入最大堆元素的新最大堆，并且它在O（h）时间内完成，其中h是两个堆的高度。证明是对堆的高度进行归纳。作为基本情况，如果子堆的大小为零，则算法立即以单例最大堆终止，并且在O（1）时间内完成。对于归纳步骤，请假设对于某个h，此过程适用于大小为h的任何子堆，并考虑在两个大小为h + 1的堆上执行它时会发生什么。当我们添加新根以连接大小为h + 1的两个子树时，有三种可能性：

新根比两个子树的根都大。在这种情况下，我们有一个新的最大堆，因为根比任何子树中的节点都大（由传递性可得）。
新根比其中一个子节点大，比另一个子节点小。然后我们将根与较大的子节点交换，并再次递归执行此过程，使用旧根和子树的两个子树，每个子树的高度都为h。根据归纳假设，这意味着我们交换进入的子树现在是最大堆。因此，由于新根比我们交换的子树中的所有内容都大（因为它比添加的节点大，并且已经比该子树中的所有内容大），并且也比另一个子树中的所有内容都大（因为它比根大，而根比另一个子树中的所有内容都大），因此总体堆是最大堆。
新根比其两个子节点都小。然后通过稍微修改上述分析的版本，我们可以证明得到的树确实是堆。

此外，由于在每个步骤中，子堆的高度都会减少一，因此此算法的总运行时间必须为O(h)。

此时，我们有一个简单的堆制作算法：

取出大约一半的节点并创建单例堆。(您可以明确计算需要多少个节点，但大约是一半)。
将这些堆成对，然后使用未使用的节点和上述过程合并它们。
重复步骤2，直到只剩下一个堆。

由于在每个步骤中，我们知道到目前为止我们拥有的堆都是有效的最大堆，因此最终会产生一个有效的整体最大堆。如果我们聪明地选择要创建多少个单例堆，那么最终会创建一个完全二叉树。

然而，似乎这应该在O(n lg n)时间内运行，因为我们执行O(n)次合并，每次合并的运行时间为O(h)，在最坏情况下，我们合并的树的高度为O(lg n)。但是这个界限并不紧密，通过更精确地分析，我们可以做得更好。

特别是，让我们考虑合并的所有树的深度。大约一半的堆深度为零，然后剩下的一半深度为一，然后剩下的一半深度为二，依此类推。如果我们总结一下，得到的总和为

0 * n/2 + 1 * n/4 + 2 * n/8 + ... + nk/(2^k) = Σ_{k = 0}^{⌈log n⌉} (nk / 2^k) = n Σ_{k = 0}^{⌈log n⌉} (k / 2^k+1)

这个式子上界了交换的次数。每次交换最多需要两次比较。因此，如果我们将上述总和乘以二，我们得到以下总和，它上界了交换的次数：

n Σ_{k = 0}^∞ (k / 2^k)

这里的总和是 0 / 2⁰ + 1 / 2¹ + 2 / 2² + 3 / 2³ + ...。这是一个著名的总和，可以用多种不同的方法进行评估。其中一种方法在这些讲座幻灯片中，幻灯片45-47页给出。结果正好为2n，这意味着最终进行的比较次数肯定被上界3n限制。

希望这能帮到您！