Heap Sort

algorithm.md

##For starters lets have few macros and methods

Since we are implementing a heap with arrays, for a node i, we can have a parent, a left child and a right child

The calculations

PARENT(i):
    return FLOOR(i/2)

LEFT(i):
    return (2*i)

RIGHT(i):
	return (2*i + 1)

Some method definations

    heap_size(array) # returns the current heap size
    set_heap_size(array) # set the heap size to some supplied parameters

##The main algorithm can be further divided into three modules.

###MAX_HEAPIFY :: Makes sure that the heap starting from index i follows the Max-Heap Property

i.e. the element at root will be the maximum. The childrens will be smaller than the root, also implying the grand childrens will be smaller than its children .. and so on.

MAX_HEAPIFY(array, i):

	l = LEFT(i)
	r = RIGHT(i)

	IF l <= heap_size(array) AND array[l] > array[i]:
		largest = l
	ELSE:
		largest = i
	END IF

	IF r <= heap_size(array) AND array[r] > array[largest]:
		largest = r
	END IF

	IF largest != i
		swap(array[i], array[largest])
		MAX_HEAPIFY(array, largest)
	END IF

END MAX_HEAPIFY

The method is supplied with an array and index i.
Store the index of left child of i in l.
And that of right child in r.

If the value at index l is greater than the value at index i, or in other words, if the value of left child array[l] is greater than the rootarray[i], set largest = l. If not, set largest = i. Now largest has the index of greater element out of root and its left child.
Now compare the value at largest with that of right child. If the value of right child is greater than the value of largest, it can be concluded that the value of right child is greater than the value of root as well as the left child. In such case set largest = r.

Now largest contains the index that hold the maximum value out of root, left child and right child.
Our next step will be to check if the present setup contradicts the Max-Heap Property.
According to the statement, root must be the largest one, i.e. after going through above mentioned conditional assignments, largest must be equal to i in order to hold Max-Heap Property.
If thats the case, we can end our algo with an assumption of the heap being in state according to the property. But if largest is not equal to i, that means the property has been violated and must be corrected. Swap the largest value with the value at root and call MAX_HEAPIFY with the largest as index to correct the decending heap. Hence if a smaller value is at the root, it will be floated down to the bottom of heap by recursive call on MAX_HEAPIFY.

###BUILD_MAX_HEAP :: Uses MAX_HEAPIFY to build Max-Heaps

BUILD_MAX_HEAP(array):
	set_heap_size(array) = length(array)
	FOR i = FLOOR(length(array) / 2) DOWNTO 1:
		MAX_HEAPIFY(array, i)

If we notice PARENT calculation, we can see PARENT(i) = FLOOR(i/2). Hence, if our array is of length n, the last parent which can be calculated is located at index FLOOR(n/2).
Speaking english (reminds me how poor I am :P) the elements of array which are located after FLOOR(n/2), are all leaf nodes and do not have further children.
So while building Max-Heap for first time, we iterate a loop from FLOOR(n/2) down to 1, where n = length(array).
Starting from leaves, the loop heads toward the root when i = 1 and in each iteration, it makes a call to MAX_HEAP with index i which makes sure that the decendents are always satisfying Max-Heap Property.

###HEAP_SORT :: Initiates the heap by calling BUILD_MAX_HEAP and then sorts the array with the help of MAX_HEAPIFY

HEAP_SORT(array):
	BUILD_MAX_HEAP(array)
	FOR i = length(array) DOWNTO 2:
		swap(array[1], array[i])
		set_heap_size(array) = heap_size(array) - 1
		MAX_HEAPIFY(array, 1)

Initiates Max Heap by calling BUILD_MAX_HEAP.
Since a heap satisfying Max-Heap Property has the maximum element as root, swap the root (here it will be always 1) with last element
Call MAX_HEAPIFY again over the heap, (leaving the last element by decreasing the heap size) to ensure the maximum at top.
Decrease the value of i and hence now swaping takes place with the second last element. The loop continues and ultimately produces a sorted array.

• Best Case: O(n log(n))
• Average Case: O(n log(n))
• Worst Case: O(n log(n))

Heap.c

/*
	HEAP SORT
	static memory allocation
	1 based indexing
	** for TURBO C, remove // from commented lines
*/

#include<stdio.h>
//#include<conio.h>

#define MAX_SIZE 11
#define swap(x,y) {t=x;x=y;y=t;}
#define PARENT(i) (i>>1)
#define LEFT(i) (i<<1)
#define RIGHT(i) ((i<<1)+1)

int HEAP_SIZE;

void MAX_HEAPIFY(int *arr, int i){
	int l, r, largest, t;

	l = LEFT(i);
	r = RIGHT(i);
	
	if(l <= HEAP_SIZE && arr[l] > arr[i])
		largest = l;
	else
		largest = i;

	if(r <= HEAP_SIZE && arr[r] > arr[largest])
		largest = r;

	if(largest != i){
		swap(arr[i], arr[largest]);
		MAX_HEAPIFY(arr, largest);
	}	
}

void BUILD_MAX_HEAP(int *arr, int arr_length){
	int i;
	HEAP_SIZE = arr_length;
	for(i = (arr_length/2); i >= 1; i--){
		MAX_HEAPIFY(arr, i);
	}
}

void HEAP_SORT(int *arr, int arr_length){
	int i, t;
	BUILD_MAX_HEAP(arr, arr_length);
	for(i = arr_length; i >= 2; i--){
		swap(arr[1], arr[i]);
		HEAP_SIZE = HEAP_SIZE - 1;
		MAX_HEAPIFY(arr, 1);
	}
}

int main(){
	int i, len, arr[MAX_SIZE];
	//clrscr();	
	printf("\nEnter length (max 10): "); scanf("%d", &len);
	printf("\nEnter %d elements one after another:\n", len);
	for(i=1; i<=len; i++) scanf("%d", &arr[i]);
	printf("\nOriginal Array ::\n\t");
	for(i=1; i<=len; i++) printf("%d  ", arr[i]);
	HEAP_SORT(arr, len);
	printf("\nSorted Array ::\n\t");
	for(i=1; i<=len; i++) printf("%d  ", arr[i]);
	printf("\n");
	//getch();
	return 0;
}