In Java, a Pagoda is a priority queue enforced with a modification of a binary tree. The binary tree is constrained to have priority queue ordering which holds that the parent should be larger than its descendants. A detailed analysis shows that the Pagoda provides a highly efficient implementation of priority queue where the efficiency is measured through average runtime.
A Pagoda is quite similar to that of a heap as Pagodas are used for impermeable priority queues and heaps are used for non-merge able priority queues.
The root of the Pagoda points to its children similar to a binary tree. Every other node points back to its parent and all the way down to its leftmost (if it’s a right child) or rightmost (if it’s a left child) descendant leaf. The key operation is merge or meld, which upholds the heap property.
A node is inserted by merging it as a singleton. The root is removed by merging its two children (left and right). Merging is a bottom-up approach, merging the leftmost edge of one with the rightmost edge of the opposite.
There are two pointers Left(Node) and Right(Node), which are defined as follows
- ROOT
- If R is the Root of the tree T — Right(R) points to the bottom of the right branch of the T and Left(R) to the bottom of the left branch of the T.
- LEFT CHILD
- If K is a left-child in T — Left(K) points to the parent of K and Right(K) to the bottom of the right branch of T.
- RIGHT CHILD
- If K is a right-child in T — Right(K) points to the parent of K and Left(K) to the bottom of the left branch of T.
Major Operations in Pagoda is as follows:
- UNION: All elements of pagoda Q’ are added to pagoda Q and Q’ is discarded.
- Q ← [Q+Q’]
- INSERT: The element k is added to the pagoda Q
- Q ← [Q+k]
- DELETE: The element k is removed from the pagoda Q (This operation is meaningful only if k belongs to Q)
- Q<-Q/k
Illustration: The difference in the representation of binary tree and Pagoda
The Orange arrows represent Left Child Pointers and the Green arrows represent Right Child Pointers. Notice that the leaf nodes point to themselves as they don’t have branches.
Procedure:
- INSERT – By considering a single key p as a pagoda, we can treat INSERT as a special case of UNION.
- The best and most effective way to insert an item into a Pagoda is to simply append it at the end.
- This guarantees to maintain the complete tree property. But, this would mean violating the heap property i.e. The parent node in the Pagoda is always greater than its children.
- Perform action on Pagoda using methods discussed below
- delete()
- Deleting a key k is possible in pagodas without the usage of extra links. To delete k, it is enough to find links to the right and left branches of the sub-trees having k as the root. Once these pointers are found, we continue by performing the union of D and G in that order.
- isEmpty()
- If Root equals NULL, returns true. Else returns false.
- clear()
- Makes root as null to pagoda empty.
- delete()
Example:
Java
// Java Program to implement Pagoda// Pagoda is simply a priority queue// which includes variations of binary tree// Class for creating a single nodeclass GFG { GFG left, right; int data; // Constructor of this class public GFG(int val) { // Node stores the value as data data = val; // Left pointer is initially set as NULL left = null; // Right pointer initially set as NULL right = null; }}// Helper class// Pagoda classclass Pagoda { // Member variable of this class private GFG root; // Constructor of this class public Pagoda() { // Initializing the root in the Pagoda as NULL root = null; } // Method 1 // To check if Pagoda is empty public boolean isEmpty() { // Returns true if root is equal to null // else returns false return root == null; } // Method 2 // To clear the entire Pagoda public void clear() { // Clears or Empties the entire Pagoda root = null; } // Method 3 // To insert node into the Pagoda public void insert(int val) { // Creates a new node with data as val GFG node = new GFG(val); // Inserts into Pagoda root = insert(node, root); } private GFG insert(GFG node, GFG queue) { // Initially the new node has no left child // so the left pointer points to itself node.left = node; // Initially the new node has no right child // so the right pointer points to itself node.right = node; // Calling merge to attach new node to Pagoda return (merge(queue, node)); } // Method 4 // To merge new node to Pagoda // New node is inserted as a leaf node // and to maintain the heap property // if the new node is greater than its parent // both nodes are swapped and this continues till // all parents are greater than its children private GFG merge(GFG root, GFG newnode) { GFG botroot, botnew, r, temp; if (root == null) // If root is null, after merge - only newnode return newnode; else if (newnode == null) // If newnode is null, after merge - only root return root; else { // Bottom of root's rightmost edge botroot = root.right; root.right = null; // bottom of newnode's leftmost edge - mostly // itself botnew = newnode.left; newnode.left = null; r = null; // Iterating via loop for merging while (botroot != null && botnew != null) { // // Comparing parent and child if (botroot.data < botnew.data) { temp = botroot.right; if (r == null) botroot.right = botroot; else { botroot.right = r.right; r.right = botroot; } r = botroot; botroot = temp; } else { // Comparing parent and child temp = botnew.left; if (r == null) botnew.left = botnew; else { // Swapping of child and parent botnew.left = r.left; r.left = botnew; } r = botnew; botnew = temp; } } // Merging stops after either // botnew or botroot becomes null // Condition check when // node(botnew) is null if (botnew == null) { root.right = r.right; r.right = botroot; return (root); } else { // botroot is null newnode.left = r.left; r.left = botnew; return (newnode); } } } // Methods 5 // To delete a particular node public void delete() { root = delete(root); } private GFG delete(GFG queue) { GFG l, r; // Deleting when Pagoda is already empty if (queue == null) { // Display message System.out.println("Empty"); return null; } // Deleting a left child else { if (queue.left == queue) l = null; else { l = queue.left; while (l.left != queue) l = l.left; l.left = queue.left; } // Deleting a right child if (queue.right == queue) r = null; else { r = queue.right; while (r.right != queue) r = r.right; r.right = queue.right; } // Merging Pagoda after deletion return merge(l, r); } } // Method 6 // To print root of Pagoda public void printRoot() { if (root != null) // Display and print the data of the root System.out.println(root.data); else // Display message when root doesn't exist // This implies Pagoda is empty System.out.println("Empty"); }}// Main classpublic class GFG2 { // Main driver method public static void main(String[] args) { // Creating an object of Pagoda type // Object is created of user defined type Pagoda p = new Pagoda(); // Adding elements to the object created above // Custom inputs - 10,30,20,50,40. // Operation 1 on Pagoda // Input 1 // Inserting element - 10 p.insert(10); // Display message System.out.print("Root Element : "); // Printing Root p.printRoot(); // Operation 2 on Pagoda // Input 2 // Inserting element - 30 p.insert(30); // Display message System.out.print("Root Element : "); // Printing Root p.printRoot(); // Operation 3 on Pagoda // Input 3 // Inserting element - 20 p.insert(20); // Display message System.out.print("Root Element : "); // Printing Root p.printRoot(); // Operation 4 on Pagoda // Input 4 // Inserting element - 50 p.insert(50); // Display message System.out.print("Root Element : "); // Printing Root p.printRoot(); // Operation 5 on Pagoda // Input 5 // Inserting element - 40 p.insert(40); // Display message System.out.print("Root Element : "); // Printing Root p.printRoot(); // Operation 6 on Pagoda // Now, deleting an element from above // inserted elements p.delete(); // Display message System.out.print("Root Element : "); // Printing Root p.printRoot(); // Operation 7 on Pagoda // Again deleting an element from above // inserted elements using delete() method p.delete(); // Display message System.out.print("Root Element : "); // Printing the Root p.printRoot(); // Operation 8 on Pagoda // Condition check using isEmpty() // Checking whether the Pagoda is empty or not // by calling isEmpty() over Pagoda System.out.println("Empty status: " + p.isEmpty()); // Emptying out the Pagoda // using clear() method p.clear(); // Again checking if Pagoda is empty // using the isEmpty() method System.out.println("Empty status: " + p.isEmpty()); }} |
Output
Root Element : 10 Root Element : 30 Root Element : 30 Root Element : 50 Root Element : 50 Root Element : 40 Root Element : 30 Empty status: false Empty status: true
