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

问题描述

问 题

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

解决方案

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

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

这篇关于算法 - 合并两个堆的复杂度为logN?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！