Iteration

Heap Sort

Given an array of integers arr, sort the array using a Heap. This is called "Heap Sort".

First Few Test Cases:

The idea is to turn your original Array into a Heap using "heapify", which takes O(n)O(n) time.

You can then repeatedly pop the smallest value from the Heap, and transfer it over to a new Array. The new Array will end up sorted when you're done.

Time Complexity O(nlogn)O(n \log n)

We first use heapify which takes O(n)O(n). We then pop the heap nn times, and popping takes O(logn)O(\log n) each time, since the heap has O(n)O(n) elements in it. This takes O(n)+O(nlogn)=O(nlogn)O(n)+O(n\log n) = O(n \log n) time.

Space Complexity O(1)O(1)

We're just transferring elements from the Heap to the sorted array. As the sorted array grows, the Heap shrinks. This means the space complexity is O(1)O(1) - there's no extra space needed.

Mark as Completed:
Submits:
heapSort
Test your code to get an output here!
heapSort(
)
Test your code to get an output here!