9

我一直在玩算法介绍教科书中的一些算法，特别是我正在尝试让二进制堆 100% 正确工作。我有一种奇怪的感觉，我正在使用的示例不正确，我想知道是否有人可以帮助我指出正确的方向。

给定数组

int[ ] arr = { 1, 2, 3, 4, 7, 8, 9, 10, 14, 16 };

我从 MaxHeapify 得到的结果是

[ 16, 14, 9, 10, 7, 8, 3, 1, 4, 2 ]

但是，在进行了几次 Google 搜索后，我发现使用这个精确数组作为示例的人期望结果是：

[ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]

让我感到困惑的是，我的 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 );
    }
}
4

2 回答 2

10

您显示的堆都是有效的。没什么好担心的。

有多种方法可以对子节点进行排序。

考虑左右交换的最简单情况：

   14         14
 10  9   vs  9  10
...  ...   ...  ...
于 2013-03-22T20:36:04.480 回答
2

你的堆是有效的。它们是不同的，因为当您不应用这两种方法时，数组不一定是排序的。这就是 Heapsort 的用途。只有一个细节，在您的 BuildMaxHeap 中您可能想要更改

for( int i = (int)Math.floor( arr.length - 1 ); i >= 0; i-- )

至

for( int i = arr.length / 2; i >= 0; i-- )

我这么说的原因是因为你可以从最后一个有叶子的节点开始，因为叶子总是一个 max_heap。

于 2013-03-23T02:39:23.487 回答