With the bulk of the work offloaded to the
hasOlderChildren(_:) helper function, it is time to implement the
heapifyDown() functionality and then add it to
finishTask(). This way, each time we want to finish a task and remove it, we maintain the heap.
This version of heapify starts at the top of the heap and works its way down through the tree structure, swapping children with parents when the children violate the heap rules. If you remember from the
finishTask() exercise, in order to remove an element from the heap we first swapped the first element with the last element but we left the tree out of order.
In order to heapify down the structure we will use a
while loop to iterate through each of the subtrees that we identify as violating the heap rules. We will only traverse through one path though, either the left or the right child. Each time we swap, we are swapping with the lesser of the two children, ensuring that we don’t need to explore the other branches of the tree, or to put it another way, we are being selective in the branches of the tree that we are disrupting.
The boolean we use to control the while loop and the index we use to swap the parent and child value with both come from the return of the helper method,
hasOlderChildren(_:). We will create a named tuple so we can access the values of the return in a more user friendly way.
Effectively, this iteration will only run at most H times, where H is the height of the tree. Our binary tree is always balanced, that is, each left and right node is always full, with the exception maybe of the very last subtree. We can calculate the height of the tree at any point by taking the log2 of the size, rounding down, and then adding 1. All completely balanced binary trees follow this logic. In asymptotic notation, this is O(logN), where N is the count of elements in the heap.
let height = Int(floor(log2(size))) + 1
Below the comments for heapifyDown, create a private
heapifyDown() function. It should take no parameters and return nothing.
Inside the function create a local variable,
currentIndex, and set it equal to the start of the heap, index
Create another variable,
toSwap, and set it equal to the result of calling
hasOlderChildren(_:) with the
currentIndex as the parameter. Give your tuple values the names of
needsToSwap for the
olderChildIndex for the
Int. Refer to the tuple documentation for a refresher on naming values in a tuple.
Next, create a
while loop that continues while the
needsToSwap property of
toSwap is true.
while loop, print the following message that displays we are about to heapify down:
"Heapifying (down) elements at index: \(currentIndex) & \(toSwap.olderChildIndex)"
After the print statement swap elements in
heap at the
currentIndex and the
Close out the
while loop by adding the logic that prevents an endless loop:
currentIndexequal to the
toSwapequal to the result of calling
The last thing we need to do is call
heapifyDown() whenever we remove an element in the
finishTask() function and test the code. Go to the
else clause in the
finishTask() method, and add a call to
heapifyDown() after the print statement.
At the bottom of the file, call
finishTask() twice, then print the