Hispanopedia WikiEn informática, un montón combinable aleatorio (también llamado montón combinable o cola de prioridad combinable aleatoria ) es una estructura de datos basada en una cola de prioridad cuya estructura subyacente es también un árbol binario ordenado por montón . Sin embargo, no existen restricciones en la forma del árbol binario subyacente.
Este enfoque presenta varias ventajas sobre estructuras de datos similares. Ofrece mayor simplicidad: todas las operaciones para el montón combinable aleatorio son fáciles de implementar y los factores constantes en sus límites de complejidad son pequeños. Tampoco es necesario preservar las condiciones de equilibrio ni información satélite dentro de los nodos. Por último, esta estructura tiene una buena eficiencia temporal en el peor de los casos. El tiempo de ejecución de cada operación individual es, como máximo, logarítmico con alta probabilidad . [ 1 ]
Operaciones
El montículo combinable aleatorio admite varias operaciones comunes: inserción, eliminación y una operación de búsqueda, findMin. Las operaciones de inserción y eliminación se implementan mediante una operación adicional específica del montículo combinable, Meld(Q1, Q2).
Fusión
El objetivo básico de la operación de fusión (también llamada meld) es tomar dos montículos (tomando los nodos raíz de cada uno), Q1 y Q2, y fusionarlos, devolviendo como resultado un único nodo de montículo. Este nodo de montículo es el nodo raíz de un montículo que contiene todos los elementos de los dos subárboles con raíz en Q1 y Q2.
Una característica interesante de esta operación de fusión es que se puede definir recursivamente. Si alguno de los montones es nulo, la fusión se realiza con un conjunto vacío y el método simplemente devuelve el nodo raíz del montón no vacío. Si tanto Q1 como Q2 no son nulos, se comprueba si Q1 > Q2. Si lo es, se intercambian. De esta forma, se garantiza que Q1 < Q2 y que el nodo raíz del montón fusionado contendrá Q1. A continuación, fusionamos recursivamente Q2 con Q1.left o Q1.right. En este paso entra en juego la aleatoriedad, ya que la decisión de con qué lado fusionar se determina mediante un lanzamiento de moneda.
función Meld( Nodo Q 1, Nodo Q 2) si Q 1 es nulo => devolver Q 2 si Q 2 es nulo => devolver Q 1 si Q1 > Q 2 => intercambiar Q 1 y Q 2 si coin_toss es 0 => Q 1. izquierda = Meld( Q 1. izquierda , Q 2) sino Q 1. derecha = Meld( Q 1. derecha , Q 2) devolver Q 1
Insertar
Una vez completada la operación de fusión, insertar datos en el montón fusionable es sencillo. Primero, se crea un nuevo nodo, u, que contiene el valor x. Este nuevo nodo se fusiona entonces con el nodo raíz del montón.
función Insertar(x) Nodo u = nuevo Nodo ux = x raíz = Meld(u, raíz) raíz.padre = nil incrementar el contador de nodos
Eliminar
De forma similar a la operación de inserción, Remove() utiliza la operación Meld para eliminar el nodo raíz del montón. Esto se logra simplemente fusionando los dos hijos del nodo raíz y convirtiendo el nodo resultante en la nueva raíz.
función Remove() raíz = Meld(raíz.izquierda, raíz.derecha) Si root no es nulo, root.parent se convierte en nulo. decremento del número de nodos
FindMin
Posiblemente la operación más sencilla para el montón combinable aleatorio, FindMin() simplemente devuelve el elemento actualmente almacenado en el nodo raíz del montón.
Operaciones adicionales
Algunas operaciones adicionales que se pueden implementar para el montón fusionable que también tienen una eficiencia en el peor de los casos de O (log n ) son:
- Remove(u) - Elimina el nodo u y su clave del montón.
- Absorber(Q) - Agrega todos los elementos del montón fusionable Q a este montón, vaciando Q en el proceso.
- DecreaseKey(u, y) - Disminuye la clave en el nodo u a y (precondición: y ≤ ux).
Análisis de eficiencia
Dado que todas las operaciones de tiempo no constante se definen en términos de la operación Meld, la eficiencia de estas operaciones se puede determinar mediante el análisis de la complejidad de fusionar dos montones aleatorios.
El resultado de este análisis es que el tiempo esperado de cualquier operación de cola de prioridad fusionable en un montón aleatorio de n nodos es O (log n ). [ 1 ] [ 2 ]
Historia
El montón fusionable parece haber sido propuesto por primera vez en 1998 por Gambin y Malinowski. [ 1 ]
Variantes
Si bien el montón combinable aleatorio es la forma más simple de implementación de un montón combinable, existen otras. Estas son:
Referencias
- 1 2 3 A. Gambin y A. Malinowski. 1998. Colas de prioridad combinables aleatorias. En Actas de la 25.ª Conferencia sobre Tendencias Actuales en Teoría y Práctica de la Informática: Teoría y Práctica de la Informática (SOFSEM '98), Branislav Rovan (Ed.). Springer-Verlag, Londres, Reino Unido, 344-349.
- ↑ P. Morin ,Estructuras de datos abiertas, pág. 191-
- Colas de prioridad