Learn

The first thing we want to be able to do is add elements to our heap. This will take a little bit more work than just appending items onto our heap array. Remember, we must write the logic to ensure the following conditions are always true in our heap:

  • The element at the “top” of our heap is the minimum value in the entire structure
  • Every subtree, that is a parent with left and right children, must have children greater than its parent.

Since we are using a custom class, TaskNode we will need to define what is considered equal and what is considered less than or greater than. In the code to the right we’ve included these protocol implementations, as well as CustomStringConvertible to make our end product more readable. We know you’re already familiar with these concepts and don’t want to distract you from the core heap data structure and logic.

We will be keeping dates in order, that is, the oldest date, or the one with the minimum time from now, will be on the top of the heap. This means that if we have a list of five tasks, four of which happen in the future and one that was supposed to happen yesterday, the late task will be on top.

In order to add to the heap we will need to define a new function, add(task:dueDate:). This function will create a new TaskNode, add it to the end of the heap, and then initiate a helper function, heapifyUp() which is used to ensure that all subtrees are properly ordered.

We will keep building on our understanding of abstraction by separating our code into public and private functions. add(task:dueDate) will be a public function so other people using our heap can add tasks to the list, however heapifyUp() will be a private function since only our add(task:dueDate) function will call it. There is no need to expose this code to general users of the heap.

Instructions

1.

In the MinHeap class, beneath the comment for the add function, add an empty add(task:dueDate) function that takes in two parameters, task of type String and dueDate of type Date.

2.

Inside the add function, create a new TaskNode constant called taskNode using the two parameters passed into the function.

3.

After the node creation, add a print statement to show that we are adding the task to the heap. Since we made our TaskNode properties private, we’ve included a getter function inside the class to gain access to the task data. Use the following string in the print statement:

"Adding [\(taskNode.getTask())]..."
4.

The next step is to actually add our new task to the heap. Use the append method to add the taskNode to the heap.

At the end of the file, you will see that we have instantiated a new MinHeap and added some tasks inside of a multiline comment, remove the comments and run the code to check if we are adding tasks to our heap properly.

5.

Our next step is to start the process of ensuring compliance with our heap requirements. Create a new private method under the comment “HeapifyUp Function”. There are no arguments and it doesn’t return anything. You can leave the function body empty. Remember, this function will be private!

6.

Back inside the add(task:dueDate) function, add a call to heapifyUp() after we’ve added the element to the heap array.

7.

At the end of the file, you will see that we have instantiated a new MinHeap and added some tasks inside of a multiline comment, remove the comments and run the code to check if we are adding tasks to our heap properly. You’ll notice that the tasks are not in the right order, we will fix that by implementing the heapifyUp() function in the next exercise.

Now that you can see how we’ve created the first few tasks, feel free to create a few more of your own if you’d like. You can see how that since our function is simply appending the items on to the end of heap they continue to break the rules of a min-heap.

Run the code to continue.

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?