在最小堆中找到最大元素？

Question

我现在正在学习堆，显然更多的关注点在于堆中的最小元素，但是我想知道如何找到最大元素？对于最小元素，你只需返回根节点即可，但是不确定你将如何处理最大元素？

- user2980566

---

你了解最小堆和最大堆的概念吗？ - jfly

假设您不想将其单独存储，您可以使用深度优先搜索来查找最小堆中的最大元素。 - Matthew Madson

一个最小堆可以让你在O(1)时间内找到最小值（因为它在根部）。在二叉堆中，最大值可能在任意一个叶子节点中，而你有O(n)个叶子节点，所以除非你有一些额外的结构，否则无法更快地找到它。例如，你可以使用最大二叉堆，在其中可以在O(1)时间内找到最大值但不能找到最小值。你还可以查看最小-最大堆 ，这是一个让你在O(1)时间内找到最大和最小值的数据结构的示例。 - Niklas B.

查看这个链接 https://dev59.com/w3I-5IYBdhLWcg3wZ3YR 可能会帮助你理解。 - Braza

可能是从MAX堆获取最小元素的时间复杂度的重复问题。 - Bernhard Barker

@Braza 计算深度如何帮助你解决这个问题？ - Bernhard Barker

Answer 1

我会假设堆是以数组的形式实现的（这是一种很常见的实现方式）。

你不需要检查整个树，“只需”检查一半即可。

因此，如果我从1开始标记数组的元素，二进制将如下所示（其中数字是数组中的索引）：

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

你只需要检查堆数组长度的一半后面的元素，对于上述例子，从7到13。前面的节点都有子节点，因此它们永远不会是最大值。这意味着只需要检查n/2个元素，因此时间复杂度仍为O(n)。

- Raul Guiu

Answer 2

定义变量max并将其初始化为0。

HeapNode[] h;
int last;
int max=0;

如果堆不为空，则从0级和0位置（根）开始检查最大值并迭代到左右子节点。

public int getMax() throws Exception {
    if (isEmpty()) {
        Exception EmptyHeapException = new EmptyHeapException();
        throw EmptyHeapException;
    } else {
        //findMax(0, 0);    //If you want to use Iteration
        for(int i=0;i<=last;i++)
            max = Math.max(h[i].key, max);//Updated Thanks Raul Guiu
        return max;
    }
}

在每个节点迭代，直到节点为最后一个。

private void findMax(int i, int level) {
    if (i > last) return;
    if(max<h[i].key)
        max=h[i].key;
    findMax(2*i+1, level+1);//left node
    findMax(2*i+2, level+1);//right node
}

public boolean isEmpty() {
    return (last < 0);
}

你可以从堆中获得最大的价值。

- Piyush

---

你正在检查整个堆。为什么不只是检查 for(i=0;i<=last;i++) max = Math.max(h[i],max); 这样既等效又更简单。 - Raul Guiu

@RaulGuiu 你是对的。 谢谢。 我在答案中更新了我的代码。 - Piyush