14

我在一次采访中被问到：

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

我回答为 O(1) 假设堆大小是已知的并且堆是使用数组实现的二进制堆。这样根据我的假设，最小值为heap_array[heap_size]。

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

4

6 回答 6

35

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

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

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

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

于 2012-07-25T07:52:06.060 回答
11

Best complexity is O(n). Sketch proof:

  • The minimum element could be absolutely any of the lowest-level nodes (in fact it could even not be at the lowest level, but let's start with these).
  • There could be up to n/2 lowest-level nodes.
  • All of them need to be examined, because the one you're looking for might be in the last place you look. Examining all-but-1 of them doesn't tell you whether the last one is the minimum or not.
  • Hence Omega(n) examinations required.

The bound is tight, since clearly we can do it in O(n) by ignoring the fact that our array happens to be a heap.

Moral: it's probably called a heap because (as with the heap of clothes on your bedroom floor) it's easy to get at the top and difficult to get at the rest.

于 2012-07-25T07:57:21.830 回答
1

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

于 2017-07-11T07:31:59.310 回答
1

来自最大堆的最小元素：

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

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

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

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

于 2015-11-21T07:22:39.827 回答
0

正确答案是 O(n) 1) 从最大堆中找到最小元素 Find nth max(这只是最小元素) 这将首先进行 n(n-1)/2 比较 == O(n^2) 2)根本就是数组要找到最小元素，应用选择排序第一遍，这将花费 O(n) 时间。3）在最大堆中一个一个（最多）删除n个元素（它只是发现而已）这将花费O（nlogn）时间。在 3 种方法中，最好的一种是 O(n)。所以正确答案将是 O(n) 时间

于 2019-06-30T18:19:13.833 回答
0

最佳复杂度是 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是最大值，但没有出现在最低级别）
于 2019-07-16T11:13:38.500 回答