Otros han indicado que rara vez se utiliza la ordenación del montón, pero eso no es necesariamente cierto. Puede que no sea tan útil para ordenar un conjunto fijo de elementos, pero es esencial para muchos algoritmos en los que desea mantener los elementos para extraer el mínimo o el máximo. Primero, por qué no es útil en muchas situaciones. Considere el siguiente conjunto de números:
[2,4,5,1,6,7,9,3,14,10,15,17,8]
Si realiza una ordenación rápida in situ en este conjunto, obviamente obtendrá [1,2,3,4,5,6,7,8,9,10,14,15,17]. Uno de los principales casos de uso de ordenar un conjunto de elementos es hacer una búsqueda rápida utilizando la búsqueda binaria. Una vez que se realiza la ordenación rápida en el lugar, podemos buscar elementos arbitrarios en el tiempo O (log n), lo cual es sorprendente. Una cosa importante es que puedes hacer esta búsqueda varias veces.
- ¿Hay un libro sobre estructuras de datos PHP y algoritmos?
- Cómo implementar un verificador de plagio en Java
- ¿Qué es mejor para la programación competitiva, la introducción del MIT a los algoritmos o los tutoriales de TopCoder?
- Cómo encontrar la complejidad de tiempo de caso promedio de un algoritmo
- Cómo dominar las estructuras de datos y los algoritmos (DSA) para mejorar mis habilidades de resolución de problemas que eventualmente serán útiles en las entrevistas
Ahora traigamos el montón aquí. Si los elementos vienen en el orden en que están escritos y crea un montón mínimo, se construiría la siguiente matriz interna:
[1, 2, 5, 3, 6, 7, 9, 4, 14, 10, 15, 17, 8]
Ahora, si el criterio principal es buscar eficientemente elementos arbitrarios varias veces, no funcionará aquí porque esta estructura de datos se concentra en la tarea asignada que debe seguir el mínimo / máximo. No solo puede darle un mínimo de tiempo logarítmico, sino que también puede cambiar la prioridad de los artículos en función de la nueva llegada para subir o bajar los artículos. La ordenación rápida en la parte superior lo ayudará a buscar CUALQUIER elemento arbitrario MÚLTIPLES VECES en el tiempo O (log n), pero dificultará el seguimiento mínimo cuando lleguen los nuevos elementos.
Ahora, una vez que haya construido este montón, puede recuperar el mínimo, imprimirlo y la matriz final se vería similar a lo que teníamos después de la clasificación rápida. Eso es esencialmente un montón.
De la descripción anterior, surgen dos cosas:
- Es posible que el ordenamiento en sí mismo no se use con frecuencia para ordenar un conjunto de elementos, pero su estructura de datos subyacente, el montón, se usa con frecuencia para mantener un orden particular cuando se desea extraer el mínimo o el máximo. Esto está en el centro de la programación del trabajo. Ninguna otra estructura de datos puede hacer esto tan eficiente como el montón que se usa como cola prioritaria.
- Dado que no hay un orden particular en el que los elementos se almacenan en el montón, aparte de encontrar el mínimo o el máximo, no es útil para otro tipo de búsquedas arbitrarias.
Vea mi respuesta a esta pregunta sobre cómo se implementan los montones min / max: ¿Cómo se puede convertir un montón máximo en un montón mínimo de manera eficiente?
