Given an array of integers arr
, sort the array using a Heap. This is called "Heap Sort".
The idea is to turn your original Array into a Heap using "heapify", which takes 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)
We first use heapify which takes O(n). We then pop the heap n times, and popping takes O(logn) each time, since the heap has O(n) elements in it. This takes O(n)+O(nlogn)=O(nlogn) time.
Space Complexity 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) - there's no extra space needed.