Max Heapify算法结果

Question

我一直在玩"算法入门"教科书中的一些算法,特别是我试图让二进制堆正确地工作100%.我有一种奇怪的感觉,我正在使用的例子是不正确的,我想知道是否有人可以帮我指出正确的方向.

鉴于阵列

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

我从MaxHeapify得到的结果是

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

但是,在进行了一些谷歌搜索之后,我发现使用这个精确数组的人作为一个例子,期望结果如下:

[ 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 );
    }
}

Answer 1

你展示的堆都是有效的.没什么值得担心的.

订购子节点有多种方法.

考虑最右边交换的最简单的情况:

   14         14
 10  9   vs  9  10
...  ...   ...  ...