Heap Sort Program in C

February 7, 2024

Heap Sort in C

A heap is a complete binary tree which is represented using array or sequential representation.

It is a special balanced  binary tree data structure where root node is compared with its children and arranged accordingly.Normally in max heap parent node is always has a value greater  then child node.

The  worst and  Average complexity of heap sort is O(n log2 n).

  • From the given array, build the initial max heap.
  • Interchange the root element with the last element.
  • Use repetitive downward operation from root node to rebuild the heap of size one less than the starting.
Heap sort in c

Algorithm of Heap Sort 

MAX-HEAPIFY(A,i)
    1- i<-left[i]
    2- r<-right[i]
    3- if l<heap-size[A]and A[l]>A[i]
    4- then largest<-1
    5- else largest<-i
    6- if r<heap-size[A] and A[r]>A[largest]
    7- then largest<-r
    8- if largest!=i
    9- then exchange A[i]<->A[largest]
    10- MAX-HEAPIFY[A,largest]

HEAP-SORT(A)
    1- BUILD-MAX-HEAP(A)
    2- for i<-length[A] down to 2
    3- do exchange A[1]<-> heap-size[A]-1
    4- heap-size[A]<-heap-size[A]-1
    5- MAX-HEAPIFY(A,1)

BUILD-MAX-HEAP(A)
    1- heap-size[A]<-length[A]
    2- for i<-(length[A]/2) down to 1 do
     3- MAX-HEAPIFY(A,i)

Implementation of Heap Sort 

As we know that heap sort is based on the tree structure. 

so we will take an example of heap sort with the based on tree.

Originally the given array is :[6,14,3,25,2,10,20,7,6]

First we call Build-max heap

heap size[A]=9

so,i=4 to 1, call MAX HEAPIFY (A,i)

i.e., first we call MAX HEAPIFY (A,4)

                            A[l]=7, A[i]=A[4] = 25,A[r] = 6

l<- left[4] = 8

r<-right[4] = 9

8<9 and 7>25 (false)

Then,largest <-4

9<9 and 6>25(false)

Then,largest = 4

A[i]<-> A[4]

Now call MAX HEAPIFY (A,2)

Heap sort in c 1
heap sort in c 3

the A[length] =9 

So, i=A/2 = 9/2 =4

i=4

since the parent node is greater than its child node.

If it is parent node is greater than child node then the parent node replace with the lesser child node.

similarly for i=3,2,1 we get the following heap tree.

 

heap sort in c 4

Now call MAX HEAPIFY

Now we will replace the root node to last child In this photo is shown by replace 25 to 6.

Now call MAX HEAPIFY

Now we will replace the root node to last child In this photo is shown by replace 20 to 6.

heap sort in c 5 (1)

Again call MAX HEAPIFY,

we get exchange A[14] and A[3] which is shown by a image.

 

heap sort in c 5(2)

Again call MAX HEAPIFY,

we get exchange A[10] and A[3] which is shown by a image.

 

heap sort in c 5(3)

Similarly,call MAX HEAPIFY

we’ll interchange A[7] and A[2]. which is shown by this image.

heap sort in c 5(4)

Similarly,call MAX HEAPIFY

we’ll interchange A[6] and A[3]. which is shown by this image.

heap sort in c 5(5)
heap sort in c 5(6)

Similarly,call MAX HEAPIFY

we’ll interchange A[6] and A[2]. which is shown by this image.

Final,call MAX HEAPIFY

we’ll interchange A[3] and A[2]. which is shown by this image.

and finally array will be sorted.

C Code of  Heap Sort

Run

#include<stdio.h> // including library files 
int temp;
void heapify(int arr[], int size, int i)//declaring functions
{
int max = i;
int left = 2*i + 1;
int right = 2*i + 2;

if (left < size && arr[left] >arr[max])
max= left;

if (right < size && arr[right] > arr[max])
max= right;

if (max!= i)
{
// performing sorting logic by using temporary variable
temp = arr[i];
arr[i]= arr[max];
arr[max] = temp;
heapify(arr, size, max);
}
}

void heapSort(int arr[], int size)// providing definition to heap sort
{
int i;
for (i = size / 2 - 1; i >= 0; i--)
heapify(arr, size, i);
for (i=size-1; i>=0; i--)
{
// swaping logic
temp = arr[0];
arr[0]= arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}

void main() // defining main()
{
int arr[] = {58, 134, 3, 67, 32, 89, 15, 10,78, 9};
// array initializing with their elements.
int i;
int size = sizeof(arr)/sizeof(arr[0]);

heapSort(arr, size);

printf("printing sorted elements\n"); // printing the sorted array
for (i=0; i<size; ++i)
printf("%d ",arr[i]);
}

Output

printing sorted elements
3 9 10 15 32 58 67 78 89 134

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting