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

Question

我在接受采访时被问到：

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

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

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

Answer 1

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

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

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

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

Answer 2

最好的复杂性是O(n)。草图证明：

• 最小元素可以绝对是任何最低级别的节点（实际上它甚至可能不是最低级别，但让我们从这些节点开始）。
• 可能有最高级别的n/2节点。
• 所有这些都需要检查，因为你正在寻找的那个可能在你看的最后一个地方。检查它们中的全部 - 但不会告诉您最后一个是否是最小值。
• 因此需要Omega(n)考试。

边界很紧，因为很明显我们可以在O(n)中忽略我们的数组恰好是堆的事实。

道德：它可能被称为堆，因为（就像在你的卧室地板上的衣服堆），很容易到达顶部，很难得到其余的。

Answer 3

Max堆中的最小元素：

1. 最后一级搜索= O（n / 2）= O（n）
2. 用最后一个元素替换搜索的元素，并将堆大小减少1 = O（1）
3. 在替换元素上应用Maxheapify = O（log n）

总时间= O（n）+ O（1）+ O（log n）= O（n）

Answer 4

MINIMUM_ELEMENT - >在最大堆的情况下需要O（n）时间，在Min堆的情况下需要O（1）。 MAXIMUM_ELEMENT - >在最大堆的情况下需要O（1）时间，在Min堆的情况下需要O（n）。