Heapsort

Problem

Sort a list of integers in ascending order and return the sorted list using heapsort.

Build a max-heap in place with sift-down starting from the last parent, then repeatedly swap the root to the end and shrink the heap, sifting the new root down. Handle empty input, negatives and duplicates.

Hint

First heapify from the last parent down to index 0, then extract the maximum n - 1 times.

Test cases

case 1

in: [[12,11,13,5,6,7]]

expected: [5,6,7,11,12,13]

case 2

in: [[]]

expected: []

case 3

in: [[1]]

expected: [1]

case 4

in: [[3,0,2,5,-1,4,1]]

expected: [-1,0,1,2,3,4,5]

Starter codePython

def heapsort(arr):
    # Your code here
    pass

4 test cases · run your code against them in the editor