合并两个堆的复杂度为logN?

Question

如何合并两个堆, 可以使复杂度为O(lgN)?

Answer 1

堆也有很多不同的实现，如果是斐波那契堆，合并的复杂度是 O(1)，斜堆合并的时间复杂度是 O(lg N)。

如果是普通的堆，树形实现如 FreeBirdLjj 所言可以做到 O(lg N)。而数组实现，因为需要移动所有的元素，只能是 O(M+N)，具体的做法是类似树形实现那样，把两个堆的根作为新堆的根的左右叶子节点，然后计算它们各个元素在新数组中的位置并且移动过去，然后把末尾的元素放到根的位置，做一次维护就行了。

Answer 2

首先，必须是用树作为基础数据结构而非是数组来实现的堆，然后随便取下一个叶子节点并且将原来两堆的根赋为这个节点的左右子节点，最后对整个堆进行一次维护（heapify）就好了。