gpt4 book ai didi

java - Max Heapify 算法结果

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:42:01 30 4
gpt4 key购买 nike

我一直在研究算法入门教科书中的一些算法,特别是我正在尝试让二叉堆 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 方法给出的结果满足堆属性,但它与预期的不同。下面是我在 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 );
}
}

最佳答案

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

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

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

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

关于java - Max Heapify 算法结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15579240/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com