5

我正在阅读Pairing heap。

这很简单，唯一棘手的部分是delete_min操作。

唯一重要的基本操作是从堆中删除最小元素。标准策略首先从左到右成对合并子堆（这是给这个数据结构命名的步骤），然后从右到左合并生成的堆列表：

我认为我不需要在此处复制/粘贴代码，因为它位于 wiki 链接中。

我的问题是

  1. 为什么他们做这两个通过合并？

  2. 为什么他们首先合并对？不直接合并它们吗？

  3. 还有为什么在合并对之后，专门从右到左合并？

4

1 回答 1

12

使用配对堆，向堆中添加项目是一个 O(1) 操作，因为它所做的只是将节点添加为新根（如果它小于当前根），或者作为当前根的第一个子节点。因此，如果您创建了一个配对堆并按顺序将数字 0 到 9 添加到其中，您最终会得到：

        0
        |
-----------------
| | | | | | | | |
9 8 7 6 5 4 3 2 1

如果您随后执行delete-min，则必须查看每个子项以确定最小项并构建新堆。如果你使用从左到右的简单组合方法，你最终会得到这棵树：

       1
       |
---------------
| | | | | | | |
9 8 7 6 5 4 3 2

下次您执行delete-min时，您必须查看剩余的 8 个子项等。使用此技术，创建然后从堆中删除所有项将是 O(n^2) 操作。

成对组合然后组合成对的两遍方法导致更有效的结构。考虑第一种情况。删除最小项目后，我们剩下九个孩子。它们从左到右成对组合产生：

  8  6  4  2  1
 /  /  /  /
9  7  5  3

然后我们从右到左组合这些对。在步骤：

  8  6  4    1
 /  /  /    /
9  7  5    2
          /
         3

  8  6    1
 /  /    / \
9  7    2   4
       /   / 
      3   5  

  8     1
 /      |
9   ---------
    6   4   2
   /   /   /
  7   5   3

      1
      |
  ----------
  8  6  4  2
 /  /  /  /
9  7  5  3

现在，下次我们调用delete-min时，只有四个节点要检查，而下一次之后将只有两个。使用两次合并方法将子级别的节点数量减少了至少一半。我展示的安排是最坏的情况。如果项目按升序排列，则第一个delete-min操作将生成一棵树，其根下方只有两个子节点。

这是配对堆摊销复杂性的一个特别好的例子。insert是 O(1)，但是在一堆插入操作之后的第一个delete-min是 O(n)，其中是自上次delete-min以来插入的项目数。两遍合并规则的美妙之处在于它可以快速重组堆以降低 O(n) 复杂度。n

使用此组合规则， delete-min的摊销复杂度为 O(log n)。使用严格的从左到右规则，它是 O(n)。

于 2014-03-19T22:22:07.027 回答