时间复杂度，以获得最大堆分钟元素 [英] Time complexity to get min elements from MAX heap

问题描述

有人问我，在接受采访时：

  

什么是从获得的最小单元（S）的最佳时间复杂度   最大堆。

我回答为O（1）假设堆大小是已知的，堆实现为使用数组二元堆。这样，按我的设想中，最小值是`heapArray [堆大小。

我的问题是，如果这个答案是正确的。如果没有什么是正确的答案？

解决方案

  

我的问题是，如果这个答案是正确的。的

没有，那是不正确的。你的唯一保证，是的每个节点包含它下面的子树的最大元素。换句话说，的最小元素可以在树中的叶

  

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

正确的答案是O（n）。在每个步骤中需要为了搜索的最小单元遍历左和右子树。在实际上，这意味着需要遍历所有元件以找到最小

I was asked in an interview:

What is the best time complexity in getting the min element(s) from a max heap.

I replied as O(1) assuming the heap size is known and the heap is implemented as a binary heap using an array. This way as per my assumption, the min value is at `heapArray[heapSize].

My question is that if this answer is correct. If not what is the correct answer ?

解决方案

My question is that if this answer is correct.

No, that's not correct. The only guarantee you have, is that each node contains the maximum element of the subtree below it. In other words, the minimum element can be any leaf in the tree.

If not what is the correct answer?

The correct answer is O(n). In each step you need traverse both left and right sub-trees in order to search for the minimum element. In effect, this means that you need to traverse all elements to find the minimum.

这篇关于时间复杂度，以获得最大堆分钟元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！