최소 Heapify 메서드 - 최소 힙 알고리즘

최소 힙을 작성하려고합니다. 나는 이미 삽입, 삭제, 스왑, 업 힙, 다운 힙을 수행했으며 올바르게 작동하고있다.최소 Heapify 메서드 - 최소 힙 알고리즘

그러나 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)

출처

2013-03-19 COLD ICE

이 의사를 따라 :

여기 내 코드입니다. 라인

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]을 확인할 수도 있습니다.

출처

2013-03-19 06:51:53 angelatlarge

도움을 주셔서 감사합니다. 지금 일하고있다. –

굉장합니다. 그것이 모든 것을 지금 듣게되어 기쁘다. – angelatlarge

최소 Heapify 메서드 - 최소 힙 알고리즘

답변

관련 문제