Hi all,
I have question about formating or syntax - not sure which does my problem fits to - of one particular piece of code that gives different results, while looking the same to me:
In excercise of this FAQ i was writting heapifying down method for minimum heap structures. Heapify down swap child node value with parent node value if parent node is bigger, when it comes to heapifying down. Heapyfing up is different story…
LInk to exercise: Min heap exercise
the code I used is here:
def heapify_down(self):
idx = 1
while self.left_child_idx(idx) <= self.count:
print("Heapifying down!")
smaller_child = self.heap_list[self.get_smaller_child_idx(idx)]
parent = self.heap_list[idx]
if parent > smaller_child:
self.heap_list[idx] = smaller_child
self.heap_list[self.get_smaller_child_idx(idx)] = parent
idx = self.get_smaller_child_idx(idx)
print("HEAP RESTORED! {0}".format(self.heap_list))
code from solution is below:
def heapify_down(self):
idx = 1
while self.child_present(idx):
print("Heapifying down!")
smaller_child_idx = self.get_smaller_child_idx(idx)
child = self.heap_list[smaller_child_idx]
parent = self.heap_list[idx]
if parent > child:
self.heap_list[idx] = child
self.heap_list[smaller_child_idx] = parent
idx = smaller_child_idx
print("HEAP RESTORED! {0}".format(self.heap_list))
left_child_idx method returns the left child index of parent in binary tree from the array
get_smaller_child method returns index of the smaller children from two siblings belonging to one parent from the array
self.child_present(idx) is method that returns result of self.left_child_idx(idx) <= self.count (like in my code)
These 3 methods works ok every time, so theyre not the concern.
What I understand is that if in first code I defined variables smaller_child and parent. By comparing my instructions to code below, I can see instructors created an extra variable called child
Child variable should have equal value as mine smaller_child variable by logic. The code is same, but instructors split the code to two variables, while I compressed it to only one. If those variables are equal, they should return equal results, but that is not so.
Maybe Im missing something so I need a fresh second set of eyes. Just to be clear, rest of the code in the excercise is exactly the same like provided by solution. The only differentiation I tried to make is in this heapifying down method, so by default the problem must be only in this part of the code.
The results is that it swaps only first child and first parent and does not continue swaping even though there are more children meeting the condition for heapify swap. I checked if the condition is incorrect, but no, the while condition is correct. Dunno what else could it be.
Thanks for help.
) below.
) to up-vote the contribution!