RSS

Building Max Heap

08 Mar

Code for Max Heap… Shows the use of MaxHeapify:

#include<iostream.h>
#include<math.h>
int size;
void maxheapify(int a[],int i,int size)
{
int l,r,largest,temp;
l=2*i;
r=(2*i+1);
if((l<=size) && (a[l]>a[i]))
largest=l;
else
largest=i;
if((r<=size) && (a[r]>a[largest]))
largest=r;
if(largest!=i)
{
temp=a[i];
a[i]=a[largest];
a[largest]=temp;
maxheapify(a,largest,size);
}
};
void buildmaxheap(int a[],int size)
{
int i;
for(i=floor(size/2);i>=1;i–)
{
maxheapify(a,i,size);
}
}
int extract_max(int*a,int size)
{
int max;
max=a[1];
a[1]=a[size];
size–;
maxheapify(a,1,size);
return(max);
}
void main()
{
int p,k,i,max,a[20],temp;
cout<<“How many no u want 2 enter\n”;
cin>>size;
cout<<“Enter no\n”;
for(i=1;i<=size;i++)
{
cin>>a[i];
}
buildmaxheap(a,size);
cout<<“Enter the value of k\n”;
cin>>k;
if(k>size)
cout<<“The value entered is greater than heap size\n”;
else
{
for(i=0;i<k;i++)
{
max=extract_max(a,size);
}
cout<<“The kth largest element is:-    “<<max;
}
}
Advertisements
 
Leave a comment

Posted by on March 8, 2011 in C/C++

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: