# 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, &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. http://www.getjealous.com/