¿Por qué se prefiere Binary Heap sobre BST para Priority Queue?

Una cola de prioridad típica requiere que las siguientes operaciones sean eficientes.

1. Obtener elemento de máxima prioridad (Obtener mínimo o máximo)
2. Insertar un elemento
3. Eliminar elemento de máxima prioridad
4. Tecla de disminución

Un montón binario admite las operaciones anteriores con las siguientes complejidades de tiempo:

1. O(1)
2. O (Iniciar sesión)
3. O (Iniciar sesión)
4. O (Iniciar sesión)

 

Un árbol de búsqueda binario autoequilibrado como el árbol AVL , el árbol rojo-negro, etc. también puede admitir operaciones anteriores con la misma complejidad de tiempo.

1. Encontrar el mínimo y el máximo no son naturalmente O(1), pero se puede implementar fácilmente en O(1) manteniendo un puntero adicional al mínimo o al máximo y actualizando el puntero con inserción y eliminación si es necesario. Con la eliminación podemos actualizar encontrando enorden predecesor o sucesor.
2. Insertar un elemento es naturalmente O (Iniciar sesión)
3. Eliminar máximo o mínimo también son O (Iniciar sesión) 
4. La tecla de disminución se puede hacer en O (Iniciar sesión) haciendo una eliminación seguida de una inserción. Vea esto para más detalles.

Entonces, ¿por qué se prefiere Binary Heap para Priority Queue?

• Dado que Binary Heap se implementa mediante arrays, siempre hay una mejor localidad de referencia y las operaciones son más amigables con la memoria caché.
• Aunque las operaciones tienen la misma complejidad de tiempo, las constantes en el árbol de búsqueda binaria son más altas.
• Podemos construir un montón binario en tiempo O(n). Los BST de autoequilibrio requieren tiempo O (nLogn) para construirse.
• Binary Heap no requiere espacio adicional para punteros.
• Binary Heap es más fácil de implementar.
• Hay variaciones de Binary Heap como Fibonacci Heap que pueden admitir la inserción y disminución de teclas en el tiempo Θ(1)

¿Binary Heap siempre es mejor? Aunque Binary Heap es para Priority Queue, los BST tienen sus propias ventajas y, de hecho, la lista de ventajas es mayor en comparación con el montón binario.

• La búsqueda de un elemento en BST de autoequilibrio es O (Inicio de sesión), que es O (n) en Binary Heap.
• Podemos imprimir todos los elementos de BST en orden en tiempo O(n), pero Binary Heap requiere tiempo O(nLogn).
• El suelo y el techo se pueden encontrar en el tiempo O (Logn).
• El elemento K’th más grande/más pequeño se encuentra en el tiempo O (Logn) al aumentar el árbol con un campo adicional.

Este artículo es una contribución de Vivek Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.