HEAP SORTING: – In this method, a tree structure called a heap is used. A heap is a type of binary tree. An ordered balanced binary tree is called a min heap where the value at the root of any sub-tree is less than or equal to the value of either of its children. An ordered balanced binary tree is called a max-heap when the value at the root of any sub-tree is more than or equal to the value of either of its children. It is not necessary that the two children must be in some order. Sometimes the value of a left child may be more than the value of the right child and some other times it may be the other way around.
Heap sort is basically an improvement over the binary tree sort. It does not create nodes as in the case of binary tree sort. Instead, it builds a heap by adjusting the position of elements within the array itself. Basically, there are two phases involved in sorting the elements using the heap sort algorithm. They are as follows:
- Construct a heap by adjusting the array elements.
- Repeatedly eliminate the t root element of the heap by shifting it to the end of the array and then restore the heap structure with the remaining elements.
The heap sort is, therefore an O (N log N). To analyze the heap sort note that a complete binary tree with n nodes (where n is one less than a power of two) has log (n + 1) levels. Thus if each element in the array were a leaf requiring it to be filtered through the entire tree both while creating and adjusting the heap the sort would still be O (N log N). In the average case, the heap sort is not as efficient as the quick sort. Experiments indicate that heap sorting requires twice as much time as quick sorting in the worst case.
In fact, heap sort remains O (N log N) in the worst case. Heap sort is also not very efficient for small n because of the overhead of initial heap creation and computation of the location of fathers and sons. The space requirement for the heap (aside from array indices) is only one additional record to hold the temporary for switching provided the array implementation of an almost complete binary tree is used.
Algorithm for Heap sorting in c programming.
HEAPSORT (A, N)
An array A with N elements is given. This algorithm sorts the elements of A
1. [Build a heap H]
Repeat For J = 1 To N – 1
Call INSHEAP (A, J, A [J + 1])
[End of loop.]
2. [Sort A by repeatedly deleting the root of H.]
Repeat while N > 1
(a) Call DELHEAP (A, N, ITEM).
(b) Set A [N + 1] = ITEM.
[End of Loop]
3. Exit.
INSHEAP (TREE, N, ITEM)
A heap H with N elements is stored in the array TREE, and an ITEM of information is given. This procedure inserts ITEM as a new element of H. PTR gives the location of ITEM as it rises in the tree, and PAR denotes the location of the parent of ITEM.
1. [Add a new node to H and initialize PTR.]
Set N:= N + 1 and PTR = N.
2. [Find a location to insert ITEM.]
Repeat Steps 3 to 6 while PTR > 1:
3. SET PAR = [PTR / 2]. [Location of the parent node.]
4. If ITEM < = TREE [PAR]. Then:
Set TREE [PTR]: = ITEM, and Return.
[End of If Structure]
5. Set TREE[PTR] = TREE [PAR] [Moves node down.]
6. Set PTR = PAR. [Updates PTR.]
[End of Step 2 loop.]
7. [Assign ITEM as the root of H.]
Set TREE [1] = ITEM.
8. Return.
DELHEAP (TREE, N, ITEM)
A heap H with N elements is stored in the array TREE. This procedure assigns the root TREE [1] of H to the variable ITEM and then reheaps the remaining elements. The variable LAST saves the value of the original last node of H. The pointer PTR, LEFT and RIGHT give the locations of LAST and its left and right children as LAST sinks in the tree.
1. Set ITEM:= TREE [1]. [Removes the last node of H.]
2. Set LAST: = TREE [N] and N:= N – 1. [Removes the last node of H.]
3. Set PTR: = 1, LEFT = 2 and RIGHT: = 3 [Initialize pointers.]
4. Repeat Steps 5 to 7 while RIGHT ≤ N:
5. If LAST >= TREE [LEFT] and LAST >= TREE [RIGHT), then:
Set TREE [PTR]: = LAST and Return.
[End of If structure.]
6. IF TREE [RIGHT] ≤ TREE [LEFT], then:
Set TREE [PTR]: = TREE [LEFT] and PTR: = LEFT.
Else:
Set TREE [PTR]: = TREE [RIGHT] and PTR: = RIGHT.
[End of If structure.]
7. Set LEFT: = 2 * PTR and RIGHT: = LEFT + 1.
[End of Step 4 loop.]
8. If LEFT = N and LAST < TREE [LEFT], then:
Set TREE [PTR]: = TREE [LEFT], PTR: = LEFT.
[End of If structure.]
9. Set TREE [PTR]: = LAST.
10 Return.
Heap sorting program in c programming.
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void insheap(int [],int,int);
int delheap(int [],int);
void heapsort(int [], int);
void main()
{
int a[SIZE],i,n;
clrscr();
printf(“Enter how many elements “);
scanf(“%d”,&n);
/*Input Array*/
for(i=0;i<n;i++)
{
printf(“Enter element %d “,i+1);
scanf(“%d”,&a[i]);
}
heapsort(a,n);
/*Output Array*/
for(i=0;i<n;i++)
printf(“%d “,a[i]);
getch();
}
void insheap(int tree[], int n, int item)
{
int ptr, par;
n++;
ptr=n;
while(ptr > 0)
{
par = (ptr-1)/2;
if(item <= tree[par])
{
tree[ptr] = item;
return;
}
tree[ptr] = tree[par];
ptr = par;
}
tree[0] = item;
}
int delheap(int tree[], int n)
{
int item,ptr,last,left,right;
item = tree[0];
last = tree[n];
ptr = 0;
left = 1;
right = 2;
while(right <= n)
{
if(last >= tree[left] && last >= tree[right])
{
tree[ptr] = last;
return(item);
}
if(tree[right] <= tree[left])
{
tree[ptr]=tree[left];
ptr=left;
}
else
{
tree[ptr]=tree[right];
ptr=right;
}
left = 2*ptr+1;
right = left+1;
}
if(left == n-1 && last < tree[left])
{
tree[ptr] = tree[left];
ptr = left;
}
tree[ptr] = last;
return(item);
}
void heapsort(int a[],int n)
{
int item,j;
for(j=0;i<n-1;j++)
insheap(a,j,a[j+1]);
while(n>0)
{
item=delheap(a,n-1);
a[n-1] = item;
n–;
}
}