3

我是堆新手，并试图了解堆是如何工作的。你如何找出最小堆中的最大值？我知道可以通过查找根来找到最小值，但是最小堆中的最大值呢？不是在寻找代码，更多的是为了理论和我的理解。

4

3 回答 3

2

如果有说明，它很容易指出最小堆中的最大值。在最小堆中，由于最小堆的规则，最大值将始终位于树的底部附近。其中父节点的值小于其子节点的值。因此，记住最大值因此不会有任何孩子非常重要。

假设你得到了一个最小堆。

          2 

     3        7 

  6    4   10   15 

12 14 9 8

在这个最小堆中，很明显 15 是最大值，因为您只需要查看没有子元素且位于最小堆中的元素 12、14、9、8、15。

于 2017-10-07T04:01:43.960 回答
1

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

  • 否定原始堆中的数字
  • 对这些运行 Min-Heapify。这将导致最小的数字（再次否定时更大）上升到根。
于 2017-10-07T02:29:43.457 回答
1

min-heap 的目的是让您在 O(1) 时间内找到最小元素（然后是 O(Log n) 堆起堆的其余部分）。在 O(1) 中找到最小值和最大值是可能的，但只能使用增强的数据结构。

但是，如果您坚持要在最小堆中找到最大元素，则可以通过提取最小堆的所有元素来做到这一点。从该最小堆中提取的最后一个元素将是最大元素。获得最大元素所需的时间上限为 O(n*Log n)。这个时间复杂度很容易推导 - 只需将 Log n 加总 n 次，

于 2017-10-07T02:41:14.337 回答