Heapify가 최소 힙에 대해 잘못된 출력을 제공합니다.

Question

최소 힙을 작성하려고하지만 올바른 결과를 얻지 못했습니다. 나는 무엇이 잘못 될지 모른다.

static void Heapify(int nIndex) 
{ 
    int nLeftIndex = GetLeft(nIndex); //2*nIndex 
    int nRightIndex = GetRight(nIndex);//2*nIndex+1 
    int nSmallest; 

    if(heapSize > nLeftIndex && nHeap[nLeftIndex] < nHeap[nIndex]) 
     nSmallest = nLeftIndex; 
    else 
     nSmallest = nIndex; 

    if(heapSize > nRightIndex && nHeap[nRightIndex] < nHeap[nSmallest]) 
     nSmallest = nRightIndex; 

    if(nSmallest != nIndex){ 
     swap(nHeap, nIndex, nSmallest); 
     Heapify(nSmallest); 
    } 
} 

이 방법이다 : 당신이 90이 97의 오른쪽 자식 안 볼 수 있듯이

input = 209 97 298 54 110 27 250 455 139 181 446 206 478 90 88

output = 27 54 97 88 110 206 90 209 139 181 446 298 478 250 455

는 ... 여기

내 코드입니다 min-heap을 빌드 :

당신이 제로 기반 인덱스를 사용하는 경우 내가 + 1, 2 전 + 2 (부모의 인덱스가 있어야합니다 * *

heapSize = nRandomNumbers.length; 

//GetParentIndex() returns n/2 and HeapSize = 15 

for(int i = GetParentIndex(heapSize - 1); i >= 0; i--){ 
    Heapify(i); 
} 

감사

Answer 1

, 아이의 인덱스가이해야한다 (I - 1)/2).