CS301 Assignment No. 4 Solution

Assignment No. 04

SEMESTER Fall 2010

CS301- Data Structure

Total Marks: 15

Due Date: 24/01/2011

Question:  

                                                                     

Write a program in c++ that takes any no of elements through command prompt from user and saves it in an array. Then convert it into sorted format with minimum heap sort using your own coded implementation.

  

Note: You can't use built-in library function or templates for heap functions. All the source code should be written manually.

Solution:

#include<iostream.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]);
}



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;
}