Un montón mínimo es un árbol binario completo en el que los Nodes secundarios tienen un valor más alto (menor prioridad) que los Nodes principales, es decir, cualquier ruta desde la raíz hasta los Nodes hoja tiene un orden ascendente de elementos. En el caso de un árbol binario, se considera que la raíz está en la altura 0, sus Nodes secundarios se consideran en la altura 1, y así sucesivamente. Cada Node puede tener dos hijos como máximo.
Propiedades importantes para Min Heap:
1. El Node principal siempre tendrá mayor prioridad y menor valor que el Node secundario (en el caso de Min Heaps).
2. Heap es un árbol binario completo. Entonces, para llenar el nivel N , los niveles (N-1) deben llenarse completamente primero y el llenado de los Nodes en el nivel N debe realizarse de izquierda a derecha.
Según estas propiedades, varias operaciones de Min Heap son las siguientes:
- Análisis de complejidad de la operación de inserción en el montón mínimo
Cuando se supone que un Node debe agregarse al montón, el elemento se agrega en el siguiente índice vacante de la array. Luego se verifica si el Node secundario insertado está de acuerdo con el Node principal o no. Si el hijo tiene un valor más bajo (prioridad más alta) que el padre, se realiza el intercambio de Nodes. Este proceso de intercambio continúa hasta que se cumplen las propiedades de Min Heap.
Si se va a insertar un Node a un nivel de altura H:
La complejidad de agregar un Node es: O(1)
Complejidad de intercambiar los Nodes (upheapify): O (H)
(el intercambio se realizará H veces en el peor de los casos)Complejidad total: O(1) + O(H) = O(H)
Para un árbol binario completo, su altura H = O (log N), donde N representa el número total. de Nodes
Por lo tanto, la complejidad general de la operación de inserción es O(log N) .
- Análisis de complejidad de la operación de eliminación en el montón mínimo
La eliminación de un Node no se puede hacer al azar. El elemento con la prioridad más alta (es decir, padre) se eliminará primero, seguido del siguiente Node en orden de prioridad. Esta es la razón por la cual el montón se llama cola de prioridad.
En primer lugar, intercambie las posiciones del Node principal y el Node hoja, y luego elimine el Node hoja recién formado (que originalmente era el principal) de la cola. A continuación, inicie el proceso de intercambio para que el nuevo Node principal se coloque en la posición correcta de acuerdo con las propiedades de Min Heap.Si se va a eliminar un Node de un montón con altura H:
La complejidad de intercambiar el Node padre y el Node hoja es: O(1)
Complejidad de intercambiar los Nodes (downheapify): O (H)
(el intercambio se realizará H veces en el peor de los casos)Complejidad total: O(1) + O(H) = O(H)
Para un árbol binario completo, su altura H = O (log N), donde N representa el número total. de Nodes
Por lo tanto, la complejidad general de la operación de eliminación es O(log N) .
- Complejidad de obtener el valor mínimo del montón mínimo
Para obtener el valor mínimo, simplemente devuelva el valor del Node raíz (que es el elemento más pequeño en Min Heap), así que simplemente devuelva el elemento en el índice 0 de la array.
Por lo tanto, la complejidad de obtener el valor mínimo es: O(1)
Publicación traducida automáticamente
Artículo escrito por kunal_pratap_singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA