Heap Sort..

Algorithm and program of heap sort..

Algorithm.

The heapsort algorithm starts by using BUILD-HEAP to build a heap on the input array A[1 . . n], where n = length[A]. Since the maximum element of the array is stored at the root A[1], it can be put into its correct final position by exchanging it with A[n]. If we now "discard" node n from the heap (by decrementing heap-size[A]), we observe that A[1 . . (n - 1)] can easily be made into a heap. The children of the root remain heaps, but the new root element may violate the heap property (7.1). All that is needed to restore the heap property, however, is one call to HEAPIFY(A, 1), which leaves a heap in A[1 . . (n - 1)]. The heapsort algorithm then repeats this process for the heap of size n - 1 down to a heap of size 2.

HEAPSORT(A)

1  BUILD-HEAP(A)

2  for i  length[A] downto 2

3        do exchange A[1]  A[i]

4           heap-size[A]  heap-size[A] -1

5           HEAPIFY(A, 1)

Figure 7.4 shows an example of the operation of heapsort after the heap is initially built. Each heap is shown at the beginning of an iteration of the for loop in line 2.
The HEAPSORT procedure takes time O(n lg n), since the call to BUILD-HEAP takes time O(n) and each of the n - 1 calls to HEAPIFY takes time O(lg n).

Program.

/* HEAP SORT */
#include<conio.h>
#include<stdio.h>

void  heap_sort(int *, int );
void create_heap(int *, int);
void display(int *, int);

void print(int arr[],int size)
{
int i;
  for(i=0;i<size;i++)
printf(" %d   ",arr[i]);
}

void create_heap(int list[], int n )
{
int k, j, i, temp;

for(k = 2 ; k <= n;  ++k)
{
i = k ;
temp = list[k];
j = i / 2 ;

while((i > 1) && (temp > list[j]))
{
list[i] = list[j];
i = j ;
j = i / 2 ;
if ( j < 1 )
j = 1 ;
}

list[i] = temp ;
}
}

void heap_sort(int list[], int n)
{
int k, temp, value, j, i, p;
int step = 1;
for(k = n ; k >= 2; --k)
{
temp = list[1] ;
list[1] = list[k];
list[k] = temp ;

i = 1 ;
value = list[1];
j = 2 ;

if((j+1) < k)
if(list[j+1] > list[j])
j ++;
while((j <= ( k-1)) && (list[j] > value))
{
list[i] = list[j];
i = j ;
j = 2*i ;
if((j+1) < k)
if(list[j+1] > list[j])
j++;
else
if( j > n)
j = n ;
list[i] = value;
} /* end of while statement */

printf("\n Step = %d ", step);
step++;
for(p = 1; p <= n; p++)
printf(" %d", list[p]);
} /* end for loop */
}

void display(int list[], int n)
{
int i;
for(i = 0 ; i < n; ++ i)
{
printf("  %d", list[i]);
}
}

void main()
{
int list[100];
int i, size;
clrscr();
printf("how many elements are there in the array");
scanf("%d",&size);
fflush(stdin);

printf("\nenter the elemnts");
for(i=0;i<size;i++)
      {
      scanf("%d",&list[i]);
      fflush(stdin);
       }

printf("\nthe elements you entered are");
print(list,size);

create_heap(list, size);
printf("\n Heap\n");
print(list, size);
printf("\n\n");

heap_sort(list,size);
printf("\n\n Sorted list is as follows :\n\n");
print(list,size);
getch();
}

Share on Google Plus

About Unknown

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.