RSS

Min Heap

08 Mar

Min Heap C program

#include<iostream.h>
#include<conio.h>
int heapsize;
void minheap(int*,int);
void insert(int*,int);
int extract_min(int*);
void decrease_key(int*,int,int);
void decreasekey(int*,int,int);
void main()
{
int i,start,A[10],min,position,key;
cout<<“Enter the number to be inserted\n”;
cin>>heapsize;
cout<<” enter the numbers\n”;
for(i=1;i<=heapsize;i++)
{
cin>>A[i];
}
start=heapsize/2;
while(start>0)
{
minheap(A,start);
start–;
}
cout<<“\nThe  minheap is:-\n”;
for(i=1;i<=heapsize;i++)
{
cout<<A[i]<<“\n”;
}

cout<<“\nThe extract min operation:-\n”;
min=extract_min(A);
cout<<“The minimum value of heap is : “<<min<<“\n\n”;
cout<<“The resulting minheap is:-\n”;
for(i=1;i<=heapsize;i++)
{
cout<<A[i]<<“\n”;
}

cout<<“\nThe decrease key operation:-\n”;
cout<<“Enter any key with its position\n”;
cin>>key>>position;
decrease_key(A,position,key);
cout<<“\nThe resulting minheap is:-\n”;
for(i=1;i<=heapsize;i++)
{
cout<<A[i]<<“\n”;
}

cout<<“\nThe insert key operation:-\n”;
cout<<“Enter the key u want 2 insert\n”;
cin>>key;
insert(A,key);
cout<<“\nThe resulting minheap is:-\n”;
for(i=1;i<=heapsize;i++)
{
cout<<A[i]<<“\n”;
}
}

void minheap(int*A,int i)
{
int lc,rc,minimum,num;
lc=(2*i);
rc=lc+1;
if((lc<=heapsize)&&(A[lc]<A[i]))
minimum=lc;
else
minimum=i;
if((rc<=heapsize)&&(A[rc]<A[minimum]))
minimum=rc;
if(minimum!=i)
{
num=A[i];
A[i]=A[minimum];
A[minimum]=num;
minheap(A,minimum);
}}

int extract_min(int*A)
{
int min;
min=A[1];
A[1]=A[heapsize];
heapsize–;
minheap(A,1);
return(min);
}

void decrease_key(int*A,int i,int key)
{
int parent,num;
parent=i/2;
if(A[i]<key)
cout<<“Cannot increase key as already smaller\n”;
else
A[i]=key;
while((i>1)&&(A[parent]>A[i]))
{
num=A[i];
A[i]=A[parent];
A[parent]=num;
i=parent;
parent=i/2;
}
}

void decreasekey(int*A,int i,int key)
{
int parent,num;
parent=i/2;
A[i]=key;
while((i>1)&&(A[parent]>A[i]))
{
num=A[i];
A[i]=A[parent];
A[parent]=num;
i=parent;
parent=i/2;
}
}

void insert(int*A,int key)
{
heapsize++;
A[heapsize]=-1000;
decreasekey(A,heapsize,key);
}
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: