5

最小ヒープを構築しようとしています。挿入、削除、スワップ、アップヒープ、ダウンヒープはすでに実行されており、正しく機能しています。

ただし、Min-Heapifyのメソッドを作成しようとしています。

これが私の入力です：{20,14,9,6,4,5,1}

私が期待した出力は、最小ヒープの場合です：{1,5,4,20,9,6,14}しかし、私が得たのは：{1,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])

右側にも同様のタイプミスがありますが（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]smallestparentIndex

于 2013-03-19T06:51:53.917 に答える