Heap Sift Up

Problem

Restore the min-heap property by sifting the element at index up toward the root.

heap is a list that is a valid min-heap everywhere except possibly at the given index. While the element is smaller than its parent, swap the two and continue from the parent position.

Return the updated heap as a new list.

Hint

Compare with the parent at (i - 1) // 2 and keep swapping while smaller.

Test cases

case 1

in: [[3,5,4],0]

expected: [3,5,4]

case 2

in: [[10,20,30,5],3]

expected: [5,10,30,20]

case 3

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

expected: [1,2,3]

case 4

in: [[2,4,6,8,1],4]

expected: [1,2,6,8,4]

Starter codePython

def sift_up(heap, index):
    # Your code here
    pass

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