Notes

#include<stdio.h>
#include<stdlib.h>

void HeapSort(int*,int);
void heapify(int*,int,int);
void swap(int*,int*);
int main()
{
int n,*a,i;
printf("Enter number of values: ");
scanf("%d", &n);
a = (int*) malloc (n*sizeof(int));
printf("Enter The valuesn");
for(i=0;i<n;i++)
scanf("%d",(a+i));
printf("Heap Sort Using Max Heapn");
HeapSort(a,n);
printf("The Sorted Array is: { ");
for(i=0;i<n;i++)
printf(" %d, ",*(a+i));
printf("}n");
}
void HeapSort(int *a, int n)
{
// Build heap by rearranging array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);

// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
swap((a+0), (a+i));

// call max heapify on the reduced heap
heapify(a, i, 0);
}
}
void heapify(int *a, int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2

// If left child is larger than root
if (l < n && a[l] > a[largest])
largest = l;

// If right child is larger than largest so far
if (r < n && a[r] > a[largest])
largest = r;

// If largest is not root
if (largest != i)
{
swap((a+i), (a+largest));

// Recursively heapify the affected sub-tree
heapify(a, n, largest);
}
}
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}