FAQ: Heaps: Python - Removing the Min: Heapify Down II


#1

This community-built FAQ covers the “Removing the Min: Heapify Down II” exercise from the lesson “Heaps: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Computer Science

Complex Data Structures

FAQs on the exercise Removing the Min: Heapify Down II

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!


#2

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.


#3

After the swapping between the parent and the smaller child.
idx = self.get_smaller_child_idx(idx),
this part of your codes is actually re-calculating which is the smaller child between your new child (the parent just heapified-down) and another child (larger one).

Your code should be working fine if all the larger children during each swapping are always larger than the fake-parent (from heapifying-down).

However, if there are any larger children during each swapping, is smaller than your fake-parent. The heapify down process stops, which leaves your fake-parent stuck on that level, results in it may be larger than its child/children.