AIM
To implement program for deaps
structure with insert and delete operations using Java.
ALGORITHM
Step 1:
Start the program by creating Deap Structure.
Step 2:
Perform insert and delete functions.
Step 3:
The insert() is done with 2 methods namely maxinsert()
and mininsert().
Step 4:
The delete() is done with 2 methods namely deletemax()
and deletemin()
Step
5:
The leftChild and rightChild are compared and the
appropriate element is placed in the root node.
Step 6:
After the insert and delete operation Deap elements are
displayed.
Step 7:
Stop of the program.
PROGRAM
DEAPS
import java.io.*;
class deapsalg
{
int
maxsize=100,size;
int[] h=new
int[maxsize+1];
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 deaps elements are:");
for(int
i=1;i<=size+1;i++)
System.out.println("\n"+h[i]);
}
public int
MaxHeap(int i)
{
int t=i;
while(t!=2
&& t!=3)
t=t/2;
if(t==2)
{
return 0;
}
else
{
return 1;
}
}
public int
MinPartner(int p)
{
int
powvalue=(int) ((Math.floor(Math.log(p)/Math.log(2)))-1);
int
partner=p-(int)(Math.pow(2,powvalue));
return
partner;
}
public int
MaxPartner(int p)
{
int
powvalue=(int) ((Math.floor(Math.log(p)/Math.log(2)))-1);
int
partner=p+(int)(Math.pow(2,powvalue));
if(partner>size+1)
partner/=2;
return
partner;
}
public void
MinInsert(int i)
{
while
(parent(i)!=1 && (h[parent(i)]>h[i]))
{
int
par=parent(i);
swap(par,i);
i=par;
}
}
public void
MaxInsert(int i)
{
while
(parent(i) !=1 && (h[parent(i)]<h[i]))
{
int
par=parent(i);
swap(par,i);
i=par;
}
}
public void
insert()
{
int
newelt=0;
size++;
if(size>maxsize)
System.out.println("Deap full");
else
{
try
{
System.out.println("Enter the element:");
DataInputStream din=new
DataInputStream(System.in);
newelt=Integer.parseInt(din.readLine());
}
catch(Exception
e){}
if(size==1)
{
h[2]=newelt;
return;
}
int
p=size+1;
h[p]=newelt;
switch(MaxHeap(p))
{
case
1:
int partner=MinPartner(p);
if(h[partner]>h[p])
{
swap(p,partner);
MinInsert(partner);
}
else
MaxInsert(p);
break;
case
0:
partner=MaxPartner(p);
if(h[partner]<h[p])
{
swap(p,partner);
MaxInsert(partner);
}
else
MinInsert(p);
break;
default:
System.out.println("ERROR");
}
}
}
public void
deletemin()
{
if(size==0)
System.out.println("Deap
empty");
else
{
System.out.println("The deleted min elt:"+ h[2]);
int i;
int
p=size+1;
int
t=h[p];
size--;
int
small;
for(
i=2;2*i<=size+1;i=small)
{
if(h[rightchild(i)]<h[leftchild(i)])
small=rightchild(i);
else
small=leftchild(i);
h[i]=h[small];
}
p=i; t
h[p]=t;
for(i=2;i<=size+1;i++)
{
switch(MaxHeap(i))
{
case
1:
int partner=MinPartner(i);
if(h[partner]>h[i])
{
swap(i,partner);
MinInsert(partner);
}
else
MaxInsert(i);
break;
case
0:
partner=MaxPartner(i);
if(h[partner]<h[i])
{
swap(i,partner);
MaxInsert(partner);
}
else
MinInsert(i);
break;
default:
System.out.println("ERROR");
}
}
}
}
public void
deletemax()
{
if(size==0)
System.out.println("Deap empty");
else
{
System.out.println("The deleted max elt:"+ h[3]);
int i;
int
p=size+1;
int
t=h[p];
size--;
int big;
for(
i=3;2*i<=size+1;i=big)
{
if(h[rightchild(i)]>h[leftchild(i)])
big=rightchild(i);
else
big=leftchild(i);
h[i]=h[big];
}
p=i;
h[p]=t;
for(i=2;i<=size+1;i++)
{
switch(MaxHeap(i))
{
case
1:
int partner=MinPartner(i);
if(h[partner]>h[i])
{
swap(i,partner);
MinInsert(partner);
}
else
MaxInsert(i);
break;
case 0:
partner=MaxPartner(i);
if(h[partner]<h[i])
{
swap(i,partner);
MaxInsert(partner);
}
else
MinInsert(i);
break;
default:
System.out.println("ERROR");
}
}
}
}
}
public class deaps
{
public static
void main(String args[]) throws IOException
{
int
ch=0,cont=0;
deapsalg
h1=new deapsalg();
do
{
System.out.println("DEAPs 1.Insert 2.Delete Min 3.Delete
Max");
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.deletemin();
h1.display();
}
else
if(ch==3)
{
h1.deletemax();
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:
--------
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
20
The deaps elements are:
0
20
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
5
The deaps elements are:
0
5
20
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
3
The deaps elements are:
0
3
20
5
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
7
The deaps elements are:
0
3
20
5
7
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
11
The deaps elements are:
0
3
20
5
7
11
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
55
The deaps elements are:
0
3
55
5
7
11
20
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
77
The deaps elements are:
0
3
77
5
7
55
20
11
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
88
The deaps elements are:
0
3
88
5
7
77
20
11
55
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
17
The deaps elements are:
0
3
88
5
7
77
20
11
55
17
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
1
The deaps elements are:
0
1
88
5
3
77
20
11
55
17
7
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
1
Enter the element:
100
The deaps elements are:
0
1
100
5
3
88
20
11
55
17
7
77
press 1 to continue:
1
DEAPs 1.Insert 2.Delete Min 3.Delete Max
2
The deleted min elt:1
The deaps elements are:
0
3
100
5
7
88
77
11
55
17
20
press 1 to continue:
RESULT
Thus the program for Deaps using Java has been implemented.
No comments:
Post a Comment