最小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]だけをチェックすると、左の子が右の子よりも小さい場合であっても、右の子が親よりも小さい場合はいつでも、親を右の子と入れ替えることになります。

ちなみに、smallestをparentIndexに初期化するので、左側にheapArray[parentIndex]の代わりにheapArray[smallest]をチェックすることもできます。