Min Heapify方法 - 最小堆算法

Question

我正在尝试构建一个最小堆.我已经完成了插入,删除,交换,上堆,下堆,它正常工作.

但是,我正在尝试为Min-Heapify编写一个方法.

这是我的输入:{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更早.