Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
Heap Sort Program in C
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.
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)
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.
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.
Again call MAX HEAPIFY,
we get exchange A[14] and A[3] which is shown by a image.
Again call MAX HEAPIFY,
we get exchange A[10] and A[3] which is shown by a image.
Similarly,call MAX HEAPIFY
we’ll interchange A[7] and A[2]. which is shown by this image.
Similarly,call MAX HEAPIFY
we’ll interchange A[6] and A[3]. which is shown by this image.
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
#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\n",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.
Login/Signup to comment