Heap sort algorithm
Heap sort is a comparison-based sorting algorithm that uses a heap data structure to sort an array. The basic idea behind the algorithm is to create a heap out of the array elements, then repeatedly remove the largest/smallest element from the heap (depending on whether the heap is a max-heap or a min-heap) and move it to the end of the array, until the heap is empty.
You are asked to implement the heap sort algorithm using a min-heap.
The first line of the input contains a single integer
n(1 ≤ n ≤ 100 000) the number of elements.
The next line contains
nspace-separated integers () representing the values that need to be sorted.
The program should print the final sorted array in increasing order.
7 4 3 8 -2 9 0 2
-2 0 2 3 4 8 9
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB