C Program For Heap Sort | C Programming

Heap

A heap is a complete tree with an ordering-relation R holding between each node and its descendant. Note that the complete tree here means tree can miss only rightmost part of the bottom level. R can be smaller-than, bigger-than. E.g. Heap with degree 2 and R is “bigger than”.

Heap Sort 

Build a heap from the given set (O(n)) time, then repeatedly remove the elements from the heap (O(n log n)). Implementation Heaps are implemented by using arrays. Insertion and deletion of an element takes O(log n) time. More on this later

Heap Sort Pseudo Code

Heapsort(A) {

   BuildHeap(A)

   for i <- length(A) downto 2 {

      exchange A[1] <-> A[i]

      heapsize <- heapsize -1

      Heapify(A, 1)

}

BuildHeap(A) {

   heapsize <- length(A)

   for i <- floor( length/2 ) downto 1

      Heapify(A, i)

}

Heapify(A, i) {

   le <- left(i)

   ri <- right(i)

   if (le<=heapsize) and (A[le]>A[i])

      largest <- le

   else

      largest <- i 

   if (ri<=heapsize) and (A[ri]>A[largest])

      largest <- ri

   if (largest != i) {

      exchange A[i] <-> A[largest]

      Heapify(A, largest)

   }

}

C Program For Heap Sort By Generating Random Numbers

#include<stdio.h>
#include <conio.h>
#include <time.h>
#include<stdlib.h>
void Adjust(int Heap_of_Numbers[],int i)  /*Function to arrange the elements in the heap*/
{
    int j;
    int copy;
    int Number;
    int Reference = 1;
    Number=Heap_of_Numbers[0];
    while(2*i<=Number && Reference==1)
    {
        j=2*i;  
        if(j+1<=Number && Heap_of_Numbers[j+1] > Heap_of_Numbers[j])
            j=j+1;
            if( Heap_of_Numbers[j] < Heap_of_Numbers[i])
                Reference=0;
            else
            {
                copy=Heap_of_Numbers[i];
                Heap_of_Numbers[i]=Heap_of_Numbers[j];
                Heap_of_Numbers[j]=copy;
                i=j;
            }
    }    
}
void Make_Heap(int heap[])
{
    int i;
    int Number_of_Elements;
    Number_of_Elements=heap[0];
    for(i=Number_of_Elements/2;i>=1;i--)
        Adjust(heap,i);
}

int main()
{
    int heap[1000];
    int NumberofElements;
    int i;
    int LastElement;
    int CopyVariable;
    time_t t;
    printf("Enter the max number \n");
    scanf("%d",&NumberofElements);
    srand((unsigned) time(&t));
    for(i=0;i<NumberofElements;i++)
    {
        heap[i]=rand()%100+1;
    }
    heap[0]=NumberofElements;
    printf("\n\nTime taken to complete the heapsort %u\n",clock()/CLOCKS_PER_SEC);
    Make_Heap(heap);
    while(heap[0] > 1) /*Loop for the Sorting process*/
    {
        LastElement=heap[0];
        CopyVariable=heap[1];
        heap[1]=heap[LastElement];
        heap[LastElement]=CopyVariable;
        heap[0]--;
        Adjust(heap,1);
    }
    printf("\nSorted Array:\n");/*Printing the sorted Array*/
    for(i=1;i<=NumberofElements;i++)
        printf("%d ",heap[i]);
    return 0;
}