This question of my homework has passed a list where index 1 is the new node and is also the root. Then I have to check if it's children is smaller then itself and swap it with the smaller child. I've written some code but it's not working.
def perc_down(data):
count = 0
index = 1
l, r = 2 * index, 2 * index + 1
while index < len(data):
if data[index] > data[l] and data[index] > data[r]:
min_i = data.index(min(data[l], data[r]))
data[index], data[min_i] = data[min_i], data[index]
count += 1
index = min_i
return count
values = [0, 100, 7, 8, 9, 22, 45, 12, 16, 27, 36]
swaps = perc_down(values)
print('Binary heap =',values)# should be [0, 7, 9, 8, 16, 22, 45, 12, 100, 27, 36]
print('Swaps =', swaps)# should be 3
Give l and r values inside the while loop
while index <= len(data) // 2:
l, r = 2 * index, 2 * index + 1
if r >= len(data):
r = index
if data[index] > data[l] or data[index] > data[r]:
min_i = data.index(min(data[l], data[r]))
data[index], data[min_i] = data[min_i], data[index]
count += 1
index = min_i
print(data) #Added this for easy debugging.
return count
And run the loop till half values only because it's binary min heap.
Output:
[0, 7, 100, 8, 9, 22, 45, 12, 16, 27, 36]
[0, 7, 9, 8, 100, 22, 45, 12, 16, 27, 36]
[0, 7, 9, 8, 16, 22, 45, 12, 100, 27, 36]
Binary heap = [0, 7, 9, 8, 16, 22, 45, 12, 100, 27, 36]
Swaps = 3
Revised the algorithm for those indices whose children do not exist.
For : values = [0, 100, 7, 11, 9, 8, 45, 12, 16, 27, 36] for 100 after 2 swaps comes at index 5 which does not have a right child so when it exceeds the length of list we just set it back to original index.
Heapified list : Binary heap = [0, 7, 8, 11, 9, 36, 45, 12, 16, 27, 100].