127: Heap sort

Given an array of integers, return a sorted array. Use the heap sort algorithm to sort the array

 

Example 1

Input:   [4, 2, 1, 5]

Output:  [1, 2, 4, 5]

Example 2

Input:   [-4, 2, 1, 5]

Output:  [-4, 1, 2, 5]