Learn

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

Instructions

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 0.

2.

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 Bool and olderChildIndex for the Int. Refer to the tuple documentation for a refresher on naming values in a tuple.

3.

Next, create a while loop that continues while the needsToSwap property of toSwap is true.

Inside the while loop, print the following message that displays we are about to heapify down:

"Heapifying (down) elements at index: \(currentIndex) & \(toSwap.olderChildIndex)"
4.

After the print statement swap elements in heap at the currentIndex and the olderChildIndex.

5.

Close out the while loop by adding the logic that prevents an endless loop:

  • Set currentIndex equal to the olderChildIndex of toSwap
  • Set toSwap equal to the result of calling hasOlderChildren(_:) on the currentIndex
6.

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.

7.

At the bottom of the file, call finishTask() twice, then print the toDoList again.

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?