Heapify Problems in C

Question

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.