Example of Heapsort Algorithm

Example of Heapsort algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

heapsort.c:

/* Framework for the sorting programs.
 * Program: 02
 * Author: Alejandro G. Carlstein
 * Description: This program will read a set of integers from standard 
 * input and sort them by implement a heap sort using the pseudocode 
 * from the book Introduction to Algorithms' by Thomas H. Cormen. 
 * Then print them out in sorted order (smallest to largest).
 */

#include <stdio.h>

#define MAX_SIZE 1000000
#define LEFT(i) ((i << 1) + 1)
#define RIGHT(i) ((i << 1) + 2)
#define DIV_BY_2(i) (i >> 1)

void Max_heapify(int array[], int i, int heap_size);
void Build_max_heap(int array[], int heap_size);
void Exchange(int *a, int *b);
void Heapsort(int array[], int length);

int data[MAX_SIZE];
int n;

int main(int argc, char* argv[]){

	int i;
	int heap_size;

	/* Read in the data */
	n = 0;
    while (scanf('%d', &data[n]) == 1)
	    ++n;

	/* Sort the numbers low to high */
	Heapsort(data, n);

	/* Print out the data */
	for (i = 0; i < n; ++i)
	    printf('%d\n', data[i]);

	return 0;
}

/*
 * Max_heapify helps to rebuild the heap region
 */
void Max_heapify(int array[], int i, int heap_size){

	int l, r, temp, largest;

	l = LEFT(i);

	r = RIGHT(i);	

	// Find Largest value
	largest = (l < heap_size && array[l] > array[i]) ? l : i;

	if (r < heap_size && array[r] > array[largest]) largest = r;

	if (largest != i){

		// Exchange 
		Exchange(&array[i], &array[largest]);

		// Rebuild heap region		
		Max_heapify(array, largest, heap_size);	

	}// end if	

}

/*
 * Build_max_heap helps to build the initial heap
 */
void Build_max_heap(int array[], int heap_size){

	int i = DIV_BY_2(heap_size);

	for (; i > -1; i--){

		Max_heapify(array, i, heap_size);

	}//end for

}

/*
 * Exchange swap the values holded by two variables
 */
void Exchange(int *a, int *b){

		int temp;

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

/*
 * Heapsort sort an array from the smallest element to the largest
 */
void Heapsort(int array[], int length){

	int i;
	int	heap_size = length ;

	Build_max_heap(data, length);

	for (i = (length - 1) ; i > 0; --i){

		// Exchange the largest item in the heap region
		// to the beginning of the sorted region
		Exchange(&data[0], &data[i]);

		// Reduce the heap region, increase the sorted region
		heap_size--;

		// Rebuild the heap region
		Max_heapify(data, 0, heap_size);

	}//end for

}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

© 2010, Alejandro G. Carlstein Ramos Mejia. All rights reserved.