Implementation of Heap Sort in C


#include <stdio.h>
#include <conio.h>
#include <math.h>
#define SIZE_OF_ARRAY 11
typedef struct
{
 int heapArray[SIZE_OF_ARRAY];
 int heapSize;
}Heap;
int Parent(int nodeIndex)
{
 return(floor(nodeIndex/2));
}
int Left(int nodeIndex)
{
 return( 2 * nodeIndex );
}
int Right(int nodeIndex)
{
 return( (2 * nodeIndex) + 1);
}
void MaxHeapify(Heap *heapInstance, int nodeIndex)
{
 int leftNode;
 int rightNode;
 int largestNode;
 int temp;
 leftNode = Left(nodeIndex);
 rightNode = Right(nodeIndex);
 if ((leftNode <= heapInstance->heapSize) && (heapInstance->heapArray[leftNode] > heapInstance->heapArray[nodeIndex]))
 {
 largestNode = leftNode;
 }
 else
 {
 largestNode = nodeIndex;
 }
 if ((rightNode <= heapInstance->heapSize) && (heapInstance->heapArray[rightNode] > heapInstance->heapArray[largestNode]))
 {
 largestNode = rightNode;
 }
 if (largestNode != nodeIndex)
 {
 temp = heapInstance->heapArray[nodeIndex];
 heapInstance->heapArray[nodeIndex] = heapInstance->heapArray[largestNode];
 heapInstance->heapArray[largestNode] = temp;
 MaxHeapify(heapInstance, largestNode);
 }
}
void BuildMaxHeap(Heap *heapInstance)
{
 int i;
 for ( i = heapInstance->heapSize/2; i >= 1; i-- )
 {
 MaxHeapify(heapInstance, i);
 }
}
void HeapSort(Heap *heapInstance)
{
 int i;
 int temp;
 BuildMaxHeap(heapInstance);
 printf("\nThe array elements after applying BuildMaxHeap operation are:\n");
 for( i = 1; i < SIZE_OF_ARRAY; i++)
 {
 printf("%d\t", heapInstance->heapArray[i]);
 }
 printf("\n");
 for ( i = SIZE_OF_ARRAY - 1; i >= 2; i-- )
 {
 temp = heapInstance->heapArray[1];
 heapInstance->heapArray[1] = heapInstance->heapArray[i];
 heapInstance->heapArray[i] = temp;
 heapInstance->heapSize = heapInstance->heapSize - 1;
 MaxHeapify(heapInstance, 1);
 }
}
int wmain(void)
{
 int i;
 Heap heapInstance;
 printf("Enter the elements of the array\n");
 for( i = 1; i < SIZE_OF_ARRAY; i++)
 {
 scanf_s("%d", &heapInstance.heapArray[i]);
 }
 heapInstance.heapSize = SIZE_OF_ARRAY - 1;
 printf("The array elements are:\n");
 for( i = 1; i < SIZE_OF_ARRAY; i++)
 {
 printf("%d\t", heapInstance.heapArray[i]);
 }
 printf("\n");
 HeapSort(&heapInstance);

 printf("The sorted array elements are:\n");
 for( i = 1; i <= SIZE_OF_ARRAY - 1; i++)
 {
 printf("%d\t", heapInstance.heapArray[i]);
 }
 printf("\n");
 printf("\nPress enter to exit");
 getchar();
 return 1;
}