|
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);
}
| 
Search