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

Question

我正在阅读配对堆.

这很简单,唯一棘手的部分是delete_min操作.

唯一不重要的基本操作是从堆中删除最小元素.标准策略首先从左到右合并子堆(这是赋予此数据结构名称的步骤),然后从右到左合并生成的堆列表:

我不认为我需要在这里复制/粘贴代码,因为它在wiki链接中.

我的问题是

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

2. 为什么他们首先合并？没有直接合并他们所有？

3. 合并后,为什么从右到左专门合并？

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个孩子等.使用这种技术,创建然后从堆中删除所有项目将是一个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).