给定 2 个最大堆 h1
和 h2
,我想将它们合并成一个最大堆 H
。我已经完成了相关问题,并理解了合并它们的 O(n)
方法:简单地连接数组并再次调用 build_max_heap
。
但是,我一直在考虑这个算法,在我看来,这是 O(logn)
并且也是正确的。有人可以证明它是否不正确,或者它的复杂性是否也归结为 O(n)
?
算法
def merge(h1, h2):
# base cases, if one of them is a leaf node.
if h1.right_child is None and h1.left_child is None:
insert(h1, h2) # insert h1 in h2
return h2
if h2.right_child is None and h2.left_child is None:
insert(h2, h1) # insert h2 in h1
return h1
if value(h1) > value(h2):
new = h1
orphan1, orphan2 = h1.left_child, h1.right_child
new.left_child = max(orphan1, orphan2)
new.right_child = merge(min(orphan1, orphan2), h2)
else:
new = h2
orphan1, orphan2 = h2.left_child, h2.right_child
new.left_child = max(orphan1, orphan2)
new.right_child = merge(min(orphan1, orphan2), h1)
return new
这似乎只遍历了整个深度两次。有误吗?
最佳答案
如果您的堆没有任何平衡要求,那么在 O(log(n)) 中合并两个二叉堆很简单。合并过程与刚刚删除根后修复堆的过程几乎相同。
对于二进制堆的通常实现,其中所有元素都连续存储在一个数组中,平衡要求意味着您的想法行不通。它会在阵列中留下一堆洞。
关于python - 合并堆的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33314502/