En informática, un montón fusionable aleatorio (también Meldable Heap o Randomized Meldable Priority Queue ) es una estructura de datos basada en cola de prioridad en la que la estructura subyacente es también un árbol binario ordenado por montón . Sin embargo, no existen restricciones sobre la forma del árbol binario subyacente.
Este enfoque tiene una serie de ventajas sobre estructuras de datos similares. Ofrece una mayor simplicidad: todas las operaciones para el montón fusible 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 y no se necesita información satelital dentro de los nodos. Por último, esta estructura tiene una buena eficiencia de tiempo 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ón fusionable aleatorio admite una serie de operaciones comunes. Se trata de una operación de inserción, eliminación y búsqueda, findMin. Las operaciones de inserción y eliminación se implementan en términos de una operación adicional específica del montón fusible, Meld (Q1, Q2).
Meld
El objetivo básico de la operación de fusión (también llamada fusión) es tomar dos montones (tomando cada uno de los nodos raíz de montones), Q1 y Q2, y fusionarlos, devolviendo un único nodo de montón como resultado. Este nodo de montón es el nodo raíz de un montón que contiene todos los elementos de los dos subárboles enraizados en Q1 y Q2.
Una característica interesante de esta operación de combinación es que se puede definir de forma recursiva. Si alguno de los montones es nulo, entonces la fusión se lleva a cabo 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, verifique si Q1> Q2. Si es así, intercambie los dos. Por lo tanto, se garantiza que Q1
función Meld ( Nodo Q 1, Nodo Q 2) si Q 1 es nulo => devuelve Q 2 si Q 2 es nulo => devuelve Q 1 si Q1 > Q 2 => intercambia Q 1 y Q 2 si coin_toss es 0 => Q 1. izquierda = Fusionar ( Q 1. izquierda , Q 2) de lo contrario Q 1. derecha = Fusionar ( Q 1. derecha , Q 2) volver Q 1
Insertar
Con la operación de fusión completa, la inserción en el montón fusible es fácil. Primero, se crea un nuevo nodo, u, que contiene el valor x. Este nuevo nodo simplemente se fusiona con el nodo raíz de montones.
función Insertar (x) Nodo u = nuevo Nodo ux = x raíz = Fusionar (u, raíz) root.parent = nil incrementar el recuento de nodos
Eliminar
De manera similar a la operación de inserción, Remove () usa la operación Meld para eliminar el nodo raíz del montón. Esto se hace simplemente fusionando los dos hijos del nodo raíz y haciendo que el nodo devuelto sea la nueva raíz.
función Eliminar () root = Meld (root.left, root.right) si root no es nil => root.parent = nil disminuir el recuento de nodos
FindMin
Posiblemente la operación más fácil para el montón fusible aleatorio, FindMin () simplemente devuelve el elemento almacenado actualmente en el nodo raíz del montón.
Operaciones adicionales
Algunas operaciones adicionales que se pueden implementar para el montón fusible que también tienen una eficiencia de O (log n ) en el peor de los casos son:
- Eliminar (u): elimina el nodo u y su clave del montón.
- Absorber (Q): agregue todos los elementos del montón Q fusionable a este montón, vaciando Q en el proceso.
- DecreaseKey (u, y): disminuye la clave en el nodo uay (condición previa: y <= ux).
Análisis de eficiencia
Como 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]
Operación | Eficiencia de tiempo en el peor de los casos |
---|---|
Meld (Q1, Q2) | O (log n ) |
Insertar (x) | O (log n ) |
Eliminar() | O (log n ) |
FindMin () | O ( 1 ) |
Quitar (x) | O (log n ) |
Absorber (Q) | O (log n ) |
Historia
El montón fusible parece haber sido propuesto por primera vez en 1998 por Gambin y Malinowski. [1]
Variantes
Si bien el montón fusionable aleatorio es la forma más simple de implementación de un montón fusionable, existen otros. Estos son:
Referencias
- ^ a b c A. Gambin y A. Malinowski. 1998. Colas de prioridad fusionables 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, Reino Unido, 344-349.
- ^ P. Morin , [1] Estructuras de datos abiertas, p. 191-