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 tofalse
olderChildIndex
, a variable, initially set to0
leftChildIndex
, a constant, equal to the left child index of thecurrentIndex
rightChildIndex
, 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
currentIndex
is greater than the task at therightChildIndex
.
AND
- The task at the
rightChildIndex
is 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!