Diferencia entre Min Heap y Max Heap

Un montón es una estructura de datos especial basada en un árbol en la que el árbol es un árbol binario completo . Dado que un montón es un árbol binario completo, un montón con N Nodes tiene una altura de registro N. Es útil eliminar el elemento de mayor o menor prioridad. Por lo general, se representa como una array . Hay dos tipos de Heaps en la estructura de datos .

Montón mínimo

En un Min-Heap, la clave presente en el Node raíz debe ser menor o igual entre las claves presentes en todos sus elementos secundarios. La misma propiedad debe ser verdadera recursivamente para todos los subárboles en 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 Max-Heap, la clave presente en el Node raíz debe ser mayor o igual entre las claves presentes en todos sus elementos secundarios. La misma propiedad debe ser verdadera recursivamente 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 Min Heap y Max Heap

	Montón mínimo	Montón máximo
1.	En un Min-Heap, la clave presente en el Node raíz debe ser menor o igual que entre las claves presentes en todos sus elementos secundarios.	En un Max-Heap, la clave presente en el Node 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 usa la prioridad ascendente.	Un Max-Heap usa 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 en salir del montón.	En un Max-Heap, el elemento más grande es el primero en salir del montón.

Aplicaciones de montones :

1. Heap Sort : Heap Sort es uno de los mejores algoritmos de clasificación que utiliza Binary Heap para ordenar una array en tiempo O (N * log N) .
2. Cola de prioridad : se puede implementar una cola de prioridad mediante el uso de un montón porque admite las operaciones insert() , delete() , extractMax() , decrementKey() en tiempo O(log N) .
3. Algoritmos gráficos : los montones se utilizan especialmente en algoritmos gráficos como el camino más corto de Dijkstra y el árbol de expansión mínimo 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)
• Quitar Elemento Máximo o Mínimo: O(log N)