next up previous contents index Search
Next: 0.3.3.6 References Up: 0.3.3 Heapsort Previous: 0.3.3.4 Analysis

0.3.3.5 Source Code

Below is an implementation of a Heapsort in C:


/* ------------------------------------------------------------------------- */
/*   h_sort - perform a heap sort on a range of data items
 */

void h_sort(int low, int hi) {
  int i;

  /* heapify the data set */
  heapify(low, hi);

  /* repeatedly swap top and last then pushdown the promoted last */
  for (i = TOPITEM - 1; i > 1; i--) {
    swap(&data[1], &data[i]);
    pushdown(1, i - 1);
  }
}

As you can see, the real trick is taking the input data set and making it into a max-heap. The support routine to push down the root node in a heap to its proper place is used both to put the data into a heap initially and at each step in the sort process.


/* ------------------------------------------------------------------------- */
/*   pushdown - push a data item down the heap until in the proper place
 */

void pushdown(int which, int limit) {

  /* we will determine the node's max child */
  int max_child = which * 2;

  /* if this is a leaf node (i.e. it has no children) then we're done */
  if (max_child > limit) return;

  /* if it has a second child, make max_child the index of the greater kid */
  if (((which * 2) + 1) <= limit)
    if (data[max_child] < data[(which * 2) + 1]) max_child = (which * 2) + 1;
 
  /* now see if the node in question if greater than its max child... */  
  if (data[which] < data[max_child]) {

    /* if it's not, swap them and keep going with the push down */
    swap (&data[which], &data[max_child]);
    pushdown(max_child, limit);
  }
}

/* ------------------------------------------------------------------------- */
/*   heapify - given a data range, make it into a heap
 */

void heapify(int low, int hi) {

  /* we only have to start at the first node with children */
  int mid = (low + hi) / 2;
  int i;

  /* work backwards to the top of the heap calling pushdown */
  for (i = mid; i > 0; i--) pushdown(i, TOPITEM-1);
}

Scott Gasch
1999-07-09