从最大堆中获取最小元素的时间复杂度

Question

在一次面试中，我被问及：

从最大堆中获取最小元素的最佳时间复杂度是什么？

我回答说，假设我们知道堆的大小，并且使用数组实现二叉堆，那么时间复杂度应该为O(1)，因为根据我的假设，最小值位于heap_array[heap_size]。

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

- hytriutucx

Answer 1

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

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

如果不是这个答案，那正确答案是什么？

正确答案是O(n)。在每一步中，你需要遍历左右子树以查找最小元素。实际上，这意味着你需要遍历所有元素来找到最小值。

- aioobe

---

我们是否可以只看数组中最后 ceil(n/2) 个元素呢？这仍然是 O(n) 的。 - grdvnl

@GuruDevanla，听起来问题似乎没有指定实现。我认为做出关于实现的假设是无效的。 - Dave Cousineau

即使我们只查看数组的最后一半（n/2）元素，时间复杂度仍然是O(n)。 - ofir_aghai

Answer 2

最优复杂度为O(n)。简要证明如下：

• 最小元素可以是任何最底层的节点（实际上甚至可以不在最底层，但我们从这里开始）。
• 最底层节点最多有n/2个。
• 需要检查所有最底层节点，因为你要找的元素可能在最后一个你查找的地方。仅检查除最后一个以外的所有节点并不能确定最后一个是不是最小的。
• 因此需要进行Omega(n)次检查。

这个上界是紧密的，因为显然我们可以忽略数组实际上是一个堆这个事实，从而在O(n)的时间内完成。

道理：它可能被称为堆，因为（就像你卧室地板上的衣服堆一样）很容易取出最上面的东西，但很难取出其余的东西。

- Steve Jessop

---

+1. 但我只会简单地说，“可能是任何一个叶子节点”。 - aioobe

@aioobe：这样可能更好，因为我相当确定至少有 n/2 个叶节点，这使得 Omega 界更明显。 - Steve Jessop

“实际上，它甚至可能不在最低层级。”-- 有什么例子可以说明最小元素不在最低层级？ - Mansoor Siddiqui

@Mansoor：最大堆的性质是每个子节点都比它的父节点小，与兄弟节点无关。因此考虑一个根节点为“10”的堆。它有两个子节点“1”和“9”。而“9”又有两个子节点“8”和“7”。那么最小值不一定在最低层（尽管必然是叶节点）。 - Steve Jessop

Answer 3

最小元素 -> 在最大堆的情况下需要O(n)时间，在最小堆的情况下需要O(1)时间。 最大元素 -> 在最大堆的情况下需要O(1)时间，在最小堆的情况下需要O(n)时间。

- Nitishgarg

Answer 4

最小元素来自最大堆：

1. 在最后一层搜索 = O(n/2)= O(n)

2. 用最后一个元素替换被搜索的元素，并将堆大小减少1 = O(1)

3. 对替换后的元素应用Maxheapify = O(log n)

总时间 = O(n)+O(1)+O(log n) = O(n)

- parimal

Answer 5

正确答案是O(n) 1）从最大堆中找到最小元素 找到第n个最大值（即最小元素） 这将需要n(n-1)/2次比较 == O(n^2) 2）首先它是一个数组 应用选择排序的第一遍来查找最小元素 这将花费O(n)时间。 3）在最大堆中逐个删除（直到）n个元素（这就是查找） 这将花费O(nlogn)时间。 在3种方法中，最好的方法是O(n)。 因此，正确答案将是O(n)时间

- Jugal Soni

Answer 6

最佳复杂度为O(n)。

与其在这里写很多关于此的内容，
在MAX-heap中，min元素和在min-heap中的MAX元素
也可以在（最低层-1）而不总是在最低层。

解释：
因为堆中有可能会缺少最低层右侧的节点，它可能不是一棵平衡（完全）树，这使得它在（较低层-1）也有叶子节点。

这意味着有n/2个要检查。 因此，在大O术语中，它等于O(n)。

例如：

• MAX-heap[10,9,1,8,7]（1是较小的值，但未出现在最低层）
  
• min-heap[8,10,20,17,15]（20是最大值，但未出现在最低层）

- ofir_aghai