Heaps: Python - Removing the Min: Heapify Down II

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.

If (I have not checked whether that is the case) the only difference is that instead of calling get_smaller_child_idx once, you call it once, modify the heap, and then call it again – then that tells us the function returns a different value the second time.

I see another difference, so that assumption doesn’t hold.
Maybe that difference is equivalent, I’m not going to try figuring that out, but you’d probably only want to have a single difference in your code while you compare, otherwise it gets really difficult to tell which one is responsible.

Without thinking too hard about it (I can’t run your code, I haven’t done this before) I would expect that function to return a different value after the swap, because the small value was replaced with a bigger one, so it might no longer be the smaller child.

If I was debugging this I’d have it write out the heap after each change, and write out all the reasoning that it does. Or use a debugger and step through it. Or possibly just think real hard about it since the action isn’t incredibly complicated, and when understood, should give me a decent chance at finding the issue by reading the code.

Hey, thanks. I didnt realize at that time, that calling again .get smaller child method updates the idx variable with different number. I didnt saved unique index no. into variable smaller_child to carrry it and than use it to update idx.