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.
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 100 000) the number of elements.The next line contains
n space-separated integers () representing the values that need to be sorted.Output
The program should print the final sorted array in increasing order.
Examples
Input | Output |
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