algorithm - 为什么配对堆在 delete_min 时需要特殊的两次传递？

Question

我正在阅读 Pairing heap .

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

The only non-trivial fundamental operation is the deletion of the minimum element from the heap. The standard strategy first merges the subheaps in pairs (this is the step that gave this datastructure its name) from left to right and then merges the resulting list of heaps from right to left:

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

我的问题是

1. 为什么他们要进行这两个 pass 合并？

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

3. 还有为什么合并pair后，特地从右往左合并？

Answer 1

在配对堆中，向堆中添加一个项目是一个 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 个 child ，等等。使用这种技术，创建然后从堆中删除所有项目将是一个 O( n^2) 运算。

两遍方法先成对组合，然后再组合成对，从而形成更高效的结构。考虑第一种情况。删除最小项目后，我们只剩下九个 child 。它们从左到右成对组合以产生:

  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)，但是在一堆 insert 操作之后的第一个 delete-min 是 O(n)，其中 n 是自上次 delete-min 以来插入的项目数。两次合并规则的美妙之处在于它可以快速重组堆以降低 O(n) 复杂度。

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