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.
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,
while statement that checks for two things:
currentIndexis greater than 0 AND
- The element of
currentIndexis less than the element of
heapat the parent index of
currentIndex. Use the helper function
Leave the body of the
while empty for now.
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))"
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.
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