3

对于那些非常了解这一点的人，只需阅读下面的粗体文本即可了解实际问题。

辅助功能前言：

我知道合并两个相同等级的二叉树是 O(1) 因为所有需要的就是将 T1 的头部附加为另一个的孩子。我也知道在二项式堆中插入一个顺序等于或小于最小顺序树的树是 O(logN)，因为合并的“结转”效应适用。想象一个 T_0,T_1,T_2,...,T_n（其中下标是顺序）的二项式堆，我们添加一个 0 阶的新 T'。这将导致结转 n 次合并树相同的顺序。我们知道 n = log(N)。

合并函数本身：

在合并函数中，两个堆以一种合并排序的方式逐棵树添加到一个新的堆中。我们将任一堆的最低顺序树添加到新堆中，如果两个顺序相同，则在构建后将其合并（O（1））并将其插入（O（logN））到结果树递归地。由于我们将首先插入最低顺序的树，因此合并将始终插入顺序等于或小于新堆中第一棵树的树。

发生混淆的地方：

我很困惑为什么合并函数是 O(logN)，而不是 O(logN*logN)。我们知道每个插入都是 O(logN)，并且我们有 logN 树，其中 N = N1+N2 其中 N1 和 N2 是每个起始堆中的元素数。如果我们在结构中有两个堆，这会导致每次插入新堆时都会发生插入的结转效应，那不是 O(logN * logN) 吗？

也许我在这里遗漏了一些关键的理解。任何帮助表示赞赏！如果您告诉我在我的理解中哪里出错了，请特别感谢:)

4

2 回答 2

2

您可能不了解该算法。当我们有两个相同顺序的树时，我们不会“合并 (O (1)) 它并插入 (O (log N))”。你认为当我们得到这样的“合并”树时，我们离开它，最后，我们一个节点一个节点地插入它，对吧？然后使它成为 O (logN)：当你有两棵 k 阶的树时，你合并它们并得到一棵 k+1 阶的树。现在，根据要合并的堆中有多少 k+1 顺序树，您有一个、两个或树 k+1 个顺序树：

如果 1 这棵树只是合并堆的一部分

如果 2 合并这两个并在 k+2 顺序树上再次执行此操作

如果 3 个是合并堆的一部分，而您将其他 2 个合并到 k+2 顺序树中

所有这些都是 O(1)，所以当你在 log(n) + 1 个订单中执行它时，你会得到 O(log(n)) 堆合并。

于 2016-06-27T09:27:37.830 回答
1

让我们合并两个二项堆，一个为 n 级，另一个为 m 级，其中 m 不大于 n。每个二项式堆都可以表示为一个二进制数。例如：1010 是具有 3 度二叉树和 1 度二叉树的二叉堆。以下是合并函数的一些 Python 代码：

    def merge(heap_one, heap_two):
        # heap_one has n nodes and heap_two has m nodes
        # A BinomialHeap object consists of an array of BinomialTrees called trees
        # where each element of the array is a BinomialTree or is None
        for tree in heap_two.trees:
            if tree != None:
                heap_one.add_tree(tree)

假设 heap_one 是 1111，heap_two 是 111。这两个堆分别是它们等级的最坏情况堆。我的意思是，1111 比 1011 或 1101 或 1000 差。heap_one 中的节点数为 1+2+4+8 = 15。heap_one 的等级为 4 = log(15 + 1)。heap_two 中的节点数为 1+2+4 = 7。 heap_two 的秩为 3 = log(7 + 1)。我们在这里使用以 2 为底的日志。

对于合并，按照代码，我们首先执行 1111 + 1，然后是 (1111 + 1) + 10，然后是 ((1111 + 1) + 10) + 100。1111 + 1 = 10000 - 生成了 4 个进位。10000 + 10 = 10010 -- 产生 0 个进位。10010 + 100 = 10110 -- 产生 0 个进位。总数 在这个例子中，产生的进位数是 4。你不能有一个没有的例子。产生的进位大于 log n。
为了合并 1001 和 101，产生 1 个进位。为了合并 1111 和 1111，产生了 4 个进位。为了合并 11111 和 1111，产生了 5 个进位。

让我们回到合并 1111 和 111。四个进位是在循环的第一次迭代中生成的，使 heap_one 为 10000。这是一个 O(logn) 操作。当产生 0 个进位时，它是一个 O(1) 操作。通俗地说，logn + (logm - 1) * 1 = logn + logm - 1 < 2logn - 1 < 2logn O(logn) + (O(logm) - 1) = O(logn + logm) = O(logn) 因为 m <= n。注意：logm - 1 是编号。heap_two 中不产生进位的节点。

让我们合并 1011 和 111。1011 不是最坏情况的 4 级二项堆。1011 + 1 = 1100 -- 产生 2 个进位。1100 + 10 = 1110 -- 产生 0 个进位。1110 + 100 = 10110 -- 生成 2 个进位。前 2 个进位是从 1011 的第 0 位和第 1 位生成的。接下来的 2 个进位是从第 2 位和第 3 位生成的。因此，合并是一个 O(logn) 操作。

于 2020-04-03T08:07:24.627 回答