Sorting Part--6 HeapSort REFERNCE PANIMALAR ENGINEERING COLLEGE NOTES

HEAP SORT

In heap sort the array is interpreted as a complete binary tree. This method has two phases.

Phase 1 : Binary heap is constructed.
Phase 2 : Deletemin or Deletemax routine is performed for sorting.

Phase 1: Two properties of a binary heap namely structure property and heap order property are achieved.

Phase 2: The array elements are sorted using deletemin operation, which gives the elements arranged in descending order.

the array elements are sorted using deletemax operation, which gives the elements arranged in ascending order.

Algorithm

#define leftchild(i) (2*(i)+1)

void PercDown (ElementType A[], int N)
{
int child;
ElementType tmp;
for ( tmp = A[i]; leftchild (i){
child = leftchild(i);
if(child!=N-1 && A[child+1] > A[child])
child++;
if(tmpA[i]=A[child];
else
break;
}
A[i]=temp;
}

void HeapSort (ElementType A[], int N)
{
int I;
for(i=N/2;i>=0;i--)
PercDown(A,i,N);
for(i=N-1;i>0;i--)
{
Swap(&A[0], &A[i]);
PercDown(A,0,i);
}
}

Analysis of Heap Sort

Worst Case Analysis              - O(N log N)
Best Case Analysis                 - O(N log N)
Average Case Analysis           - O(N log N)

Advantages of Heap Sort

It is efficient for sorting large number of elements.
It has the advantage of Worst Case O(N log N) running time.

Limitations

It is not a stable sort.
It requires more processing time.

Example:

Input : 25, 73, 10, 95, 68, 82, 22, 60

Step 1: Build Heap routine execution to derive a MaxHeap structure

Step 2: Delete Max routine to derive a sorted list :