java Max Heapify 算法结果
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15579240/
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
Max Heapify algorithm results
提问by wmarquez
I've been playing around with some of the Algorithms in the Intro to Algorithms textbook, in specific I'm trying get a Binary Heap to work 100% correctly. I have a curious feeling that the example that I'm working with isn't correct, and I was wondering if anyone can help point me in the right direction.
我一直在玩算法介绍教科书中的一些算法，特别是我试图让二叉堆 100% 正确工作。我有一种奇怪的感觉，我正在使用的示例不正确，我想知道是否有人可以帮助我指出正确的方向。
Given the array
给定数组
int[ ] arr = { 1, 2, 3, 4, 7, 8, 9, 10, 14, 16 };
The result I get from MaxHeapify is
我从 MaxHeapify 得到的结果是
[ 16, 14, 9, 10, 7, 8, 3, 1, 4, 2 ]
However, after doing a few Google searches, I found that people who use this exact array as an example expect the result to be:
然而，在做了几次谷歌搜索之后，我发现使用这个精确数组作为例子的人期望结果是：
[ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]
What confuses me is that the result that my MaxHeapify method gives satisfies the Heap property, but it's different than what is expected. Below is my implementation in Java
让我感到困惑的是，我的 MaxHeapify 方法给出的结果满足 Heap 属性，但与预期的不同。下面是我在 Java 中的实现
public static void BuildMaxHeap( int[ ] arr )
{
for( int i = (int)Math.floor( arr.length - 1 ); i >= 0; i-- )
MaxHeapify( arr, i );
}
public static void MaxHeapify( int[ ] arr, int i )
{
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if( left < arr.length && arr[ left ] > arr[ largest ] )
largest = left;
if( right < arr.length && arr[ right ] > arr[ largest ] )
largest = right;
if( largest != i )
{
int temp = arr[ i ];
arr[ i ] = arr[ largest ];
arr[ largest ] = temp;
MaxHeapify( arr, largest );
}
}
回答by Alexey Frunze
The heaps that you've shown are both valid. There's nothing to worry about.
您显示的堆都是有效的。没有什么可担心的。
There are multiple ways to order subnodes.
有多种方法可以对子节点进行排序。
Consider the simplest case of swapping left with right:
考虑最简单的左右交换情况：
14 14
10 9 vs 9 10
... ... ... ...
回答by C Coder
Your heaps are valid. They are different because the array is not necessarily sorted when you apply neither of these methods. That's what Heapsort is for. Just one detail, in your BuildMaxHeap you may want to change
你的堆是有效的。它们是不同的，因为当您不应用这两种方法时，数组不一定是排序的。这就是 Heapsort 的用途。只是一个细节，在你的 BuildMaxHeap 中你可能想要改变
for( int i = (int)Math.floor( arr.length - 1 ); i >= 0; i-- )
to
到
for( int i = arr.length / 2; i >= 0; i-- )
The reason I say this is because you can start from the last node that has leaves as it's children, since leaves are always a max_heap.
我这么说的原因是因为你可以从最后一个有叶子的节点作为子节点开始，因为叶子总是一个 max_heap。
