This is a Java Program to implement Pagoda. A pagoda is a priority queue implemented with a variant of a binary tree. The root points to its children, as in a binary tree. Every other node points back to its parent and down to its leftmost (if it is a right child) or rightmost (if it is a left child) descendant leaf. The basic operation is merge or meld, which maintains the heap property. An element is inserted by merging it as a singleton. The root is removed by merging its right and left children. Merging is bottom-up, merging the leftmost edge of one with the rightmost edge of the other.
Here is the source code of the Java program to implement Pagoda. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/*
* Java Program to Implement Pagoda
*/
import java.util.Scanner;
/* Class PNode */
class PNode
{
PNode left, right;
int data;
/* Constructor */
public PNode(int val)
{
data = val;
left = null;
right = null;
}
}
/* Class Pagoda */
class Pagoda
{
private PNode root;
/* Constructor */
public Pagoda()
{
root = null;
}
/* Function to check if empty */
public boolean isEmpty()
{
return root == null;
}
/* Function to clear */
public void makeEmpty()
{
root = null;
}
/* Function to insert value */
public void insert(int val)
{
PNode newNode = new PNode(val);
root = insert(newNode, root);
}
private PNode insert(PNode newNode, PNode pq)
{
newNode.left = newNode;
newNode.right = newNode;
return (merge(pq, newNode));
}
/* Function to merge two nodes */
private PNode merge(PNode a, PNode b)
{
PNode bota, botb, r, temp;
if (a == null)
return b;
else if (b == null)
return a;
else
{
bota = a.right; a.right = null;
/* bottom of b's leftmost edge */
botb = b.left; b.left = null;
r = null;
/* Merging loop */
while ( bota != null && botb != null )
if ( bota.data < botb.data )
{
temp = bota.right;
if ( r == null )
bota.right = bota;
else
{
bota.right = r.right;
r.right = bota;
}
r = bota;
bota = temp;
}
else
{
temp = botb.left;
if ( r == null )
botb.left = botb;
else
{
botb.left = r.left;
r.left = botb;
}
r = botb;
botb = temp;
}
/* one edge is exhausted, finish merge */
if ( botb == null )
{
a.right = r.right;
r.right = bota;
return( a );
}
else
{
b.left = r.left;
r.left = botb;
return( b );
}
}
}
/* Function to delete */
public void delete()
{
root = delete(root);
}
private PNode delete(PNode pq)
{
PNode le, ri;
/* Deletion on empty queue */
if ( pq == null )
{
System.out.println("Empty");
return null;
}
else
{
/* Find left descendant of root */
if ( pq.left == pq )
le = null;
else
{
le = pq.left;
while ( le.left != pq )
le = le.left;
le.left = pq.left;
}
/* Find right descendant of root */
if ( pq.right == pq )
ri = null;
else
{
ri = pq.right;
while ( ri.right != pq )
ri = ri.right;
ri.right = pq.right;
}
/* merge them */
return merge(le, ri);
}
}
/* Function to print root value */
public void printPagodaRoot()
{
if (root != null)
System.out.print(root.data +"\n");
else
System.out.print("Empty\n");
}
}
/* Class PagodaTest */
public class PagodaTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of Pagoda */
Pagoda pgda = new Pagoda();
System.out.println("Pagoda Test\n");
char ch;
/* Perform tree operations */
do
{
System.out.println("\nPagoda Operations\n");
System.out.println("1. insert ");
System.out.println("2. delete");
System.out.println("3. check empty");
System.out.println("4. clear");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
pgda.insert( scan.nextInt() );
break;
case 2 :
pgda.delete();
break;
case 3 :
System.out.println("Empty status = "+ pgda.isEmpty());
break;
case 4 :
System.out.println("\nCleared");
pgda.makeEmpty();
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/* Display tree */
System.out.print("\nRoot Element : ");
pgda.printPagodaRoot();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Pagoda Test Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 1 Enter integer element to insert 45 Root Element : 45 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 1 Enter integer element to insert 23 Root Element : 45 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 1 Enter integer element to insert 57 Root Element : 57 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 1 Enter integer element to insert 19 Root Element : 57 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 1 Enter integer element to insert 24 Root Element : 57 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 1 Enter integer element to insert 93 Root Element : 93 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 1 Enter integer element to insert 87 Root Element : 93 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 2 Root Element : 87 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 2 Root Element : 57 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 2 Root Element : 45 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 2 Root Element : 24 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 2 Root Element : 23 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 2 Root Element : 19 Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 2 Root Element : Empty Do you want to continue (Type y or n) y Pagoda Operations 1. insert 2. delete 3. check empty 4. clear 3 Empty status = true Root Element : Empty Do you want to continue (Type y or n) n
Sanfoundry Global Education & Learning Series – 1000 Java Programs.
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.
Related Posts:
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Check Computer Science Books
- Check Data Structure Books
- Check Programming Books