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.