OVERVIEW:
Heapsort begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the partially sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the partially sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.
Heapsort inserts the input list elements into a binary heap data structure. The largest value (in a max-heap) or the smallest value (in a min-heap) are extracted until none remain, the values having been extracted in sorted order. The heap's invariant is preserved after each extraction, so the only cost is that of extraction.
During extraction, the only space required is that needed to store the heap. To achieve constant space overhead, the heap is stored in the part of the input array not yet sorted.
Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array. The remaining prefix of the array stores the unsorted elements.
ALGORITHM:
function heapSort(a, count) is
input: an unordered array a of length count
(first place a in max-heap order)
heapify(a, count)
end := count-1 //in languages with zero-based arrays the children are 2*i+1 and 2*i+2
while end > 0 do
(swap the root(maximum value) of the heap with the last element of the heap)
swap(a[end], a[0])
(decrease the size of the heap by one so that the previous max value will
stay in its proper placement)
end := end - 1
(put the heap back in max-heap order)
siftDown(a, 0, end)
function heapify(a, count) is
(start is assigned the index in a of the last parent node)
start := (count - 1) / 2
while start ≥ 0 do
(sift down the node at index start to the proper place such that all nodes below
the start index are in heap order)
siftDown(a, start, count-1)
start := start - 1
(after sifting down the root all nodes/elements are in heap order)
function siftDown(a, start, end) is
input: end represents the limit of how far down the heap
to sift.
root := start
while root * 2 + 1 ≤ end do (While the root has at least one child)
child := root * 2 + 1 (root*2 + 1 points to the left child)
swap := root (keeps track of child to swap with)
(check if root is smaller than left child)
if a[swap] < a[child]
swap := child
(check if right child exists, and if it's bigger than what we're currently swapping with)
if child+1 ≤ end and a[swap] < a[child+1]
swap := child + 1
(check if we need to swap at all)
if swap != root
swap(a[root], a[swap])
root := swap (repeat to continue sifting down the child now)
else
returnANIMATION:
CODE:
/* www.code-aholic.blogspot.in- HEAP SORT*/
#include<stdio.h>
#include<conio.h>
void restoreHup(int*,int);
void restoreHdown(int*,int,int);
void main()
{
int a[20],n,i,j,k;
printf("Enter the number of elements to sort : ");
scanf("%d",&n);
printf("Enter the elements : ");
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
restoreHup(a,i);
}
j=n;
for(i=1;i<=j;i++)
{
int temp;
temp=a[1];
a[1]=a[n];
a[n]=temp;
n--;
restoreHdown(a,1,n);
}
n=j;
printf("Here is it...");
for(i=1;i<=n;i++)
printf("%4d",a[i]);
getch();
}
void restoreHup(int *a,int i)
{
int v=a[i];
while((i>1)&&(a[i/2]<v))
{
a[i]=a[i/2];
i=i/2;
}
a[i]=v;
}
void restoreHdown(int *a,int i,int n)
{
int v=a[i];
int j=i*2;
while(j<=n)
{
if((j<n)&&(a[j]<a[j+1]))
j++;
if(a[j]<a[j/2]) break;
a[j/2]=a[j];
j=j*2;
}
a[j/2]=v;
}