Iteration

Heap Sort

Sorting

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

First Few Test Cases:
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)O(n) time.

Heap Sort - image

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 sortedArr

Time Complexity O(nlog⁡n)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(log⁡n)O(\log n) each time, since the heap has O(n)O(n) elements in it. This takes O(n)+O(nlog⁡n)=O(nlog⁡n)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!