Let’s start scratching off some of the tasks on To-Do List with a
finishTask() function that actually removes items from the heap!
Our heap, while stored in an array, is actually a binary tree with the root node being the minimum element of the heap. If we simply remove the first element of the array, we will leave the whole structure without a root, essentially fracturing our tree in half. The only elements that can be removed from a tree that are guaranteed not to cause any fractures are leaf nodes, that is, it doesn’t have any children.
In order to remove the top of our heap, we will have to swap the element at the top of the tree with the element at the bottom of the tree. Once again, we will turn to array’s
swapAt(_:_:) function to do this. In making the last element of the heap the new root, we will be in violation of the laws of our heap and need to move, or
heapifyDown that element back into its rightful place to restore order in the heap.
For starters, we will focus on the core logic of the
finishTask() function before we move on to reordering the heap. Before we can go about removing an item from the heap, we start by checking if there are any items. If there are, we swap the top and the bottom of the heap and remove the new last element (the former top).
Underneath the comments for the
finishTask function, create an empty
finishTask() function that has no parameters and returns nothing.
Inside the new function, create an
if statement that checks if the
heap has elements in it. If it is empty:
"There are no tasks left to complete."
At the bottom of the file, after
toDoList is instantiated but before tasks are added, make a call to
finishTask(), you should see your message printed out.
else clause, inside the body:
- Use the array function,
swapAt(_:_:), swap the first and last elements in the array.
"Removing: \(heap.remove(at: size - 1))"
At the bottom of the file, after the tasks have been added to
toDoList, make a call to
finishTask() again. Also, print out
Look at the order of the heap now, we have a task that isn’t due until 2041 at the top of the heap and a late task further down! While we did successfully remove the top of the heap, we still need to reorganize it with a
heapifyDown() function that we’ll build in the exercises coming up. Run the code to continue.