在最小堆中搜索最大值

Question

3

我刚接触堆，正在尝试理解堆的工作原理。如何在最小堆中找到最大值？我知道可以通过查找根节点来找到最小值，但是最小堆中的最大值应该怎么找呢？我并不需要代码，只是想了解一下理论知识以便更好地理解。

- ArkhamWarfare

3个回答

1

这只是一个技巧，可能比你需要的要长一些，但如果你的堆包含数字，你可以这样做：

- ribbit

将所有数字取反的时间复杂度为O(n)，因此您的解决方案并不比扫描叶子更有效，但这是一个不错的技巧。 - limido

1

min-heap的目的是让你在O(1)的时间内找到最小元素（接着是O(Log n)的堆化剩下的堆）。在O(1)中找到最大和最小值是可能的，但只能使用增强的数据结构。

然而，如果您坚持要在min-heap中找到最大元素，则可以通过提取min-heap的所有元素来完成。从该min-heap中提取的最后一个元素将是最大元素。获取最大元素所需的时间将受到O(n*Log n)的上限约束。这种时间复杂度很容易推导 - 只需总共n次地对Log n求和即可。

- displayName

1

如果你实现一个min-max堆，在O(1)时间内找到最小值和最大值就很容易了。我想你可以把它归类为“增强型数据结构”。对于min-max堆上的所有操作，其渐近复杂度与min堆（或max堆）上的操作相同，但常数略高一些。 - Jim Mischel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Blazar · Accepted Answer

如果给出一个最小堆，找到最大值非常容易。在最小堆中，由于最小堆的规则，最大值总是位于树的底部附近。父节点的值比其子节点小。因此，重要的是要记住，由于这个原因，最大值将没有任何子节点。

假设你有一个最小堆。

          2 

     3        7 

  6    4   10   15 

12 14 9 8

在这个小根堆中，只需看一眼就很明显15是最大值，因为你只需要看元素12、14、9、8、15，它们没有子节点并且在一个小根堆中。