¿Cuándo querría usar un montón?

92

Además de la respuesta obvia de una cola prioritaria, ¿cuándo sería útil un montón en mis aventuras de programación?

Mitrax
fuente
8
Aquí hay muchas buenas respuestas, así que voy a intervenir con "cuando una pila no es lo suficientemente grande".
Don Werve

Respuestas:

121

Úselo siempre que necesite acceso rápido al elemento más grande (o más pequeño), porque 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 manera de lidiar con eventos o datos entrantes y siempre tener acceso a los primeros / mayores.

Útil para colas de prioridad, programadores (donde se desea el elemento más temprano), 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, con el nodo raíz primero (luego los hijos de ese nodo después, 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 en el lugar.

Joe Koberg
fuente
3
Tenga en cuenta también que puede ser una clasificación NlogN garantizada conveniente que no requiere asignaciones de matriz adicionales
desborda el
38
También es genial saber montones de preguntas para entrevistas;)
vivekian2
21
@ vivekian2 La única razón por la que estoy aquí es porque estoy a punto de tener una entrevista.
byxor
¿Por qué no usar una clase de pila con una pila auxiliar para rastrear el elemento más grande (o más pequeño)? la recuperación es O (1)
Ridhwaan Shakeel
@RidhwaanShakeel Si usa la pila, su artículo siempre se colocará en la cabeza, ¿qué pasa si la posición del artículo debe determinarse en función de alguna propiedad del artículo, como el evento más grande (según la cantidad de personas que participaron en el evento)?
SandeepGodara
49

Los montones son estructuras destinadas a permitir un acceso rápido al mínimo o al máximo .

Pero, ¿por qué querrías eso? Simplemente puede verificar cada entrada en agregar para ver si es la más pequeña o la más grande. De esta forma siempre tienes el más pequeño o el más grande en tiempo constante O(1).

La respuesta es porque los montones le permiten extraer el más pequeño o el más grande y saber rápidamente el SIGUIENTE más pequeño o más grande . Por eso se llama Cola de prioridad.

Ejemplo del mundo real (aunque no es un mundo muy justo):

Suponga que tiene un hospital en el que se atiende a los pacientes en función de sus edades. Los mayores siempre son atendidos primero, sin importar cuándo se hayan puesto en la cola.

No puedes simplemente hacer un seguimiento del más antiguo porque si lo sacas, no sabes cuál es el siguiente. Para resolver este problema hospitalario, implementa un montón máximo . Este montón está, por definición, parcialmente ordenado. Esto significa que no puede clasificar a los pacientes por su edad, pero sabe que los mayores siempre están en la parte superior, por lo que puede sacar a un paciente en un tiempo constante O(1)y reequilibrar el montón en el tiempo de registro O(log N).

Ejemplo más sofisticado:

Suponga que tiene una secuencia de números enteros y desea realizar un seguimiento del median. La mediana es el número que se encuentra en el medio de una matriz ordenada.

Ejemplo:

[1, 2, 5, 7, 23, 27, 31]

En el caso anterior, 7es 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 impar de elementos, la mediana es el promedio aritmético de los 2 elementos del medio, p (5 + 7)/2. Ej .

Ahora bien, ¿cómo realiza 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 bien, si estos montones siempre están equilibrados, los 2 montones contendrán el mismo número de elementos o uno tendrá 1 elemento más que el otro, el máximo.

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.

André Pena
fuente
6
¡El ejemplo más sofisticado es asombroso! Definitivamente voy a probar esto en algún momento. Sin embargo, creo que hay un pequeño error en tu ejemplo. Dado que necesitamos obtener la mediana promediando los dos elementos en el medio. Asumiría que necesitamos usar un montón mínimo para almacenar los números más grandes que la mediana actual y un montón máximo para almacenar los números más pequeños que la mediana actual. ¿De esta manera podemos extraer los dos elementos del medio en tiempo constante y calcular la mediana? ¿Estoy en lo correcto?
Calvin Ku
12

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 un orden completo y el costo de buscar a través del caos aleatorio. Esa característica se utiliza en muchos algoritmos, como la selección, el orden o la clasificación.

Otra característica útil de un montón es que se puede crear in situ a partir de una matriz.

AticusFinch
fuente
3

También es bueno para algoritmos de selección (encontrar el mínimo o el máximo)

Dan
fuente
3

en cualquier momento al ordenar una lista temporal, debería considerar montones.

Javier
fuente
0

Puede usar minHeap o maxHeap cuando desee acceder a los elementos más pequeños y más grandes respectivamente.

QuadBiker
fuente