Algoritmo de Heap sort
Heap sort (ordenamiento por montículos) es un algoritmo de ordenación basado en comparaciones que emplea una estructura de datos tipo heap (montículo) para ordenar un arreglo. La idea principal es construir un heap a partir de los elementos del arreglo y, luego, repetir el proceso de extraer el elemento más grande o más pequeño (en función de si se trabaja con un montículo máximo —max-heap— o uno mínimo —min-heap—) y colocarlo al final del arreglo, hasta que el heap se vacíe por completo.
Se te pide que implementes el algoritmo heap sort utilizando un min-heap.
Entrada
La primera línea de la entrada contiene un solo entero
n (1 ≤ n ≤ 100 000), que indica el número de elementos.La siguiente línea contiene
n enteros separados por espacios (), que representan los valores que deben ordenarse.Salida
El programa debe imprimir el arreglo final ordenado en orden ascendente.
Ejemplos
Entrada | Salida |
7
4 3 8 -2 9 0 2 | -2 0 2 3 4 8 9 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB