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; 
}