A Montón es un especial árbol binario completo . Dado que un montón es un árbol binario completo, un montón con norte los nodos tienen registro norte altura. Es útil eliminar el elemento de mayor o menor prioridad. Generalmente se representa como un formación . Hay dos tipos de montones en elmontón mínimo
en un montón mínimo la clave presente en el nodo raíz debe ser menor o igual entre las claves presentes en todos sus hijos. La misma propiedad debe ser verdadera de forma recursiva para todos los subárboles de ese árbol binario. En un Min-Heap, el elemento clave mínimo presente en la raíz. A continuación se muestra el árbol binario que satisface todas las propiedades de Min Heap.
Montón máximo
en un montón máximo la clave presente en el nodo raíz debe ser mayor o igual entre las claves presentes en todos sus hijos. La misma propiedad debe ser recursivamente verdadero para todos los subárboles en ese árbol binario. En un Max-Heap, el elemento clave máximo presente en la raíz. A continuación se muestra el árbol binario que satisface todas las propiedades de Max Heap.
Diferencia entre montón mínimo y montón máximo
| Montón mínimo | Montón máximo | |
|---|---|---|
| 1. | En un Min-Heap, la clave presente en el nodo raíz debe ser menor o igual que entre las claves presentes en todos sus hijos. | En un Max-Heap, la clave presente en el nodo raíz debe ser mayor o igual que entre las claves presentes en todos sus hijos. |
| 2. | En un Min-Heap, el elemento clave mínimo presente en la raíz. | En un Max-Heap, el elemento clave máximo presente en la raíz. |
| 3. | Un Min-Heap utiliza la prioridad ascendente. | Un Max-Heap utiliza la prioridad descendente. |
| 4. | En la construcción de un Min-Heap, el elemento más pequeño tiene prioridad. | En la construcción de un Max-Heap, el elemento más grande tiene prioridad. |
| 5. | En un Min-Heap, el elemento más pequeño es el primero que se extrae del montón. | En un Max-Heap, el elemento más grande es el primero que se extrae del montón. |
Aplicaciones de montones :
- Ordenar montón : Heap Sort es uno de los mejores algoritmos de clasificación que utiliza montón binario a ordenar una matriz en O(N*logN) tiempo.
- Cola de prioridad : Se puede implementar una cola de prioridad mediante el uso de un montón porque admite insertar() , borrar() , extraerMax() , disminuirClave() operaciones en O(logN) tiempo.
- El camino más corto de Dijkstra y Árbol de expansión mínima de Prim .
Análisis de rendimiento de Min-Heap y Max-Heap :
- Obtener elemento máximo o mínimo: O(1)
- Insertar elemento en Max-Heap o Min-Heap: O (log N)
- Eliminar elemento máximo o mínimo: O (log N)