En Java, una Pagoda es una cola de prioridad impuesta con una modificación de un árbol binario. El árbol binario está restringido para tener un orden de cola de prioridad que sostiene que el padre debe ser más grande que sus descendientes. Un análisis detallado muestra que Pagoda proporciona una implementación altamente eficiente de la cola de prioridad donde la eficiencia se mide a través del tiempo de ejecución promedio.
Una pagoda es bastante similar a la de un montón, ya que las pagodas se usan para colas de prioridad impermeables y los montones se usan para colas de prioridad no fusionables.
La raíz de la Pagoda apunta a sus hijos de forma similar a un árbol binario. Todos los demás Nodes apuntan a su padre y hasta su hoja descendiente más a la izquierda (si es un hijo derecho) o más a la derecha (si es un hijo izquierdo). La operación clave es fusionar o fusionar, lo que mantiene la propiedad del montón.
Un Node se inserta fusionándolo como un singleton. La raíz se elimina fusionando sus dos hijos (izquierdo y derecho). La fusión es un enfoque de abajo hacia arriba, fusionando el borde más a la izquierda de uno con el borde más a la derecha del opuesto.
Hay dos punteros Izquierda (Node) y Derecha (Node), que se definen de la siguiente manera
- RAÍZ
- Si R es la raíz del árbol T , la derecha (R) apunta a la parte inferior de la rama derecha de la T y la izquierda (R) a la parte inferior de la rama izquierda de la T.
- NIÑO IZQUIERDO
- Si K es un hijo izquierdo en T , Left(K) apunta al padre de K y Right(K) a la parte inferior de la rama derecha de T.
- NIÑO DERECHO
- Si K es un hijo derecho en T , Right(K) apunta al padre de K e Left(K) a la parte inferior de la rama izquierda de T.
Las principales operaciones en Pagoda son las siguientes:
- UNIÓN: Todos los elementos de la pagoda Q’ se agregan a la pagoda Q y Q’ se descarta.
- Q ← [Q+Q’]
- INSERTAR: El elemento k se agrega a la pagoda Q
- Q ← [Q+k]
- ELIMINAR: El elemento k se elimina de la pagoda Q (Esta operación solo tiene sentido si k pertenece a Q)
- Q<-Q/k
Ilustración: La diferencia en la representación del árbol binario y Pagoda
Las flechas naranjas representan punteros secundarios izquierdos y las flechas verdes representan punteros secundarios derechos. Observe que los Nodes de hoja apuntan a sí mismos ya que no tienen ramas.
Procedimiento:
- INSERT: al considerar una sola tecla p como una pagoda, podemos tratar INSERT como un caso especial de UNION.
- La forma mejor y más efectiva de insertar un elemento en una pagoda es simplemente agregarlo al final.
- Esto garantiza mantener la propiedad completa del árbol. Pero, esto significaría violar la propiedad del montón, es decir, el Node padre en la Pagoda siempre es mayor que sus hijos.
- Realice acciones en Pagoda usando los métodos que se describen a continuación.
- Eliminar()
- Es posible eliminar una clave k en pagodas sin el uso de enlaces adicionales. Para eliminar k, es suficiente encontrar enlaces a las ramas derecha e izquierda de los subárboles que tienen k como raíz. Una vez encontrados estos punteros, continuamos realizando la unión de D y G en ese orden.
- esta vacio()
- Si Root es igual a NULL, devuelve verdadero. Else devuelve falso.
- clear()
- Hace que la raíz sea nula para la pagoda vacía.
- Eliminar()
Ejemplo:
Java
// Java Program to implement Pagoda
// Pagoda is simply a priority queue
// which includes variations of binary tree
// Class for creating a single node
class 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 class
class 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 class
public 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());
}
}
Producción
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
Publicación traducida automáticamente
Artículo escrito por deepthimgs y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA