5

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

但是，我正在尝试为 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)
4

1 回答 1

13

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

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

应该

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

右边有一个类似的错字（看起来你把leftand换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较早。

于 2013-03-19T06:51:53.917 回答