Un montón es una estructura de datos. Es un tipo de árbol con la interesante propiedad de que cualquier nodo tiene un valor menor que cualquiera de sus hijos.
Esto sólo le da un orden parcial, por lo que si quieres encontrar un valor específico en el montón, no es fácil. Esta es una gran desventaja en comparación con un árbol binario, que le permite hacer búsquedas eficientes.
Pero la ventaja de aflojar esa restricción es la velocidad. Puede hacer inserciones y eliminaciones en tiempo log n, y puedes ver el valor mínimo en tiempo constante.
Un uso de esto es una ordenación del montón. Funciona así
- Poner todos los valores en un montón
- Sacarlos de un montón
Es una ordenación nlgn eficiente en el lugar. Poner los valores en un montón les da un orden flojo, pero el valor más bajo está siempre en la raíz, por lo que a medida que se eliminan se devuelven los valores en orden.
También es una buena opción para implementar una cola de prioridad. Añades valores en base a su prioridad, y los devolverás en orden de prioridad. Esto es mucho más eficiente que tratar de mantener una lista debidamente ordenada en cada paso.