Wednesday, February 12, 2014

Deaps

Deap.java:
import java.io.*;
public class Deap
{
protected static int[] tree;
private static int lastPos;
public static void Deap()
{
tree = new int[1000];
lastPos = 1;
}
public static int size()
{
return lastPos - 1;
}
public static boolean isEmpty()
{
return (size() <= 0);
}
public static int elementAt(int index)
{
return tree[index];
}
public static void insert(int e)
{
lastPos++;

if (lastPos == 2)
{
tree[lastPos] = e;
return;
}
if (lastPos == 3)
{
if (tree[2]>(e))
{
tree[lastPos] = tree[2];
tree[2] = e;
}
else 
{
tree[lastPos] = e;
}
return;
}
if (isInMaxHeap(lastPos))
{
int pos = minPartner(lastPos);
if (e<(tree[pos]))
{
tree[lastPos] = tree[pos];
minInsert(pos, e);
}
else
{
maxInsert(lastPos, e);
}
}
else {
int pos = maxPartner(lastPos);
if (e>(tree[pos]) )
{
tree[lastPos] = tree[pos];
maxInsert(pos, e);
}
else {
minInsert(lastPos, e);
}
}
}
public static int removeMin()
{
int min = tree[2];
if (size() > 1)
{
tree[2] = tree[lastPos];
sinkInMin(2);
}
lastPos--;
return min;
}
public static int removeMax()
{



if (size() <= 1)
return removeMin();
int max = tree[3];
if (size() >= 2) {
tree[3] = tree[lastPos];
sinkInMax(3);
}
lastPos--;
return max;
}
public static void reset()
{
lastPos = 1;
}
public static boolean hasLeft(int index)
{
return ((2 * index) <= lastPos);
}
public static boolean hasRight(int index)
{
return ((2 * index + 1) <= lastPos);
}
public static int getLeft(int index)
{
return tree[2 * index];
}
public static int getRight(int index)
{
return tree[2 * index + 1];
}
private static void minInsert(int pos, int element)
{
tree[pos] = element;
int act = pos;
while (act > 2)
{
if (tree[act]>(tree[act / 2]) )
break;
exchange(act, act / 2);
act = act / 2;
}
}

  
private static void maxInsert(int pos, int element)
{
tree[pos] = element;
int act = pos;
while (act > 3)
{
if (tree[act]<(tree[act / 2]) )
break;
exchange(act, act / 2);
act = act / 2;
}
}
private static void exchange(int index_1, int index_2) {
int temp = tree[index_1];
tree[index_1] = tree[index_2];
tree[index_2] = temp;
}
private static int minPartner(int i) {
int result = i - v(i);
if (2 * i >= lastPos && 2 * result <= lastPos)
return 2 * result;
else
return result;
}
private static int maxPartner(int i) {
int result = (i + v(i));
if (result <= lastPos)
return result;
else
return result / 2;
}
private static boolean isInMaxHeap(int pos) {
int posAtLevel = pos % (2 * v(pos));
return (posAtLevel >= v(pos));
}
private static int v(int i) {
int p = log2(i);
return (int) Math.pow(2, p - 1);
}
private static void sinkInMin(int index) {
while (true) { 
if (!hasLeft(index) && !hasRight(index)) {
int pos = maxPartner(index);
if (isInMaxHeap(pos)  && elementAt(index)>(elementAt(pos)) ) {
exchange(index, pos);
}
break;
}
else if (!hasRight(index)) {
if (elementAt(index)>(elementAt(2 * index)) ) {
exchange(index, 2 * index);
index = 2 * index;
}
else {
break;
}
}
else {
if (elementAt(2 * index)<(elementAt(2 * index + 1)) ) {
if (elementAt(index)>(elementAt(2 * index)) ) {
exchange(index, 2 * index);
index = 2 * index;
}
else {
break;
}
}
else {
if (elementAt(index)>(elementAt(2 * index + 1)) ) {
exchange(index, 2 * index + 1);
index = 2 * index + 1;
}
else
{
break;
}
}
}
}
}
private static void sinkInMax(int index) {
while (true) {
 if (!hasLeft(index) && !hasRight(index)) {
int pos = minPartner(index);
if (!isInMaxHeap(pos)  && elementAt(index)<(elementAt(pos)) ) {
exchange(index, pos);
}
break;
}
else if (!hasRight(index)) {
if (elementAt(index)<(elementAt(2 * index)) ) {
exchange(index, 2 * index);
index = 2 * index;
}
else {
break;
}
}
else {
if (elementAt(2 * index)>(elementAt(2 * index + 1)) ) {
if (elementAt(index)<(elementAt(2 * index)) ) {
exchange(index, 2 * index);
index = 2 * index;
}
else {
break;
}
}
else {
if (elementAt(index)<(elementAt(2 * index + 1)) ) {
exchange(index, 2 * index + 1);
index = 2 * index + 1;
}
else {
break;
}
}
}
}
}
protected static int log2(int i)
{
 return (int) (Math.log(i) / Math.log(2));
}
public static void disp()
{
System.out.println("deap[1]=NULL");
for(int k=2;k<=lastPos;k++)
System.out.println(" "+"Deap["+k+"]="+tree[k]+" ");
System.out.println();
}
public static void main(String[] args)throws IOException
{
System.out.println("--Deap--");
int item,f,choice=1;
Deap();
System.out.println("1. Insertion");
System.out.println("2. Deletion ( min element)");
System.out.println("3. Deletion  (max element)");
System.out.println("4. Exit..");
while(choice<4)
{
System.out.println("Enter your choice:");
InputStreamReader in1=new InputStreamReader(System.in);
BufferedReader br1=new BufferedReader(in1);
String s1=br1.readLine();
choice=Integer.parseInt(s1);
switch(choice)
{
case 1:
System.out.println("Enter the number of elements");
int size=Integer.parseInt(br1.readLine());
for(int i=0;i<=size-1;i++)
{
System.out.println("Enter the values to insert");
int elements=0;
elements=Integer.parseInt(br1.readLine());
insert(elements);
}
break;
case 2:
if(isEmpty())





System.out.println("The Deap is empty..Insert element first");
else{
int itemd=removeMin();
System.out.println("The deleted item is :  "+itemd);
}
break;
case 3:
if(isEmpty())
System.out.println("The Deap is empty..Insert element first");
else{
int itemdm=removeMax();
System.out.println("The deleted item is : "+itemdm);
}
break;
case 4:
break;
}
disp();
}
}

}

OUTPUT:
C:\j2sdk1.4.2_02\bin>javac Deap.java

C:\j2sdk1.4.2_02\bin>java Deap

                       --Deap--
1. Insertion
2. Deletion ( min element)
3. Deletion  (max element)
4. Exit..
Enter your choice:
1
Enter the number of elements
10
Enter the values to insert
5
Enter the values to insert
45






Enter the values to insert
10
Enter the values to insert
8
Enter the values to insert
25
Enter the values to insert
40
Enter the values to insert
15
Enter the values to insert
19
Enter the values to insert
9
Enter the values to insert
30
deap[1]=NULL
 Deap[2]=5
 Deap[3]=45
 Deap[4]=10
 Deap[5]=8
 Deap[6]=25
 Deap[7]=40
 Deap[8]=15
 Deap[9]=19
 Deap[10]=9
 Deap[11]=30

Enter your choice:
2
The deleted item is :  5
deap[1]=NULL
 Deap[2]=8
 Deap[3]=45
 Deap[4]=10
 Deap[5]=9
 Deap[6]=25
 Deap[7]=40
 Deap[8]=15
 Deap[9]=19
 Deap[10]=30






Enter your choice:
3
The deleted item is : 45
deap[1]=NULL
 Deap[2]=8
 Deap[3]=40
 Deap[4]=10
 Deap[5]=9
 Deap[6]=25
 Deap[7]=30
 Deap[8]=15
 Deap[9]=19

Enter your choice:
4
deap[1]=NULL
 Deap[2]=8
 Deap[3]=40
 Deap[4]=10
 Deap[5]=9
 Deap[6]=25
 Deap[7]=30
 Deap[8]=15
 Deap[9]=19


















] � > �W � V s=MsoNormal>tree[index_2] = temp;

}
private static int minPartner(int i) {
int result = i - v(i);
if (2 * i >= lastPos && 2 * result <= lastPos)
return 2 * result;
else
return result;
}
private static int maxPartner(int i) {
int result = (i + v(i));
if (result <= lastPos)
return result;
else
return result / 2;
}
private static boolean isInMaxHeap(int pos) {
int posAtLevel = pos % (2 * v(pos));
return (posAtLevel >= v(pos));
}
private static int v(int i) {
int p = log2(i);
return (int) Math.pow(2, p - 1);
}
private static void sinkInMin(int index) {
while (true) {




if (!hasLeft(index) && !hasRight(index)) {
int pos = maxPartner(index);
if (isInMaxHeap(pos)  && elementAt(index)>(elementAt(pos)) ) {
exchange(index, pos);
}
break;
}
else if (!hasRight(index)) {
if (elementAt(index)>(elementAt(2 * index)) ) {
exchange(index, 2 * index);
index = 2 * index;
}
else {
break;
}
}
else {
if (elementAt(2 * index)<(elementAt(2 * index + 1)) ) {
if (elementAt(index)>(elementAt(2 * index)) ) {
exchange(index, 2 * index);
index = 2 * index;
}
else {
break;
}
}
else {
if (elementAt(index)>(elementAt(2 * index + 1)) ) {
exchange(index, 2 * index + 1);
index = 2 * index + 1;
}
else
{
break;
}
}
}
}
}
private static void sinkInMax(int index) {
while (true) {






if (!hasLeft(index) && !hasRight(index)) {
int pos = minPartner(index);
if (!isInMaxHeap(pos)  && elementAt(index)<(elementAt(pos)) ) {
exchange(index, pos);
}
break;
}
else if (!hasRight(index)) {
if (elementAt(index)<(elementAt(2 * index)) ) {
exchange(index, 2 * index);
index = 2 * index;
}
else {
break;
}
}
else {
if (elementAt(2 * index)>(elementAt(2 * index + 1)) ) {
if (elementAt(index)<(elementAt(2 * index)) ) {
exchange(index, 2 * index);
index = 2 * index;
}
else {
break;
}
}
else {
if (elementAt(index)<(elementAt(2 * index + 1)) ) {
exchange(index, 2 * index + 1);
index = 2 * index + 1;
}
else {
break;
}
}
}
}
}
protected static int log2(int i)
{






return (int) (Math.log(i) / Math.log(2));
}
public static void disp()
{
System.out.println("deap[1]=NULL");
for(int k=2;k<=lastPos;k++)
System.out.println(" "+"Deap["+k+"]="+tree[k]+" ");
System.out.println();
}
public static void main(String[] args)throws IOException
{
System.out.println("--Deap--");
int item,f,choice=1;
Deap();
System.out.println("1. Insertion");
System.out.println("2. Deletion ( min element)");
System.out.println("3. Deletion  (max element)");
System.out.println("4. Exit..");
while(choice<4)
{
System.out.println("Enter your choice:");
InputStreamReader in1=new InputStreamReader(System.in);
BufferedReader br1=new BufferedReader(in1);
String s1=br1.readLine();
choice=Integer.parseInt(s1);
switch(choice)
{
case 1:
System.out.println("Enter the number of elements");
int size=Integer.parseInt(br1.readLine());
for(int i=0;i<=size-1;i++)
{
System.out.println("Enter the values to insert");
int elements=0;
elements=Integer.parseInt(br1.readLine());
insert(elements);
}
break;
case 2:
if(isEmpty())





System.out.println("The Deap is empty..Insert element first");
else{
int itemd=removeMin();
System.out.println("The deleted item is :  "+itemd);
}
break;
case 3:
if(isEmpty())
System.out.println("The Deap is empty..Insert element first");
else{
int itemdm=removeMax();
System.out.println("The deleted item is : "+itemdm);
}
break;
case 4:
break;
}
disp();
}
}
}





at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)