Given an array of integers arr, sort the array using a Heap. This is called "Heap Sort".
heapSort([1])
# [1]heapSort([1, 2])
# [1, 2]heapSort([2, 1])
# [1, 2]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.
def heapSort(arr):
# turn array into a min heap
heapq.heapify(arr)
# transfer smallest value from Heap to Sorted Array
sortedArr = []
for _ in range(len(arr)):
sortedArr.append(heapq.heappop(arr))
return sortedArrTime 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.