Java Program to Implement Pagoda

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.

  1. /*
  2.  *    Java Program to Implement Pagoda
  3.  */
  4.  
  5. import java.util.Scanner;
  6.  
  7. /* Class PNode */
  8. class PNode
  9. {
  10.     PNode left, right;
  11.     int data;
  12.  
  13.     /* Constructor */
  14.     public PNode(int val)
  15.     {
  16.         data = val;
  17.         left = null;
  18.         right = null;
  19.     }
  20. }
  21.  
  22. /* Class Pagoda */
  23. class Pagoda
  24. {
  25.     private PNode root;
  26.  
  27.     /* Constructor */
  28.     public Pagoda()
  29.     {
  30.         root = null;
  31.     }
  32.     /* Function to check if empty */
  33.     public boolean isEmpty()
  34.     {
  35.         return root == null;
  36.     }
  37.     /* Function to clear */
  38.     public void makeEmpty()
  39.     {
  40.         root = null;
  41.     }
  42.     /* Function to insert value */
  43.     public void insert(int val)
  44.     {
  45.         PNode newNode = new PNode(val);
  46.         root = insert(newNode, root);
  47.     }
  48.     private PNode insert(PNode newNode, PNode pq)
  49.     {
  50.         newNode.left = newNode;
  51.         newNode.right = newNode;
  52.         return (merge(pq, newNode));
  53.     }
  54.     /* Function to merge two nodes */
  55.     private PNode merge(PNode a, PNode b)
  56.     {
  57.         PNode bota, botb, r, temp;
  58.         if (a == null)
  59.             return b;
  60.         else if (b == null)
  61.             return a;
  62.         else
  63.         {
  64.             bota = a.right;    a.right = null;
  65.             /* bottom of b's leftmost edge */
  66.             botb = b.left;    b.left = null;
  67.             r = null;
  68.             /* Merging loop */
  69.             while ( bota != null && botb != null )
  70.                 if ( bota.data < botb.data ) 
  71.                 {
  72.                     temp = bota.right;
  73.                     if ( r == null )
  74.                         bota.right = bota;
  75.                     else
  76.                     {
  77.                         bota.right = r.right;
  78.                         r.right = bota;
  79.                     }
  80.                     r = bota;
  81.                     bota = temp;
  82.                 }
  83.                 else
  84.                 {
  85.                     temp = botb.left;
  86.                     if ( r == null )
  87.                         botb.left = botb;
  88.                     else
  89.                     {
  90.                         botb.left = r.left;
  91.                         r.left = botb;
  92.                     }
  93.                     r = botb;
  94.                     botb = temp;
  95.                 }
  96.             /* one edge is exhausted, finish merge */
  97.             if ( botb == null )
  98.             {
  99.                 a.right = r.right;
  100.                 r.right = bota;
  101.                 return( a );
  102.             }
  103.             else
  104.             {
  105.                 b.left = r.left;
  106.                 r.left = botb;
  107.                 return( b );
  108.             }
  109.         }
  110.     }
  111.     /* Function to delete */
  112.     public void delete()
  113.     {
  114.         root = delete(root);
  115.     }
  116.     private PNode delete(PNode pq)
  117.     {
  118.         PNode le, ri;
  119.         /* Deletion on empty queue */
  120.         if ( pq == null ) 
  121.         {
  122.             System.out.println("Empty");
  123.             return null;
  124.         } 
  125.         else
  126.         {
  127.             /* Find left descendant of root */
  128.             if ( pq.left == pq ) 
  129.                 le = null;
  130.             else 
  131.             {
  132.                 le = pq.left;
  133.                 while ( le.left != pq ) 
  134.                     le = le.left;
  135.                 le.left = pq.left;
  136.             }
  137.             /* Find right descendant of root */
  138.             if ( pq.right == pq ) 
  139.                 ri = null;
  140.             else 
  141.             {
  142.                 ri = pq.right;
  143.                 while ( ri.right != pq ) 
  144.                     ri = ri.right;
  145.                 ri.right = pq.right;
  146.             }
  147.             /* merge them */
  148.             return merge(le, ri);
  149.         }        
  150.     }
  151.     /* Function to print root value */
  152.     public void printPagodaRoot()
  153.     {
  154.         if (root != null)
  155.             System.out.print(root.data +"\n");
  156.         else
  157.             System.out.print("Empty\n");
  158.     }    
  159. }
  160.  
  161.  
  162. /* Class PagodaTest */
  163.  public class PagodaTest
  164.  {
  165.      public static void main(String[] args)
  166.      {            
  167.         Scanner scan = new Scanner(System.in);
  168.         /* Creating object of Pagoda */
  169.         Pagoda pgda = new Pagoda(); 
  170.         System.out.println("Pagoda Test\n");          
  171.         char ch;
  172.         /*  Perform tree operations  */
  173.         do    
  174.         {
  175.             System.out.println("\nPagoda Operations\n");
  176.             System.out.println("1. insert ");
  177.             System.out.println("2. delete"); 
  178.             System.out.println("3. check empty");
  179.             System.out.println("4. clear");
  180.  
  181.             int choice = scan.nextInt();            
  182.             switch (choice)
  183.             {
  184.             case 1 : 
  185.                 System.out.println("Enter integer element to insert");
  186.                 pgda.insert( scan.nextInt() );                     
  187.                 break;                          
  188.             case 2 : 
  189.                 pgda.delete(); 
  190.                 break;                          
  191.             case 3 :
  192.                 System.out.println("Empty status = "+ pgda.isEmpty());
  193.                 break;
  194.             case 4 : 
  195.                 System.out.println("\nCleared");
  196.                 pgda.makeEmpty();
  197.                 break;            
  198.             default : 
  199.                 System.out.println("Wrong Entry \n ");
  200.                 break;   
  201.             }
  202.             /*  Display tree  */ 
  203.  
  204.             System.out.print("\nRoot Element : ");
  205.             pgda.printPagodaRoot();
  206.  
  207.             System.out.println("\nDo you want to continue (Type y or n) \n");
  208.             ch = scan.next().charAt(0);                        
  209.         } while (ch == 'Y'|| ch == 'y');               
  210.      }
  211.  }

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.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.