Heap sort uses a binary heap, which is a complete binary tree.
Binary Tree : A Binary Tree is a hierarchical structure that is either empty or consists of an element, called the root, and two distinct binary trees, called the left subtree and right subtree.
 |
Heap Sort : Binary Tree |
Heap is a binary tree with the following properties :
- It is a complete binary tree.
- Each node is greater than or equal to any of its children.
Complete Binary Tree : A binary tree is complete if each of its levels is full, except that the last level may not be full and all the leaves on the last level are placed leftmost.
Example :
 |
Heap Sort : Complete Binary Tree |
Heap Example :
 |
Heap Sort : Heap |
Note : We represent heaps in level order, going from left to right. The array corresponding to the heap above is :
[45, 24, 32, 16,19,12, 21].
To add a new node to the heap, first add it to the end of the heap and then rebuild the tree as follows:
Let the last node be the current node;
while (the current node is greater than its parent) {
Swap the current node with its parent;
Now the current node is one level up;
}
Suppose we want to insert
3, 5, 1, 19, 11, 22. We assume that the heap is initially empty.
 |
Heap Sort : Adding Node In Heap |
Now lets insert a new node 88 in the above heap.
 |
Heap Sort : Rebuilding of Heap after adding a new node |
Often you need to remove the max element, which is the root in a heap. After the root is removed, the tree must be rebuilt to maintain the heap property. The algorithm for rebuilding the tree can be described as follows:
Move the last node to replace the root;
Let the root be the current node;
while (the current node has children and the current node is smaller than one of its children) {
Swap the current node with the larger of its children;
Now the current node is one level down;
}
 |
Heap Sort : Removing Root and Rebuilding Heap
|
|
- First we take input in an array.
- Then we insert these element in heap.
- As we know that root of the heap is maximum element so we remove root and rebuild heap so that the next maximum element is at root. Rebuilding ensures that our tree is in the form of heap.
- We store the root ( maximum element ) in decreasing order of array length. We could have used another array as well to store the root.
// C Program ( Code ) for Heap sort
#include<stdio.h>
void insert(int a[], int n, int item);
int deleteheap(int a[],int n);
int main()
{
int a[20],i,n,item;
printf(" Enter number of elements in array : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf(" Enter number %d : ",i+1);
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
item=a[i];
insert(a,i,item);
}
printf("\n Heap is : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
for(i=n;i>=1;i--)
{
item=deleteheap(a,i);
// Stores item=Maximum element in decreasing order of array length
a[i-1]=item;
}
printf("\n SORTED LIST IS!!!!\n");
for(i=0;i<n;i++)
{
printf(" %d ",a[i]);
}
}
// Used to Build Heap
void insert(int a[], int n, int item)
{
int ptr,par,temp;
ptr=n;
while(ptr>=1)
{
par=(ptr-1)/2;
if(a[par]>=item)
{
a[ptr]=item;
return;
}
else
{
a[ptr]=a[par];
ptr=par;
}
a[ptr]=item;
}
}
/* Remove root which is the maximum element in Heap and rebuild heap
so that the next maximum element is at root. Rebuilding ensures
that our tree is in the form of heap.
Returns item = a[0] wcich contains the root of the heap.
*/
int deleteheap(int a[],int n)
{
int i=0,item,temp;
// a[0] - contains the root of the heap
item=a[0];
a[0]=a[n-1];
n=n-1;
while(((a[i]<a[2*i+1])||(a[i]<a[2*i+2]))&&((2*i+1)<n))
{
if(a[2*i+1]>a[2*i+2])
{
temp=a[i];
a[i]=a[2*i+1];
a[2*i+1]=temp;
i=2*i+1;
}
else
{
temp=a[i];
a[i]=a[2*i+2];
a[2*i+2]=temp;
i=2*i+2;
}
}
// Root of the heap is returned
return item;
}