Heap Sort
Problem statement
Given an integer array nums, return all its elements sorted from smallest to largest. Keep duplicate values. An empty array returns an empty array.
Practice implementing heap sort: build a max heap, repeatedly move its maximum into the last position of the unsorted prefix, and repair the smaller heap. The returned values are judged; no particular intermediate heap layout is required.
Function
heapSort(nums: int[]) → int[]Examples
Example 1
nums = [6,15,2,4,3,8,19]return = [2,3,4,6,8,15,19]Each extraction places the current largest value at the end of the remaining prefix.
Example 2
nums = [3,-1,3,0]return = [-1,0,3,3]Negative values and duplicate threes are retained.
Example 3
nums = []return = []No construction or extraction is needed.
Constraints
0 <= nums.length <= 100000.- Every element is a signed 32-bit integer.