Article 2: Heap Sort and Heapify Methods

 Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

The primary advantage of the heap sort is its efficiency. The execution time efficiency of the heap sort is O(n log(n)). The memory efficiency of the heap sort, unlike the other n log n sorts, is constant, O(1),because the heap sort algorithm is not recursive. 

Implementation of Max-Heap Sort:

 

/* Practical Lab Assignment 7

Implementation of Max-Heap Sort algorithm.*/

 

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

 

//Global Variable Declaration

int i,j;

 

//Max-Heapify method is used for maintaining the max-heap property in the heap

void max_heapify(int ar[],int n,int i)

{

    int left,right,largest;

    left =  2*i+1; //left child

    right = 2*i+2; //right child

    largest = i;

 

    if(left<n && ar[left]>ar[largest])

    {

        largest=left;

    }

   

    if(right<n && ar[right]>ar[largest])

    {

        largest=right;

    }

   

    if(largest!=i)

    {

        int temp;

        temp=ar[i];

        ar[i]=ar[largest];

        ar[largest]=temp;

        max_heapify(ar,n,largest);

    }

 

}

 

//Max_heap is the method to create the heap

void max_heap(int ar[],int n)

{

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

    {

        max_heapify(ar,n,i);

    }

}

 

//Heap-sort is used for sorting the elements in heap

void heap_sort(int ar[],int n)

{

    max_heap(ar,n);

    int i;

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

    {

        int temp;

        temp=ar[i];

        ar[i]=ar[0];

        ar[0]=temp;

        max_heapify(ar,i,0);

    }

}

 

void main()

{

    int n;

    clock_t start_time,end_time;

    printf("=================================================");

printf("\n Heap Sort Implementation");

    printf("\n================================================");

 

    printf("\n Enter the number of elements you want to sort: ");

    scanf("%d",&n);

 

    int arr[n];

 

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

    {

        printf("Enter the %dth element: ",i+1);

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

    }

 

    start_time = clock();

    heap_sort(arr,n);

    end_time = clock() - start_time;

 

   long double time_taken=((double)end_time)/CLOCKS_PER_SEC;

 

 

printf("\n================================================");

printf("\n Sorted Array is given as per below: ");

 

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

    {

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

    }

 

printf("\n================================================");

    printf("\n Heap Sort takes %.9Lf to execute",time_taken);

   

 

}