You'll need to log in from a computer to start Introduction to Non-linear Data Structures in Swift. But you can practice or keep up your coding streak with the Codecademy Go app. Download the app to get started.

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.