java - 在最小堆中查找最大元素？

Question

我现在正在学习堆，显然更多的注意力放在了堆的最小元素上，但是我只是想知道如何找到最大元素？对于 min 元素，您只需返回根元素，不确定如何处理 max 元素？

Answer 1

我假设堆是作为数组实现的(这是实现堆的一种非常常见的方式)。

你不需要检查整棵树，“只”检查一半。

因此，如果我从 1 开始索引数组的元素，二进制文件将如下所示(其中数字是数组中的索引):

              1
         2          3
      4    5     6     7
     8 9 10 11 12 13 

你只需要检查 floor(length(heapArray)/2) 最后一个元素，在上面的例子中是 7，所以从 7 到 13。之前的节点有子节点，所以它们永远不会是最大值。这意味着检查 n/2 个元素，所以你仍然有 O(n) 的复杂性。