Heapifying an array with duplicates

Question

I was trying to heapify an array. My code is working fine with an array of unique values. But had a problem with duplicate entries.The maximum value is always achieved at the root. Yet, the result is not a heap.

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 HEAP: 7,6,5,4,1,3,7

Here, last node 7 comes under 5. Is there a better way to solve this problem?

Answer 1

What's happening here is that on your last iteration it's swapping the 5 and the 7, giving:

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

5 is still out of place. You need to continue checking until you know that 5 is in the proper place. So your heapify needs to be run in a loop:

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

Also, your outer loop really should start at length/2. In this case (7/2), which will start at 3 rather than 2. It's not a problem in this case, but it's possible that with other arrangements of items, failing to check that middle item will cause a problem.