为什么二项堆的合并函数是O(logN)而不是O(logN * logN)？
Why is the merge function of binomial heaps O(logN) rather than O(logN * logN)?
对于那些非常了解这一点的人，请阅读下面的粗体文本以了解实际问题。
辅助功能前言：
我知道合并两个相同等级的二项式树是 O(1) 因为所有必要的是附加 T1 的头部作为另一个的 child。我还知道在二项式堆中插入一个阶数等于或小于最小阶数的树是 O(logN)，因为合并的“carry-over”效果适用。想象一个T_0,T_1,T_2,...,T_n的二项堆（其中下标是阶数），我们新增一个0阶的T' .这会导致carry-overn次合并相同顺序的树。我们知道 n = log(N).
合并函数本身：
在合并函数中，两个堆以合并排序的方式逐树添加到新的堆树中。我们将任一堆的最低阶树添加到新堆中，如果两个阶相同，则我们将其合并（O（1））并在构建后将其插入（O（logN））到结果树中递归地。由于我们将首先插入最低阶的树，因此合并将始终插入一棵等于或小于新堆中第一棵树的树。
混淆发生的地方：
我很困惑为什么合并函数是 O(logN) 而不是 O(logN*logN)。我们知道每个插入都是 O(logN)，并且我们有 logN 棵树，其中 N = N1+N2，其中 N1 和 N2 是每个起始堆中的元素数。 如果我们在结构中有两个堆，这会导致每次插入到新堆中都会发生插入的遗留效应，这不是 O(logN * logN) 吗？
也许我在这里遗漏了一些关键的理解。任何帮助表示赞赏！如果你能告诉我我的理解哪里出了问题，我将非常感谢:)
你可能不了解算法。当我们有两棵相同顺序的树时，我们不会 "merge (O (1)) it and insert (O (log N))"。您认为当我们得到这样的 "merged" 树时，我们将其保留并在最后逐个节点插入它，对吗？然后使其成为 O(logN)：当你有两棵 k 阶树时，你将它们合并并得到一棵 k+1 阶树。现在，根据要合并的堆中有多少 k+1 阶树，您有一个、两个或树 k+1 阶树：
if 1 这棵树只是合并堆的一部分
if 2 你合并这两个然后在k+2个顺序树上再次做这个点
如果3个是合并堆的一部分，你将另外2个合并成k+2阶树
所有这些都是 O(1)，所以当您以 log(n) + 1 个订单执行此操作时，您将获得 O(log(n)) 堆合并。
让我们合并两个二项式堆，一个为 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 位生成的。所以，merge是一个O(logn)的操作。
对于那些非常了解这一点的人，请阅读下面的粗体文本以了解实际问题。
辅助功能前言：
我知道合并两个相同等级的二项式树是 O(1) 因为所有必要的是附加 T1 的头部作为另一个的 child。我还知道在二项式堆中插入一个阶数等于或小于最小阶数的树是 O(logN)，因为合并的“carry-over”效果适用。想象一个T_0,T_1,T_2,...,T_n的二项堆（其中下标是阶数），我们新增一个0阶的T' .这会导致carry-overn次合并相同顺序的树。我们知道 n = log(N).
合并函数本身：
在合并函数中，两个堆以合并排序的方式逐树添加到新的堆树中。我们将任一堆的最低阶树添加到新堆中，如果两个阶相同，则我们将其合并（O（1））并在构建后将其插入（O（logN））到结果树中递归地。由于我们将首先插入最低阶的树，因此合并将始终插入一棵等于或小于新堆中第一棵树的树。
混淆发生的地方：
我很困惑为什么合并函数是 O(logN) 而不是 O(logN*logN)。我们知道每个插入都是 O(logN)，并且我们有 logN 棵树，其中 N = N1+N2，其中 N1 和 N2 是每个起始堆中的元素数。 如果我们在结构中有两个堆，这会导致每次插入到新堆中都会发生插入的遗留效应，这不是 O(logN * logN) 吗？
也许我在这里遗漏了一些关键的理解。任何帮助表示赞赏！如果你能告诉我我的理解哪里出了问题，我将非常感谢:)
你可能不了解算法。当我们有两棵相同顺序的树时，我们不会 "merge (O (1)) it and insert (O (log N))"。您认为当我们得到这样的 "merged" 树时，我们将其保留并在最后逐个节点插入它，对吗？然后使其成为 O(logN)：当你有两棵 k 阶树时，你将它们合并并得到一棵 k+1 阶树。现在，根据要合并的堆中有多少 k+1 阶树，您有一个、两个或树 k+1 阶树：
if 1 这棵树只是合并堆的一部分
if 2 你合并这两个然后在k+2个顺序树上再次做这个点
如果3个是合并堆的一部分，你将另外2个合并成k+2阶树
所有这些都是 O(1)，所以当您以 log(n) + 1 个订单执行此操作时，您将获得 O(log(n)) 堆合并。
让我们合并两个二项式堆，一个为 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 位生成的。所以，merge是一个O(logn)的操作。