En informática , un montón fusionable (también llamado montón combinable ) es un tipo de datos abstracto , que es un montón que admite una operación de fusión.
Un montón fusionable admite las operaciones de montón habituales: [1]
Make-Heap(), crea un montón vacío.Insert(H,x), inserta un elemento xen el montón H.Min(H), devuelve el elemento mínimo, o Nilsi no existe dicho elemento.Extract-Min(H), extrae y devuelve el elemento mínimo, o Nilsi no existe dicho elemento.Y una más que la distingue: [1]
Merge(H1,H2), combina los elementos de H1y H2en un solo montón.Es sencillo implementar un montón fusionable dado un montón simple:
Merge(H1,H2):
x ← Extract-Min(H2)while x ≠ NilInsert(H1, x)x ← Extract-Min(H2)Sin embargo, esto puede ser un desperdicio, ya que normalmente cada uno Extract-Min(H)tiene Insert(H,x)que mantener la propiedad del montón .
Algunos ejemplos de estructuras de datos de montón fusionables incluyen:
Se puede encontrar una lista más completa con comparaciones de rendimiento en Heap (estructura de datos) § Comparación de límites teóricos para variantes .
En la mayoría de las estructuras de montón fusionables, la fusión es la operación fundamental en la que se basan las demás. La inserción se implementa fusionando un nuevo montón de un solo elemento con el montón existente. La eliminación se implementa fusionando los elementos secundarios del nodo eliminado.