Learn

Before we can finish the `heapifyUp()` function we need to do a little background work to establish the structure of the binary tree out of an array. To do this, we’ll use a little math magic with the array indices.

The root of our tree will always be at index 0, and its left child will be index 1 while its right is index 2. The first structure is easy, but now what happens when we add children to the left node? In our array, we place those children at index 3 and 4 four respectively whereas children of the first right node would end up at indices 5 and 6.

If we look closely, we can start seeing a pattern emerge. Every left child index is equal to twice its parent plus 1 and every right child index is twice its parent plus 2. Let’s consolidate the rules:

• `leftChildIndex = (parentIndex * 2) + 1`
• `rightChildIndex = (parentIndex * 2) + 2`
• `parentIndex = (childIndex - 1) / 2`

Since we will be constantly getting and setting values using this logic, we’ve created a series of “help the helper” functions that return these indices. We’ve also included another helper function that checks if our index exists in the array, that way we don’t end up trying to stick a value outside the bounds of the array.

Now that that’s out of the way, let’s finish implementing the `heapifyUp()` function. The basic functionality of this function will be to iterate from the end of the array where we added a new element and check if the current task we are visiting is closer to today than its parent. If it is, we need to swap those elements and then redo the test on the new parent.

### Instructions

1.

Inside the `heapifyUp()` function create a new variable, `currentIndex`, equal to the last index of the `heap` array. You can get the size of the array by referencing the computed property, `size`.

2.

Create a `while` statement that checks for two things:

• The `currentIndex` is greater than 0 AND
• The element of `heap` at `currentIndex` is less than the element of `heap` at the parent index of `currentIndex`. Use the helper function `parentIndex(of:)` here.

Leave the body of the `while` empty for now.

3.

Inside the body of the `while` loop, start by printing the following data so we can see when we’ve had to perform a swap.

``"Heapifying (up) elements at index: \(currentIndex) & \(parentIndex(of: currentIndex))"``
4.

After the print statement, we need to actually perform the swap. Arrays have the perfect built-in function for this, swapAt(::) that takes two element indexes and swaps the values at those locations. Call the function on `heap` passing in the `currentIndex` and the parent of `currentIndex` as the arguments. Reference the parent index the same way we did in the `while` loop logic.

5.

At the end of the `while` loop, still inside it, set the `currentIndex` equal to the parent index so we can check the next parent/child relationship until we reach the top of the heap.

Uncomment the last lines of code, run it, and look at the output. You can see that we have called our `heapifyUp()` function and that the heap now has the “Submit Initial Design Ideas” task at the top. You will also notice that when we print an item if the date is older than now it will be printed with “LATE: “ in front of it.

If the program never stops running after hitting “Run”, it’s entered an infinite loop, refresh the browser window, and double check your code to make sure we’ve added the proper logic to exit the `while` loop.