用重复数组对阵列进行堆积

我试图堆积一个数组。我的代码使用一组唯一值正常工作。但是有重复条目的问题。最大值始终在根上实现。然而，结果并不是一堆。用重复数组对阵列进行堆积

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

用重复数组对阵列进行堆积

回答

相关问题