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 () 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 () below!
Agree with a comment or answer? Like () to up-vote the contribution!
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”?
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:___________________
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??
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.
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!
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?
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)].
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-