DelMin 알고리즘의 접근 설계로 d 힙 배열에서 효과적인 방법을 찾는 방법

Question

효과적인 방법으로 최소를 찾기 위해 d 힙 배열을 작성해야하지만 이미 알고리즘을 찾았으나 누군가 나를 찾을 수있는 가장 쉬운 방법을 찾도록 도와 줄 수 있다고 믿으십시오. 제발 누군가 제발 나를 찾는데 다른 방법으로 도와주세요.

내 코드 : 당신이 인덱스를 계산하는 경우

Heap delMin(d, heap){ 
    heap.array[0] := heap.array[idx]; 
    heap.idx := heap.idx-1; 
    downHeap(heap.array, heap.idx, 0, d); 
    return heap; 
} 

//------------------------------------------- 
downHeap(array[], n, k, d) { 
    int currentElement; 
    int firstSuccessorIndex; 
    currentElement := array[k]; 
    smallestChildIndex = findSmallestChildIndex(array, n, currentElement, d); 
    if(smallestChildIndex == -1 || currentElement < array[smallestChildIndex]) 
    { 
     return; 
    } else { 
     swap(array, k, smallestChildIndex); 
     downHeap(array, n, smallestChildIndex, d); 
    } 
} 

//------------------------------------------- 
int findSmallestChildIndex(array[], n, k, d) { 
    firstChildIndex = array[k*d + 1]; 
    if(firstChildIndex > n){ 
     return -1; //the element is a leaf 
    } 
    lastChildIndex = array[k*d + d]; 
    if(lastChildIndex > n) { 
     lastChildIndex = n; 
    } 
    smallestChildIndex = firstChildIndex; 
    for(int i=firstChildIndex; i < lastChildIndex; i++) 
    { 
     if(array[i] < array[smallestChildIndex]) { 
      smallestChildIndex = array[i]; 
     } 
    } 
    return smallestChildIndex; 
} 

Answer 1

나는, 당신이 당신의 findSmallestChildIndex 기능에 오류가있는 것 같아요. 예를 들어 다음과 같습니다.

firstChildIndex = array[k*d + 1]; 

첫 번째 자녀의 색인을 얻지 못합니다. 오히려 첫 번째 하위 인덱스에서 값을 가져옵니다. 색인은 k*d + 1과 같습니다.

이 오류는 함수의 여러 위치에서 발생합니다.

또한 firstChildIndex이 항상 n보다 작고 n보다 작거나 같아야합니다. 나는 그 변화도했다.

수정 된 코드는 다음과 같습니다 스택 오버플로

int findSmallestChildIndex(array[], n, k, d) { 
    firstChildIndex = k*d + 1; 
    if(firstChildIndex >= n){ 
     return -1; //the element is a leaf 
    } 
    lastChildIndex = k*d + d; 
    if(lastChildIndex > n) { 
     lastChildIndex = n; 
    } 
    smallestChildIndex = firstChildIndex; 
    for(int i=firstChildIndex; i < lastChildIndex; i++) 
    { 
     if(array[i] < array[smallestChildIndex]) { 
      smallestChildIndex = i; 
     } 
    } 
    return smallestChildIndex; 
}