AIM
To implement the min heap structure
with insert and delete minimum operation using Java program
ALGORITHM
Step 1:
start the program by creating function with min heap
property
Step 2:
two functions namely insert() and deletemin() are
created
Step 3:
the insert() is used to insert new element in the tree
structure with heap property.
Step 4:
The deletemin() is used to delete the minimum element
which is usually a root node.
Step 5:
The two operations are performed satisfying heapness
and completeness property.
Step 6:
End of the program.
PROGRAM:
MIN HEAP
import java.io.*;
class heapalg
{
int
maxsize=100,size;
int[] h=new
int[maxsize];
public int
leftchild(int i)
{
return
2*i;
}
public int
rightchild(int i)
{
return
2*i + 1;
}
public int
parent(int i)
{
return
i/2;
}
public boolean
isleaf(int i)
{
return
((i<=size) && (i>size/2));
}
public void
swap(int i,int j)
{
int t;
t=h[i];h[i]=h[j];h[j]=t;
}
public void
display()
{
System.out.println("The heap elements are:"+"\n");
for(int
i=1;i<=size;i++)
System.out.println("\n"+h[i]);
}
public void
insert()
{
size++;
if(size>maxsize)
System.out.println("Heapfull");
else
{
try
{
System.out.println("Enter the element:");
DataInputStream din=new
DataInputStream(System.in);
h[size]=Integer.parseInt(din.readLine());
}
catch(Exception e){}
insertelt(size);
}
}
public void
insertelt(int i)
{
while ((h[parent(i)]>h[i]))
{
int
par=parent(i);
swap(par,i);
i=par;
}
}
public void
delete()
{
if(size==0)
System.out.println("Heapempty");
else
{
System.out.println("The deleted min elt:"+h[1]);
h[1]=h[size--];
if(size!=0)
percolate(1);
}
}
public
void percolate(int i)
{
while(!isleaf(i))
{
int
small=leftchild(i);
if(
(small<size)&& h[small] > h[small+1])
small+=1;
if(h[small] < h[i])
swap(small,i);
i=small;
}
}
}
class minheap
{
public static
void main(String args[]) throws IOException
{
int
ch=0,cont=0;
heapalg
h1=new heapalg();
do
{
System.out.println("MIN HEAP 1.Insert 2.Delete Min");
DataInputStream din=new DataInputStream(System.in);
try
{
ch=Integer.parseInt(din.readLine());
}
catch(Exception e){}
if(ch==1)
{
h1.insert();
h1.display();
}
else
if(ch==2)
{
h1.delete();
h1.display();
}
else
{
System.out.println("Enter the correct choice");
}
System.out.println("press 1 to continue:");
try
{
cont=Integer.parseInt(din.readLine());
}
catch(Exception e){}
}while(cont==1);
}
}
OUTPUT:
--------
MIN HEAP 1.Insert 2.Delete Min
1
Enter the element:
42
The heap elements are:
42
press 1 to continue:
1
MIN HEAP 1.Insert 2.Delete Min
1
Enter the element:
3
The heap elements are:
3
42
press 1 to continue:
1
MIN HEAP 1.Insert 2.Delete Min
1
Enter the element:
86
The heap elements are:
3
42
86
press 1 to continue:
1
MIN HEAP 1.Insert 2.Delete Min
1
Enter the element:
2
The heap elements are:
2
3
86
42
press 1 to continue:
1
MIN HEAP 1.Insert 2.Delete Min
2
The deleted min elt:2
The heap elements are:
3
42
86
press 1 to continue:
12
No comments:
Post a Comment