Algoritmo Heap Sort
O heap sort é um algoritmo de ordenação baseado em comparações que utiliza a estrutura de dados heap para ordenar um array. A ideia fundamental do algoritmo é transformar os elementos do array num heap e, em seguida, remover repetidamente o maior/menor elemento do heap (dependendo de ser um max-heap ou um min-heap) e colocá-lo no final do array, até que o heap fique vazio.
Pede-se que implemente o algoritmo de heap sort usando um min-heap.
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 100 000), que representa o número de elementos.A linha seguinte contém
n inteiros separados por espaço, (), correspondentes aos valores a serem ordenados.Saída
O programa deve imprimir o array ordenado em ordem crescente.
Exemplos
Entrada | Saída |
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