FAQ: Heaps: Python - Adding an Element: Heapify Up II

FAQ Python FAQ
#1

Community%20FAQs%20on%20Codecademy%20Exercises
Community FAQs on Codecademy Exercises.jpeg1000×208 141 KB

This community-built FAQ covers the “Adding an Element: Heapify Up 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 Adding an Element: Heapify Up 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

First assignment is:

Inside of .heapify_up() , declare a variable called idx and set it to the last index of the internal list.

I used the below, but it returned incorrectly and told me to use self.count:

idx = self.heap_list[-1]

Why would this not work?

Edited to reflect that it told me to use self.count

1 Like
#3

The only reason why I guess this would not work is because the first (and only, after instantiating) element in self.heap_list is “None”, while self.count = 0.

Would you not want to use self.heap_list[-1] because that is “None”?

2 Likes
#4

You are to set it to the last index, not the last element of the list.

6 Likes
#5

Hi,
while I was working on the heapify up funktion. I thought it would be great to actually see the tree and get a better understanding of what I’m doing.
Therefore I wrote a tree_update helper function. Maybe it can be some help for others as well.

put the maximum idx and you can call it after and before you add a new element to see the chances.
Or you can integrate it into the add and heapify_up function by calling self.tree_update(len(self.heap_list))

On a side note: The function could be smarter, but I tried to name everything that it hopefully is self explaining. Feel free to chance it and feedback of course is always welcome.

def tree_update(self,idx):
	tree_range = range(1,idx+1)
	level_count = (len(tree_range) % 2) +(int((len(tree_range)/2)-1))
	print("\nThis Binary Tree has {levels} levels.".format(levels=(str(level_count))))
	print("Every parent has max. two children.\n")
	new_tree_list = []
	spaces = int(idx)*2

	i = 1
	while level_count > 0:
		sibbling_list = []
		sibbling_list.append(self.heap_list[i:(i+i)])
		new_tree_list.append(sibbling_list)
		i = (i + i)
		level_count -= 1

	element_count = 1
	level = 1
	for element in new_tree_list:
		print(("Level: ") + (str(level)) + ("/") + (str(element_count)) + " Child max.")
		print((" ")*(int(spaces)) + (str(element)))
		element_count = (element_count) + (element_count)
		level += 1
		spaces = int(spaces)- (element_count)

min_heap.heap_list = [None, 10, 13, 21, 61, 22, 23, 99] # = 8 elements in list > max idx = 8
min_heap.tree_update(8)
output:___________________

image

#6 
idx = len(self.heap_list) - 1

this would count as well, because we need the last index, not the last element

#7

This is the first time to ask. I need a help to understand the swapping line below. Why are the variables on the right side not left side? What does it mean to assign variable to value??

self.heap_list[idx] = parent
self.heap_list[self.parent_idx(idx)] = child

#8

Hi @tera3233728489.

You’re just modifying a single element of the list referred to by self.heap_list using idx as the index. A quick simplified example-

lst = ['a', 'b', 'c']
lst[2] = 'egg'  # modify the reference at index 2
print(lst)
Out: ['a', 'b', 'egg']

So in your example you’re changing self.heap_list at index idx to the name parent and whatever it references.

#10

Why is the following line of code (instruction 4) resulting in “SyntaxError: invalid syntax”?

self.heap_list[idx] = parent

I checked the indentation, made sure there weren’t but spaces, etc., and keeps throwing SyntaxError.

#11

Syntax errors are one of the ones that often occur from an error on a previous line, e.g. unmatched parantheses, missing separators and indentation problems. Try editing out that line and seeing if the error moves somewhere else because there’s a good chance it occurred on a previous line.

2 Likes
#12

That’s it! There was an unmatched parantheses on the previous line.
Thank you very much!

1 Like
#13

I am sorry, I still don’t understand.
I know to find the last index of the heap_list you could type

idx = len(self.heap_list) - 1

My question is how does self.count do the same thing in this case? I thought it was just an internal counter for our minheap

#15

Why am I stuck in an infinite loop? Here is my code:

class MinHeap:
  def __init__(self):
    self.heap_list = [None]
    self.count = 0

  # HEAP HELPER METHODS
  # DO NOT CHANGE!
  def parent_idx(self, idx):
    return idx // 2

  def left_child_idx(self, idx):
    return idx * 2

  def right_child_idx(self, idx):
    return idx * 2 + 1

  # END OF HEAP HELPER METHODS

  def add(self, element):
    self.count += 1
    print("Adding: {0} to {1}".format(element, self.heap_list))
    self.heap_list.append(element)
    self.heapify_up()
    
  def heapify_up(self):
    print("Heapifying up")
    idx = self.count
    while self.parent_idx(idx) > 0:
      child = self.heap_list[idx]
      parent = self.parent_idx(idx)
      if parent > child:
        print("swapping {} with {}...".format(parent_element, element_at_index))
        self.heap_list[idx] = parent
        self.heap_list[self.parent_idx(idx)] = child
#16

You need to update idx at the end of the loop so that self.parent_idx(idx) updates on each iteration.

#17

I can’t get past the second task of this exercise.
I have written the following code, which I am sure passes the condition for the 2nd task:

  def heapify_up(self):
    print("Heapifying up")
    # start at the last element of the list
    idx = self.count
    while(self.parent_idx(idx) > 0):
      idx = self.parent_idx(idx)

But, the annoying thing is that I am getting an error message stating :

Did you declare a while loop that runs as long as self.parent_idx(idx) > 0 and inside the loop set idx = self.parent_idx(idx) ?

I am really getting annoyed at this one, am I making a mistake somewhere? Or, is this a bug? Please help!

#18

Point 5 of this exercise asks us to swap the child element and the parent element, why wouldn’t this work?

self.heap_list[idx] = self.heap_list[self.parent_idx(idx)]
self.heap_list[self.parent_idx(idx)] = self.heap_list[idx]

Yet we need this:

child = self.heap_list[idx]
parent = self.heap_list[self.parent_idx(idx)]


self.heap_list[idx] = parent
self.heap_list[self.parent_idx(idx)] = child

thanks!

#19

When you reassign a name you would lose the reference that it holds. So for example x = 'red' followed by x = 'blue' on the next line would mean you no longer have a reference to the string object 'red'. Can you see what may happen based on your current execution order?

For another quick to run example-

a = 5
b = 3
b = a
a = b
print(f'a={a} and b={b}')
# What would this output be?
#20

both a and b will be 5, as b was assigned with a, which has the value of b. This I understand. But then in the solution given by the exercise, wouldn’t the line

self.heap_list[idx] = parent

changes the assignment of the variable ‘child’ too? i.e.:
child = self.heap_list[idx] = parent = self.heap_list[self.parent_idx(idx)].

Then how come this line

self.heap_list[self.parent_idx(idx)] = child

won’t equal to this line?

self.heap_list[self.parent_idx(idx)] = self.heap_list[self.parent_idx(idx)]

thanks!

#21

So the main difference to the previous a, b example is that there are two more names being used. It’s like performing the previous step but with a = temp_a and b = temp_b and then swapping the two making use of this temporary names so as to avoid the overwrite. For a quick example using a list and some ‘temporary’ variables-

lst = [0, 1]
temp_a, temp_b = lst
# Note that we now have 4! different references, lst[0], lst[1], a & b
# So it's four references for just two integer objects
lst[0] = temp_b
lst[1] = temp_a
print(lst)
Out: [1, 0]

If you’re not 100% sure about Python’s assignments then it’s worth looking into “pass-by-reference”, “pass-by-value” and Python’s own style (sometimes called pass-by-assignment) as well as mutable/immutable types. It might be a lot of reading and testing if you’ve not come across it before but since this is comp-sci it’s definitely worthwhile.

The following seems to cover most of it but there are multiple guides/tutorials about this if you prefer something else-

1 Like
#22

aha! Thanks for the article! Now it makes sense to me. Really appreciate it! :slight_smile:

2 Likes