FAQ: Heaps: Python - Finding the Smallest Child

This community-built FAQ covers the “Finding the Smallest Child” 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 Finding the Smallest Child

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!

we check to see if there’s a right child, but how do we know that there is no left child if we don’t check it? are we just assuming that there is at least one child when we call the function

def get_smaller_child_idx(self, idx):

2 Likes

This is only one step in the “heapifying down” process. It is a method to select the smaller of two children. The way that the heap indexing works, if there is a right child, there must be a left child. So, if there is a right child, select the lesser value between right & left; however if there is no right child, the left child will be selected.

Remember that you have removed the min value from the top by swapping it with the final element. When you have the heapify_down() function fully coded, beginning with that new (non-minimum) top element, each parent will “look at” its two children, use the function you are working now on to swap so that left child is minimum, and then swap left child <--> parent if left child’s value is less than parent’s.

Repeat all the way down until there are no more children…

4 Likes

Another thing to consider. Remember that this is a binary tree, so there must be not more than 2 childs. If there is only 1 child, its the left child because of the way the array is filled. When we remove the last element of the list, we remove the rightmost element (the last right child or the only child (left) if there would be just one at the given last index. When we populate the heap, we do from top to bottom, left to right, so a “no left child” case would likely not happen.

At this point we are dealing with min or max heap, the only element we would need to retrieve (remove) in both cases is the root.

What happens if the two children are of the same value? Which child is selected then?

Hey guys, I have a question about this part:

Which should we choose? We’ll use an example to think it through. Imagine we have a heap with four elements:

print(heap.heap_list) # [None, 21, 36, 58, 42] heap.retrieve_min() # 21 # [None, 42, 36, 58] # Should we swap with 36 or 58?

We want to swap with the smaller of the two children, otherwise, we wouldn’t maintain our heap properties!

Was the 42 supposed to be 24? If not, I don’t understand why you would swap with 36 instead of 58. The exercise tells us to swap with 36 thereby making the list:
[None, 42, 36, 58]

That is not maintaining the minimum heap. That would only be maintaining the minimum heap if they meant to say 24 instead of 42.

What am I missing here?

I think you’ve misunderstood. You’re swapping the 42 with the smallest of the two children ie. the smallest value out of 36 and 58. 36 is the smallest child therefore we swap the 42 with 36. This maintains the minimum heap as the root node is now 36 which is the min value and the two children 42 and 58 are both larger than their parent.