簡單的堆程序 - 這個變量做什麼

void ReheapDown(int* heap, int top, int swpIndx, int numElements) { 
    int leftChild = 2 * top + 1; 
    int rightChild = 2 * top + 2; 
    int minChild; 
    if (leftChild < numElements) { 
     // find subscript of smallest child 
     if (rightChild >= swpIndx || heap[leftChild] < heap[rightChild]) 
      minChild = leftChild; 
     else 
      minChild = rightChild; 
     // if data at top is greater than smallest 
     // child then swap and continue 
     if (heap[top] > heap[minChild]) { 
      swap(heap[top], heap[minChild]); 
      ReheapDown(heap, minChild, swpIndx, numElements); 
     } 
    }

這是一個簡單的堆。 ReheapDown部分用於刪除堆中的項目。 swpIndx做什麼？（我需要知道做一個家庭作業，我應該寫這個函數來刪除堆中的某個鍵。）簡單的堆程序 - 這個變量做什麼

來源

2012-06-09 forthewinwin

它只在函數中使用過一次，試圖弄清楚'if'在哪裏使用... –

要從堆中移除一個鍵，我們可能想要將它與刪除它之前最後一個鍵在堆中，否則堆中會出現一個空洞。

然而，交換與我們要刪除會破壞堆排序，這就是你提供的ReheapDown方法來在節點的最後一個節點。

相信swpIndex參數是我們放置要刪除的元素的索引。所以那部分代碼基本上說：

if (there exists a left child) { 
    if (there is no right child || left child < right child) 
     minChild <- left child 
    else 
     minChild <- right child 
}

我認爲參數是不必要的，雖然，因爲它似乎是唯一的目的是檢查左，右孩子的存在;這也可以通過比較leftChild和rightChild索引到numElements來完成。

希望這會有所幫助:)

來源

2012-06-09 23:12:39 Shiv16

簡單的堆程序 - 這個變量做什麼

回答

相關問題