Heap Sort
Practice this coding question on Coding Gurukul.
Problem statement
Given an array of n integers, sort it in nondecreasing order using Heap Sort. Build a max heap. Repeatedly move its largest value to the end and restore the heap in the remaining part. Print the sorted array. Keep every occurrence of a repeated value. Negative values are allowed. Do not use a library sorting function. Target O(n log n) time. Worked example [5, -2, 5, 0, 1] becomes [-2, 0, 1, 5, 5]. Both copies of 5 remain.
Input format
First line: n. Second line: n integers.
Output format
Print the n sorted integers separated by spaces.
Constraints
1 <= n <= 100000; -10^9 <= a[i] <= 10^9.
Sample input
5 5 -2 5 0 1
Sample output
-2 0 1 5 5
Sign in to run or submit a solution in C++, Java or Python.