AIM
To implement the leftist heap with
insert and deletemin operation using Java.
ALGORITHM
Step 1:
Start the program by defining function.
Step
2:
We know heap as the root node with minimum element.
Step
3:
The insert and delete operations are performed with the
help of combining 2 trees.
Step
4:
The insert operation is performed by combining the two
leftist trees.
Step
5:
The deletemin() is used to delete the minimum element
in the heap.
Step
6:
After the insert and delete operations leftist heap
elements are displayed.
Step
7:
Stop the program.
PROGRAM
LEFTIST HEAP
import java.io.*;
class node
{
public int
data;
public node
LC,RC;
public int shortest;
}
class minleftist
{
node root =
null;
public void
insert()
{
int
newelt=0;
try
{
System.out.println("Enter the element:");
DataInputStream din=new
DataInputStream(System.in);
newelt=Integer.parseInt(din.readLine());
}
catch(Exception e){}
node temp = new node();
temp.data=newelt;
temp.LC=temp.RC=null;
temp.shortest=1;
if(root==null)
root=temp;
else
root=meld(root,temp);
}
public node
meld(node a, node b)
{
if(a.data
> b.data)
{
node t;
t=a;
a=b;
b=t;
}
if(a.RC==null)
a.RC=b;
else
a.RC=meld(a.RC,b);
if((a.LC==null)
|| (a.LC.shortest < a.RC.shortest))
{
node t=new node();
t=a.LC;
a.LC=a.RC;
a.RC=t;
}
if(a.RC==null)
a.shortest=1;
else
a.shortest=a.RC.shortest+1;
return
a;
}
public void
remove()
{
System.out.println("Deleted
element is "+root.data+"\n");
root=meld(root.LC,root.RC);
}
public void
display()
{
if(root==null)
System.out.println("EMPTY");
else
{
System.out.println("\nIn Order");
dispin(root);
}
}
public void
dispin(node currentnode)
{
if(currentnode!=null)
{
dispin(currentnode.LC);
System.out.println(currentnode.data+"
"+"SHORTEST "+currentnode.shortest);
dispin(currentnode.RC);
}
}
};
class LeftistTree
{
public static
void main(String args[ ])throws IOException
{
int ch=0,cont=0;
minleftist m = new minleftist();
do
{
System.out.println("LEFTIST TREE 1.
Insert 2. Delete");
DataInputStream din = new
DataInputStream(System.in);
try
{
ch=Integer.parseInt(din.readLine());
}
catch(Exception e){}
if(ch==1)
{
m.insert();
m.display();
}
else
if(ch==2)
{
m.remove();
m.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:
-------
LEFTIST TREE 1. Insert 2. Delete
1
Enter the element:
50
In Order
50 SHORTEST 1
press 1 to continue:
1
LEFTIST TREE 1. Insert 2. Delete
1
Enter the element:
8
In Order
50 SHORTEST 1
8 SHORTEST 1
press 1 to continue:
1
LEFTIST TREE 1. Insert 2. Delete
1
Enter the element:
13
In Order
50 SHORTEST 1
8 SHORTEST 2
13 SHORTEST 1
press 1 to continue:
1
LEFTIST TREE 1. Insert 2. Delete
1
Enter the element:
11
In Order
50 SHORTEST 1
8 SHORTEST 2
13 SHORTEST 1
11 SHORTEST 1
press 1 to continue:
1
LEFTIST TREE 1. Insert 2. Delete
1
Enter the element:
20
In Order
13 SHORTEST 1
11 SHORTEST 2
20 SHORTEST 1
8 SHORTEST 2
50 SHORTEST 1
press 1 to continue:
1
LEFTIST TREE 1. Insert 2. Delete
1
Enter the element:
18
In Order
13 SHORTEST 1
11 SHORTEST 2
20 SHORTEST 1
8 SHORTEST 2
50 SHORTEST 1
18 SHORTEST 1
press 1 to continue:
1
LEFTIST TREE 1. Insert 2. Delete
1
Enter the element:
2
In Order
13 SHORTEST 1
11 SHORTEST 2
20 SHORTEST 1
8 SHORTEST 2
50 SHORTEST 1
18 SHORTEST 1
2 SHORTEST 1
press 1 to continue:
1
LEFTIST TREE 1. Insert 2. Delete
1
Enter the element:
7
In Order
13 SHORTEST 1
11 SHORTEST 2
20 SHORTEST 1
8 SHORTEST 2
50 SHORTEST 1
18 SHORTEST 1
2 SHORTEST 2
7 SHORTEST 1
press 1 to continue:
1
LEFTIST TREE 1. Insert 2. Delete
2
Deleted element is 2
In Order
13 SHORTEST 1
11 SHORTEST 2
20 SHORTEST 1
8 SHORTEST 2
50 SHORTEST 1
18 SHORTEST 1
RESULT
No comments:
Post a Comment