Very subtle problem! Apart from various small annoyances which meant your code would not run until I fixed a few things (function prototypes and #includes, and the absence of a printTree() function), your real issue is in the line
while(i > 0) heapify(array, n, i--);
This never calls heapify with i==0, since you use the post-increment operator (i-- instead of --i. Thus, the last call to heapify has i==1.
So the first change you need is this:
i = n / 2;
while(i > 0) heapify(array, n, --i);
There is also a problem with your heapify code. First of all, when you look for children, you test whether the array element is zero; and if it is, you set the child node to node 0 (which is actually a valid node). I changed things a bit so you start out by initializing the left and right child to -1, so you can tell the difference between "valid" and "invalid".
Finally - when you make a swap, you need to recurse back down the tree; and you were looking at the wrong leg ( you were re-examining the one that just got swapped, instead of drilling down):
swap(array, i,largest);
heapify(array, n, i);
Instead of
swap(array, i,largest);
heapify(array, n, largest);
Taking it all together, the code becomes as follows:
#include <stdio.h>
void buildHeap(int array[], int n);
void heapify(int array[], int n, int i);
void swap(int array[], int indexA, int indexB);
void printTree(void);
int* TREE; // global variable used for printing the entire tree
int main(int argc, char *argv[])
{
int heapArray[] = {0, 1, 2, 3, 4, 5, 6 , 7, 8 ,9 ,10 , 11, 12, 13 ,14 ,15};
int n = sizeof(heapArray)/sizeof(int);
TREE = heapArray;
printTree();
buildHeap(heapArray, n);
printTree();
return 0;
}
void printTree(void)
{
// lazy way to print the entire tree...
int* array = TREE;
printf(" %3d\n ", array[0]);
printf(" %3d %3d\n", array[1], array[2]);
printf(" %3d %3d %3d %3d\n", array[3], array[4], array[5], array[6]);
printf(" %3d %3d %3d %3d %3d %3d %3d %3d\n", array[7], array[8], array[9], array[10], array[11], array[12], array[13], array[14]);
printf("%3d\n", array[15]);
printf("\n");
}
void buildHeap(int array[], int n)
{
printf("buildHeap\n");
// changed starting condition
int i = n/2;
// changed from i-- to --i so we get to zero
while(i > 0) heapify(array, n,--i);
}
void heapify(int array[], int n, int i)
{
printf("heapify [%i] = %i\n", i, array[i]);
printTree();
// mark nodes initially as -1 to distinguish from "valid" zero
int childLeft = -1, childRight = -1;
int largest = i;
// changed the way we check for valid nodes:
if(2*i+1<n) childLeft = 2*i+1;
if(2*i + 2<n) childRight = 2*i + 2;
// see if any nodes are invalid now:
if(childLeft < 0 && childRight < 0) return;
if(childLeft < 0) childLeft = childRight;
if(childRight < 0) childRight = childLeft;
printf("child left [%i] = %i child right [%i] = %i\n", childLeft, array[childLeft], childRight, array[childRight]);
if(array[childLeft] > array[i]) largest = childLeft;
if(array[childRight] > array[largest]) largest = childRight;
if(largest != i)
{
swap(array, i,largest);
heapify(array, n, largest);
}
}
void swap(int array[], int indexA, int indexB)
{
printf("swap [%i] %i with [%i] %i\n", indexA, array[indexA], indexB, array[indexB]);
int temp = array[indexA];
array[indexA] = array[indexB];
array[indexB] = temp;
}
And the sorted tree at the end of this is
15
10 14
8 9 12 13
7 1 0 4 11 5 2 6
3
The head of each node is now bigger than the children below it - just as you would expect from this algorithm.
