Bueno, hay una respuesta fácil que parecería algo así porque las complejidades promedio para el montón de emparejamiento [1] son mejores que para el montón binario [2], pero eso no es lo que estás buscando, ¿verdad?
Comencemos con el montón binario. El montón binario en realidad es un árbol binario que se almacena en un formato plano, por así decirlo.
- Cómo estimar pi usando un hexágono unitario en Matlab
- ¿Cuál es la diferencia entre analizar un archivo CSV y JSON? ¿Qué algoritmos comunes usarías en ambos?
- En los términos más simples, ¿qué es un algoritmo? ¿Cual es su propósito?
- ¿Para qué sirven las estructuras de datos?
- ¿Puede alguien sin antecedentes de cálculo aprender estructuras de datos y algoritmos leyendo CLRS?
Las complejidades [3] [4], no sorprendentemente, contienen logaritmos:
- find-min Θ (1): devuelve el primer elemento;
- delete-min Θ (log n ): necesita eliminar la raíz y restaurar las propiedades del montón;
- inserte O (log n ): agregue el elemento y restaure las propiedades del montón comparando el elemento agregado con el elemento primario e intercambiando en caso de que sea más pequeño. El emparejamiento del montón funcionará mejor;
- tecla de disminución Θ (log n ) – disminuye el valor, restaura la propiedad del montón, de manera similar a insertar;
- fusionar Θ ( n ): solo reconstruye el montón a partir de una matriz fusionada, no hay forma de evitarlo aquí. El emparejamiento del montón funcionará mejor.
El emparejamiento del montón es más complicado. En lugar de tener un árbol binario simple, tiene un árbol de múltiples vías que tiene propiedades de montón.
Imagen cortesía de Sataj Sahni. Veamos las complejidades:
- find-min Θ (1) – igual, devuelve el primer elemento;
- delete-min Θ (log n ): igual, es necesario eliminar la raíz y restaurar las propiedades del montón;
- inserte O (1): mejor, cree un nuevo montón para el elemento insertado y fusione con el montón original. Debido a que la fusión es barata, este es el camino a seguir;
- tecla de disminución Θ (log n ): igual, disminuir el valor, restaurar la propiedad del montón, de forma similar a insertar;
- fusionar Θ (1): mucho mejor, comparar los dos elementos raíz, el más pequeño sigue siendo la raíz del resultado, el elemento más grande y su subárbol se adjunta como hijo de esta raíz.
En general, es evidente que el almacenamiento dinámico de emparejamiento es mejor en las operaciones comparadas. El almacenamiento dinámico de emparejamiento es realmente muy similar al almacenamiento dinámico binario, pero gana debido a la facilidad de operación de fusión, que se reutiliza para las inserciones.
Notas al pie
[1] Heap de emparejamiento – Wikipedia
[2] Montón binario – Wikipedia
[3] Montón binario – Wikipedia
[4] Montones
