Heapify Build Min-Heap

Problem

Build a min-heap from an unsorted list in O(n) time using the bottom-up heapify algorithm.

Starting from the last internal node (n // 2 - 1) down to index 0, sift each element down: repeatedly swap it with its smaller child until both children are greater than or equal to it.

Return the resulting heap as a new list. The exact layout is deterministic for this algorithm.

Hint

Sift down every internal node from the last one back to the root; leaves are already heaps.

Test cases

case 1

in: [[]]

expected: []

case 2

in: [[5]]

expected: [5]

case 3

in: [[3,2,1]]

expected: [1,2,3]

case 4

in: [[9,4,7,1,-2,6,5]]

expected: [-2,1,5,9,4,6,7]

case 5

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

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

Starter codePython

def heapify(nums):
    # Your code here
    pass

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