Back to ChallengesImplement Heap SortMedium 30 min

Implement Heap Sort

Write a function that takes in an array of integers and returns a sorted version of that array using the Heap Sort algorithm.

Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

Examples

Input: arr = [8, 5, 2, 9, 5, 6, 3]

Output: [2, 3, 5, 5, 6, 8, 9]

The array is sorted in ascending order.

Constraints

• 1 <= arr.length <= 10^5
• -10^4 <= arr[i] <= 10^4

Complexity Analysis

Time

O(N log N)

building the heap takes O(N) and sifting down elements takes O(N log N).

Space

O(1)

sorts in place.

Test Cases

#1 Standard unsorted array

Input: arr = [8,5,2,9,5,6,3]

Expected: [2,3,5,5,6,8,9]

#2 Reverse sorted

Input: arr = [3,2,1]

Expected: [1,2,3]

JavaScript

Output

Click "Run Code" to see output here...