我一直在尝试使用《算法导论》中的一些算法,具体来说是尝试让二叉堆能够正常工作。我有一种奇怪的感觉,认为我正在使用的示例不正确,所以想知道是否有人可以帮助我指出正确的方向。
给定数组
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 );
}
}
A [(floor(n/2)+1)... n]
子数组中的每个元素都已经是叶节点,因此它们每个都是一个包含1个元素的堆。 - wmarquez(int)Math.floor(arr.length / 2)
。然而,floor
是不必要的,因为整数除法会截断小数部分。 - jpmarr.length - 1
来尝试一些不同的东西,但忘记了当我重新添加floor时。 - wmarquez