Montón fusionable

En informática , un montón fusionable (también llamado montón meldable ) es un tipo de dato 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(), crear un montón vacío.
• Insert(H,x), insertar un elemento xen el montón H.
• Min(H), devuelve el elemento mínimo, o Nilsi no existe tal elemento.
• Extract-Min(H), extrae y devuelve el elemento mínimo, o Nilsi no existe tal 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 a partir de un montón simple:

Merge(H1,H2):

1. x ← Extract-Min(H2)
2. while x ≠ Nil
   1. Insert(H1, x)
   2. x ← Extract-Min(H2)

Sin embargo, esto puede ser un desperdicio, ya que cada uno Extract-Min(H)y Insert(H,x)normalmente tienen que mantener la propiedad del montón .

Algunos ejemplos de estructuras de datos de montón fusionables son:

• Montículo binomial
• Montículo de Fibonacci
• árbol izquierdista
• Montón de emparejamiento
• Montón sesgado

Una lista más completa con comparaciones de rendimiento se puede encontrar en Heap (estructura de datos) §  Comparación de límites teóricos para variantes .

En la mayoría de las estructuras de montículos fusionables, la fusión es la operación fundamental sobre la que se basan las demás. La inserción se implementa fusionando un nuevo montículo de un solo elemento con el montículo existente. La eliminación se implementa fusionando los hijos del nodo eliminado.

• Montón direccionable