时间复杂度，以获得最大的堆最小元素

Question

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

什么是从最大堆得到最小元素（S）的最佳时间复杂度？

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

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

Answer 1

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

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

如果不是什么正确答案？

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

Answer 2

最佳复杂度是O(n)。素描证明：

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

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

道德：它可能被称为堆，因为（就像在你的卧室地板上堆放的衣服一样），很容易到达顶部，很难进入休息。从最大堆

Answer 3

敏元件：在末级

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）的时间在最大堆和O的情况下，（1 ）在最小堆的情况下。 MAXIMUM_ELEMENT - >如果是最大堆，则最多需要O（1）次，最小堆需要O（n）。