Before we begin work on the heapifyDown() function, we have one more helper function we need to create, hasOlderChildren(_:). This function will do the brunt of the work when it comes to determining how we are going to execute our process to put the heap back in order after removing the top of the heap.
The function will get passed in the index of the current task we are checking, the current parent. It will then begin by looking at the left child, if there is one, and it is larger than the parent, we know we need to swap. In order to keep the heap in order, we need to swap the oldest of either the left or the right child, so the next thing we do is check the right child against the parent and the left child. Any task that exists in the past is “older” than any task that exists in the future. In our MinHeap, we always want the oldest task, or the minimum from today, to be on top. Dates in the past have “negative” differences from today, making them the minimum values.
The function returns a tuple, a boolean value to control the logic of the heapifyDown() function, and the index of the oldest child so we can swap the parent and the oldest child side of our heap.
There are several other ways to implement this functionality, however, the goal is to give you practice with returning different types of data structures and using them in unique ways. Most interview questions aren’t difficult in nature, they just require an “outside the box” approach to problem-solving, and we’re here to put as many tools as we can into your tool belt.
Instructions
Inside the MinHeap class, you will see a comment for the hasOlderChildren function. Below it, create a private hasOlderChildren(_:) function that takes one parameter, currentIndex of type Int with an omitted argument label. The function returns a tuple containing a Bool and an Int. Inside the function, return a tuple, (false, 0).
The function will have four local values, two variables and two constants:
olderChild, a variable, initially set tofalseolderChildIndex, a variable, initially set to0leftChildIndex, a constant, equal to the left child index of thecurrentIndexrightChildIndex, a constant, equal to the right child index of thecurrentIndex
Insert them above the return statement then modify the return statement to return olderChildren and olderChildIndex in place of false and 0.
The next thing to do is check the left child. Above the return statement, create an empty if statement that checks if the left child exists using the indexExists(_:) helper method AND that the task at the currentIndex is greater than the task at the leftChildIndex.
Inside the if statement, set olderChild equal to true and olderChildIndex equal to leftChildIndex.
Now we’ll check if the right child is in fact the one that needs to be swapped.
Create another, separate empty if statement after the last. It will check three things:
- The right child exists.
AND
- The task at
currentIndexis greater than the task at therightChildIndex.
AND
- The task at the
rightChildIndexis less than the task at theleftChildIndex.
Finally, inside that if statement, set olderChild equal to true and olderChildIndex equal to rightChildIndex.
Our helper function is now complete!