29

我查看了 C++0x 标准，发现 make_heap 的比较不能超过 3*N 的要求。

即 heapify 一个无序的集合可以在 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);

对我来说是一个沼泽标准日志 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 比较堆的堆
  • <1.5N 以相反的顺序堆积堆。
4

2 回答 2

53

使用巧妙的算法和巧妙的分析，可以在 O(n) 时间内创建一个包含 n 个元素的二进制堆。在接下来的内容中，我将讨论它是如何工作的，假设您有显式节点和显式左右子指针，但是一旦将其压缩到数组中，这种分析仍然完全有效。

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

  1. 使新节点成为堆的根，使其左右子指针指向两个最大堆。

  2. 虽然此节点有一个比它大的子节点，但将子节点与其更大的子节点交换。

我的主张是，这个过程最终会产生一个新的最大堆，其中包含两个输入最大堆的元素，并且它在 O(h) 时间内完成，其中 h 是两个堆的高度。证明是对堆高度的归纳。作为基本情况，如果子堆的大小为零，则算法立即以单例最大堆终止，并且在 O(1) 时间内完成。对于归纳步​​骤，假设对于某些 h，此过程适用于任何大小为 h 的子堆，并考虑在两个大小为 h + 1 的堆上执行它时会发生什么。当我们添加一个新根以将两个大小为的子树连接在一起时h + 1，有三种可能：

  1. 新根大于两个子树的根。然后在这种情况下，我们有一个新的最大堆，因为根大于任一子树中的任何节点（通过传递性）

  2. 新的根比一个孩子大，比另一个小。然后我们将根与较大的子子交换，并再次递归执行此过程，使用旧根和子的两个子树，每个子树的高度为 h。根据归纳假设，这意味着我们交换的子树现在是一个最大堆。因此整个堆是一个最大堆，因为新的根比我们交换的子树中的所有东西都大（因为它比我们添加的节点大并且已经比那个子树中的所有东西都大），而且它也比所有东西都大在另一个子树中（因为它大于根并且根大于另一个子树中的所有内容）。

  3. 新的根比它的两个孩子都小。然后使用上面分析的稍微修改的版本，我们可以证明生成的树确实是一个堆。

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

至此，我们有了一个简单的堆算法：

  1. 取大约一半的节点并创建单例堆。（您可以在这里明确计算需要多少节点，但大约是一半）。
  2. 将这些堆配对，然后使用未使用的节点之一和上述过程将它们合并在一起。
  3. 重复步骤 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 ⌈日志 n⌉ (k / 2 k+1 )

这是交换次数的上限。每次交换最多需要两次比较。因此，如果我们将上述总和乘以 2，我们会得到以下总和，它是交换次数的上限：

n Σ k = 0 ∞ (k / 2 k )

这里的求和是求和 0 / 2 0 + 1 / 2 1 + 2 / 2 2 + 3 / 2 3 + ... 。这是一个著名的总结，可以用多种不同的方式进行评估。这些演讲幻灯片，幻灯片 45-47中给出了评估这一点的一种方法。它最终精确到 2n，这意味着最终进行的比较次数肯定以 3n 为界。

希望这可以帮助！

于 2011-06-09T22:26:58.490 回答
17

@templatetypedef 已经给出了一个很好的答案，为什么渐近运行时间build_heap是O(n)。在CLRS第 2 版的第 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
于 2011-06-11T00:05:34.403 回答