Heapify 为我提供了 min-heap 的错误输出

Question

我正在尝试构建 min-heap，但未能获得正确的结果。我不确定哪里出了问题。

input = 209 97 298 54 110 27 250 455 139 181 446 206 478 90 88

output = 27 54 97 88 110 206 90 209 139 181 446 298 478 250 455

如你所见，90不应该是97的右边child...

这是我的代码：

static void Heapify( int nIndex )
{
    int nLeftIndex = GetLeft(nIndex); //2*nIndex
    int nRightIndex = GetRight(nIndex);//2*nIndex+1
    int nSmallest;

    if(heapSize > nLeftIndex && nHeap[nLeftIndex] < nHeap[nIndex])
        nSmallest = nLeftIndex;
    else
        nSmallest = nIndex;

    if(heapSize > nRightIndex && nHeap[nRightIndex] < nHeap[nSmallest])
        nSmallest = nRightIndex;

    if(nSmallest != nIndex){
        swap(nHeap, nIndex, nSmallest);
        Heapify(nSmallest);
    }
}

这就是我构建 min-heap 的方式：

heapSize = nRandomNumbers.length;

//GetParentIndex() returns n / 2 and HeapSize = 15

for(int i = GetParentIndex(heapSize - 1); i >= 0; i--){
    Heapify(i);
}

谢谢

Answer 1

如果使用从零开始的索引，则子索引应为 2 * i + 1 和 2 * i + 2（父索引应为 (i - 1) / 2）。

Heapify 为我提供了 min-heap 的错误输出

Heapify is giving me an incorrect output for a min-heap

java

heap

min-heap