data structures - ¿Cuándo quisiera usar un montón?
min heap (6)
Además de la respuesta obvia de una Cola de Prioridad, ¿cuándo sería útil un montón en mis aventuras de programación?
Úselo siempre que necesite un acceso rápido al elemento más grande (o más pequeño), ya que ese elemento siempre será el primer elemento de la matriz o en la raíz del árbol.
Sin embargo, el resto de la matriz se mantiene parcialmente sin clasificar. Por lo tanto, el acceso instantáneo solo es posible al elemento más grande (más pequeño). Las inserciones son rápidas, por lo que es una buena forma de lidiar con eventos o datos entrantes y siempre tener acceso a los primeros o más grandes.
Útil para colas de prioridad, planificadores (donde se desea el primer elemento), etc.
Un montón es un árbol donde el valor de un nodo padre es mayor que el de cualquiera de sus nodos descendientes.
Si piensa en un montón como un árbol binario almacenado en orden lineal por profundidad, primero con el nodo raíz (luego los secundarios de ese nodo, luego los hijos de esos nodos después); entonces los hijos de un nodo en el índice N están en 2N + 1 y 2N + 2. Esta propiedad permite un acceso rápido por índice. Y dado que los montones se manipulan intercambiando nodos, esto permite la clasificación in situ.
La característica de un montón es que es una estructura que mantiene los datos semiordenados; por lo tanto, es una buena compensación entre el costo de mantener una orden completa y el costo de la búsqueda a través del caos aleatorio. Esa característica se usa en muchos algoritmos, como selección, ordenamiento o clasificación.
Otra característica útil de un montón es que se puede crear in situ desde una matriz.
Puede utilizar un minHeap o maxHeap cuando desee acceder a los elementos más pequeños y más grandes, respectivamente.
También es bueno para algoritmos de selección (encontrar el mínimo o máximo)
en cualquier momento cuando clasifique una lista temporal, debe considerar montones.
Los montículos son estructuras diseñadas para permitir un acceso rápido al mínimo o máximo .
Pero, ¿por qué querrías eso? Podrías verificar cada entrada en agregar para ver si es la más pequeña o la más grande. De esta forma siempre tendrá el más pequeño o el más grande en el tiempo constante O(1) .
La respuesta es porque los montones le permiten sacar el más pequeño o el más grande y saber rápidamente el SIGUIENTE, el más pequeño o el más grande . Es por eso que se llama Priority Queue.
Ejemplo del mundo real (aunque no es un mundo muy justo):
Supongamos que tiene un hospital en el que se atiende a los pacientes en función de su edad. Siempre se atiende primero a los mayores, sin importar cuándo ingresaron en la cola.
No se puede simplemente hacer un seguimiento de la más antigua porque si se saca, no se sabe cuál es la más vieja. Para resolver este problema del hospital, implementa un montón máximo . Este montón está, por definición, parcialmente ordenado. Esto significa que no puede ordenar los pacientes por su edad, pero sabe que los más viejos siempre están en la parte superior, por lo que puede sacar a un paciente en tiempo constante O(1) y volver a equilibrar el montón en el tiempo de registro O(log N) .
Ejemplo más sofisticado:
Supongamos que tiene una secuencia de enteros y desea realizar un seguimiento de la median . La mediana es el número que está en el medio de una matriz ordenada.
Ejemplo:
[1, 2, 5, 7, 23, 27, 31]
En el caso anterior, 7 es la mediana porque la matriz que contiene los números más pequeños [1, 2, 5] es del mismo tamaño que la que contiene los números más grandes [23, 27, 31] . Normalmente, si la matriz tiene un número par de elementos, la mediana es el promedio aritmético de los 2 elementos en el medio, por ejemplo, (5 + 7)/2 .
Ahora, ¿cómo haces un seguimiento de la mediana? Al tener 2 montones , un montón mínimo que contiene los números más pequeños que la mediana actual y un montón máximo que contiene los números más grandes que la mediana actual. Ahora, si estos montones están siempre equilibrados, los 2 montones contendrán el mismo número de elementos o uno tendrá 1 elemento más que el otro, la mayoría.
Cuando agrega un nuevo elemento a la secuencia, si el número es menor que la mediana actual, lo agrega al montón mínimo, de lo contrario, lo agrega al montón máximo. Ahora, si los montones están desequilibrados (un montón tiene más de 1 elemento más que el otro), extrae un elemento del montón más grande y lo agrega al más pequeño. Ahora están equilibrados.