从max-heap获取min元素的时间复杂度

Question

我在接受采访时被问到:

从最大堆中获取min元素的最佳时间复杂度是多少？

我回答为O(1),假设堆大小已知,并且堆使用数组实现为二进制堆.按照我的假设,这样的最小值是heap_array[heap_size].

我的问题是,如果这个答案是正确的.如果没有,那么正确的答案是什么？

Answer 1

我的问题是,如果这个答案是正确的.

不,那不对.您唯一的保证是每个节点都包含它下面的子树的最大元素.换句话说,最小元素可以是树中的任何叶子.

如果没有,那么正确的答案是什么？

正确的答案是O(n).在每个步骤中,您需要遍历左侧和右侧子树以搜索最小元素.实际上,这意味着您需要遍历所有元素以找到最小值.

Answer 2

最复杂的是O(n).草图证明:

• 最小元素可以绝对是任何最低级别的节点(实际上它甚至可能不是最低级别,但让我们从这些节点开始).
• 可能存在n/2最低级别的节点.
• 所有这些都需要检查,因为你正在寻找的那个可能在你看的最后一个地方.检查除了1之外的所有内容并不会告诉您最后一个是否是最小值.
• 因此Omega(n)需要进行检查.

绑定是紧的,因为很明显我们可以O(n)通过忽略我们的数组碰巧是堆的事实来做到这一点.

道德:它可能被称为堆,因为(就像在你的卧室地板上的衣服堆),很容易到达顶部,很难得到其余的.