Question
In the context of this exercise, how does applying heapify up help maintain the heap property?
Answer
Heapify up is guaranteed to maintain the heap property for the subtree of the current element, and as a result, the entire heap, after all heapify up calls, maintains the heap property.
When we first add a new element, it has no children elements. So, the subtree consisting of that new element satisfies the heap property. A heap with only one element has that element at the top, which applies to this subtree of just one element.
Now, if this new element has a parent, we compare them to determine whether to swap them. We know that if the element is greater than the parent, then we don’t need to heapify up, so say that the parent has a child, and is greater than the new element. Since the parent is greater than the new element, the child of the parent is also greater than the element, by transitivity child >= parent >= element. So if we swap the new element and that parent, it is less than both of its children, maintaining the heap property.
Here is a quick illustration of how this would work.
'''
# A new element is added.
# It has no children, so the heap property
# for that subtree consisting of just that element
# is satisfied.
p(4)
/ \
left(5) new(2)
# p(4) is greater than new(2), so
# swap p(4) and new(2).
new(2)
/ \
left(5) p(4)
# new(2) now has the parent and
# the parent's child as children.
# Because left was a child of p(4) previously, we know that
# left(5) >= p(4) >= new(2)
# because of transitivy, and so this
# maintains the heap property.
'''
As we move up the heap, repeating this process, we know that the parent’s descendants must have been less than itself, so we do not have to worry about each subsequent swap messing up the heap property. Rather, each swap is fixing the heap property for that subtree.