最小堆化法- Min堆算法

Question

我正试着建立一个最小的堆。我已经完成了插入、删除、交换、上堆、下堆，并且它正在正常工作。

但是，我正在尝试为编写一个方法。

这里是我的输入：{20,14,9,6,4,5,1}

我希望最小堆的输出是：{1,5,4,20,9,6,14}，但我得到的是：{14,6,9,20,4,5,1}，正好相反。

这是我的代码：

public void minHeapify(int parentIndex)
    {
        int left = getLeft(parentIndex);
        int right = getRight(parentIndex);
        int smallest = parentIndex;
        if(_size >right && _heapArray[left]<_heapArray[parentIndex])
        {
            smallest = left;
        }

        if(_size>left && _heapArray[right]<_heapArray[parentIndex])
        {
            smallest = right;
        }
        if(smallest !=parentIndex)
        {
            replace(parentIndex, smallest);
            minHeapify(smallest);
        }
    }

我遵循了MAX-Heapify的伪代码。

Heapify (A, i)
l ← left [i]
r ← right [i]
if l ≤ heap-size [A] and A[l] > A[i]
then largest ← l
else largest ← i
if r ≤ heap-size [A] and A[i] > A[largest]
then largest ← r
if largest  ≠ i
then exchange A[i] ↔ A[largest]
Heapify (A, largest)

Answer 1

有一个错误的部分，应该检查左的孩子。线

if(_size >right && _heapArray[left]<_heapArray[parentIndex])

应该是

if(_size >left && _heapArray[left]<_heapArray[parentIndex])

右边有一个类似的错误(看起来您在错误的地方替换了left和right )，但是还有一个更严重的逻辑错误。以下一行：

if(_size>left && _heapArray[right]<_heapArray[parentIndex])

实际上应该是(纠正错误和逻辑错误)：

if(_size>right && _heapArray[right]<_heapArray[smallest])

因为您需要选择left或right中较小的一个。如果您只检查_heapArray[right]<_heapArray[parentIndex]，那么当正确的子小于父子时，即使左子小于对的子，也将与正确的子交换。

顺便说一句，您也可以检查heapArray[smallest]，而不是左边的heapArray[parentIndex]，因为您在前面将smallest初始化为parentIndex。