sortHeap.h

/**
   Heap Sort                                             
   * * * * *                                             
   A heap sort is a complete binary tree so:               
   // (index) left child = 2 * parent,                      
   // (index) right child = 2 * parent + 1;              
   * * * * *
   Note: heap uses 1-base index: [1 ... n] 
   // so list index k would be list[k - 1]
   * * * * *
   Edit: elType
**/

//// EDIT ////
/*
  typedef struct
  {
  int key;
  } elType;
*/

/* Swap 2 elType */
void swap(elType *a, elType *b)
{
  elType temp;

  temp = *a;
  *a = *b;
  *b = temp;
}

/* Max heapify a parent-child tree */
void max_heapify(elType list[], int idx, int n)
// idx: index of node want to max_heapify 
{
  // idx: big parent
  int child = 2 * idx; // start with left child

  while (child <= n)
    {
      // compare and choose the higher of 2 children
      if (child < n)
	{
	  if (list[child - 1].key < list[child].key)
	    {
	      child++; // turn to right child
	      // else child is still left child
	    }
	}

      // compare parent and child and swap if need
      if (list[child / 2 - 1].key > list[child - 1].key)
	// remember we have a loop with parent changing
	{
	  break;
	}
      else
	{
	  swap(&list[child / 2 - 1], &list[child - 1]);
	  child *= 2; // continue to go to descendent
	}
    }
}

/* Heap Sort */
void sortheap(elType list[], int n)
{
  int i;

  /* 1. BUILD MAX HEAP */
  // only for parent [n/2 ... 1]
  // [n/2+1 ... n] are all leaves
  for (i = n / 2; i > 0; i--)
    {
      max_heapify(list, i, n);
    }

  for (i = n - 1; i > 0; i--)
    {
      /* 2. SWAP ROOT-MAX-ITEM TO LAST */
      swap(&list[i], &list[0]);
      // this is swap 0-base

      /* 3. MAX HEAPIFYING NEW ROOT, AGAIN */
      // with just swapped max cut-off
      max_heapify(list, 1, i);
    }	
}