最大堆化算法的结果

Question

我一直在尝试使用《算法导论》中的一些算法，具体来说是尝试让二叉堆能够正常工作。我有一种奇怪的感觉，认为我正在使用的示例不正确，所以想知道是否有人可以帮助我指出正确的方向。

给定数组

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方法所给出的结果符合堆属性，但与预期不同。以下是我的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 );
    }
}

- wmarquez

---

这两个都是有效的堆。你只是在稍微不同的方式下执行了max-heapify。 - Andrew Mao

你为什么要对“length”进行向下取整操作？这没有任何意义。 - jpm

Jpm，教科书上有一个证明说从A [（floor（n/2）+1）... n] 子数组中的每个元素都已经是叶节点，因此它们每个都是一个包含1个元素的堆。 - wmarquez

我觉得你的意思是 (int)Math.floor(arr.length / 2)。然而，floor 是不必要的，因为整数除法会截断小数部分。 - jpm

是的！你完全正确！我只是改变了arr.length - 1来尝试一些不同的东西，但忘记了当我重新添加floor时。 - wmarquez

Answer 1

你展示的两个堆都是有效的，无需担心。

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

考虑将左侧和右侧进行交换的最简单情况：

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

- Alexey Frunze

---

因此，一个好的测试断言应该测试结果验证堆属性，而不是检查用于实现堆的数组中数值的顺序... - Snicolas

@Snicolas 没错。红黑树通常也会被测试以确保它们的属性得到保留。 - Alexey Frunze

Answer 2

你的堆是有效的。它们之间的差异在于，当你不使用这些方法时，数组不一定是排序的。这就是堆排序的作用。只有一个细节，在 BuildMaxHeap 中，你可能想要更改

。

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

为了

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

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

- C Coder