Java 在最小堆中找到最大元素？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22703549/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding max element in a min-heap?
提问by user2980566
I'm learning about heaps right now and obviously more attention is given to the min element of the heap, however I'm just wondering how you would find the max element? For the min element you would just have to return the root, not sure how you would approach it for the max?
我现在正在学习堆，显然堆的最小元素得到了更多的关注，但是我只是想知道如何找到最大元素？对于 min 元素，您只需要返回根，不确定您将如何处理它以获得最大值？
采纳答案by Piyush
Define variable maxand initialize it to 0.
定义变量max并将其初始化为 0。
HeapNode[] h;
int last;
int max=0;
If heap is not empty, start from 0 level and 0 position(root) and check for max value and iterate to left and right child.
如果堆不为空，则从 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;
}
}
Iteration at every node until Node is last.
在每个节点上迭代，直到最后一个节点。
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);
}
You get maximum value from heap.
您从堆中获得最大值。
回答by Raul Guiu
I will assume that the Heap is implemented as an array (that is a very common way to implement a Heap).
我将假设 Heap 被实现为一个数组（这是实现 Heap 的一种非常常见的方式）。
You dont need to check the whole tree, "only" half.
你不需要检查整棵树，“只”一半。
So if I index the elements of the array starting from 1, the binary will look like this (where numbers ar ethe indexes in the array):
因此，如果我从 1 开始索引数组的元素，二进制文件将如下所示（其中数字是数组中的索引）：
1
2 3
4 5 6 7
8 9 10 11 12 13
You only need to check floor(length(heapArray)/2) last elements, in the case above 7, so from 7 to 13. The nodes before that have children so they never will be the max. Than means checking n/2 elements so you still have O(n) complexity.
你只需要检查 floor(length(heapArray)/2) 最后一个元素，在 7 以上的情况下，从 7 到 13。之前的节点有孩子，所以它们永远不会是最大值。这意味着检查 n/2 个元素，因此您仍然具有 O(n) 复杂度。
