Heap Sort

 Heap Sort

/*******************************************************************************/

#include <stdio.h>

// Function to perform heapify on a subtree rooted at index i in the given array

void heapify(int arr[], int n, int i) {

    int largest = i;    // Initialize largest as the root

    int left_child = 2 * i + 1;

    int right_child = 2 * i + 2;

    // Compare with left child

    if (left_child < n && arr[left_child] > arr[largest]) {

        largest = left_child;

    }

    // Compare with right child

    if (right_child < n && arr[right_child] > arr[largest]) {

        largest = right_child;

    }

    // If the largest is not the root, swap and continue heapifying

    if (largest != i) {

        int temp = arr[i];

        arr[i] = arr[largest];

        arr[largest] = temp;

        heapify(arr, n, largest);

    }

}

// Main function to perform Heap Sort

void heapSort(int arr[], int n) {

    // Build a max-heap

    for (int i = n / 2 - 1; i >= 0; i--) {

        heapify(arr, n, i);

    }

    // Extract elements from the heap one by one

    for (int i = n - 1; i > 0; i--) {

        // Swap the root (maximum element) with the last element

        int temp = arr[0];

        arr[0] = arr[i];

        arr[i] = temp;

        // Call heapify on the reduced heap

        heapify(arr, i, 0);

    }

}

int main() {

  int arr[50],n,i;

 

  printf("Enter size of the array: ");

  scanf("%d",&n);

  printf("Enter %d elements:\n",n);

  for(i=0;i<n;i++)

    scanf("%d",&arr[i]);

    heapSort(arr, n);

    printf("\nSorted array: ");

    for (int i = 0; i < n; i++) {

        printf("%d ", arr[i]);

        }

    return 0;

}

/* Heap Sort Alternate Implementation */

#include<stdio.h>
void heapsort(int a[],int n);
void buildheap(int a[],int n);
void extractmax(int a[],int n);
void heapify(int a[],int i, int n);
void swap (int a[],int i, int j);

void heapsort(int a[],int n)
{
//build heap structure
buildheap(a,n);
//extract maxima
extractmax(a,n);
}
void buildheap(int a[],int n)
{
//let heap grow from half size to entire size
for(int i=n/2-1; i>=0; i--)
{
heapify(a,i,n);
}
}
void extractmax(int a[],int n)
{
//n is separator between heap and sorted part
while (n>1)
{
n--;
//put maximum at the end of heap
swap(a,0,n);
//restore heap
heapify(a,0,n);
}
}

//restore heap invariant
void heapify(int a[],int i, int n)
{
int k=2*i+1; //first child of i
while (k<n)
{
//if another child exists and that child is the maximum
if (k+1<n && a[k+1]>a[k]) k++;
if (a[i]>=a[k])
{
return; //heap invariant restored
} 

else
{
//swap element with its child
swap(a,i, k);
//continue with next iteration
i=k;
k=2*i+1;
}
}
}
void swap (int a[],int i, int j)
{
int t;
t= a[i];
a[i] = a[j];
a[j] = t;
}

int main()

{
int size,i;
printf("Enter size of the array: ");
scanf("%d",&size);

int a[size];
printf("Enter %d elements: ",size);
for(i=0;i<size;i++)
scanf("%d",&a[i]);

heapsort(a,size);

printf("Sorted elements: ");
for(i=0;i<size;i++)
printf(" %d",a[i]);

return 0;
}