用重複數組對陣列進行堆積

我試圖堆積一個數組。我的代碼使用一組唯一值正常工作。但是有重複條目的問題。最大值始終在根上實現。然而，結果並不是一堆。用重複數組對陣列進行堆積

CODE：

static int arr[7] = { 5, 6, 7, 4, 1, 3, 7 }; 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    for (int i = (6 - 1)/2; i >= 0; i--)//assuming size 7(0 to 6) 
    { 
     heapify2(i); 
    } 
    return 0; 
} 

void heapify2(int key) 
{ 
    int nextchoice = (arr[2 * key + 1] > arr[2 * key + 2] ? (2 * key + 1) : (2 * key + 2)); 
    if (arr[key] < arr[nextchoice]) 
    { 
     arr[key] += arr[nextchoice]; 
     arr[nextchoice] = arr[key] - arr[nextchoice]; 
     arr[key] = arr[key] - arr[nextchoice]; 
    } 
}

RESULTANT堆： 7,6,5,4,1,3,7

這裏，最後一個節點7自帶5歲以下有沒有更好的辦法解決這個問題？

來源

2014-02-14 Subhanandh

請注意，我編輯了您的代碼示例以修復格式。下次使用空格而不是製表符。 –

這裏發生的事情是，在你的最後一次迭代它交換的5和7，贈送：

7,6,5,4,1,3,7

5仍然是不合時宜的。你需要繼續檢查，直到你知道5是在適當的地方。所以你heapify需要在一個循環中運行：

while (key < length/2) 
{ 
    nextchoice = .... 
    if (arr[key] < arr[nextchoice]) 
    { 
     ... 
    } 
    key = nextchoice 
}

此外，您的外環真的應該在length/2開始。在這種情況下，(7/2)將從3開始，而不是2.在這種情況下，這不是問題，但可能與其他項目安排無法檢查中間項目是否會導致問題。

來源

2014-02-16 05:36:07

當我從中間元素開始而不是（中間1）時，它必須檢查沒有任何孩子的元素。考慮堆大小爲8，循環將從（（size-1）-1）/ 2 = 3開始。只有大小爲8或更大時，第三個元素纔有孩子。 – Subhanandh

用重複數組對陣列進行堆積

回答

相關問題