从最大堆中获取最小元素的时间复杂度 [英] Time complexity to get min elements from max-heap

问题描述

在一次采访中有人问我：

I was asked in an interview:

从最大-获得最小元素的最佳时间复杂度是多少？

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

我回答为O（1），假设堆大小已知并且使用数组将其实现为二进制堆。按照我的假设，最小值是 heap_array [heap_size] 。

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 heap_array[heap_size].

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

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?

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

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屋！