ENDS 12/4: Get 50% off your Pro annual membership using code [CYBER23](https://www.codecademy.com/checkout?periods=year&plan_id=proGoldAnnualV2&discountCode=CYBER23)


An implementation of a heap data structure, as well as a discussion of the techniques around the implementation of methods and properties that make a heap function.

Heaps: Swift

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 and Helping the Helpers

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](https://docs.swift.org/swift-book/ReferenceManual/Types.html#grammar_tuple-type), 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.


Finding the Children

It turns out we are having some trouble staying on track with our programming lessons and need to devise a way to keep track of all the things we need to do, particularly what we need to do next. Why not solve this problem by creating a To-Do list tracker that will let us keep track of the upcoming (or late) tasks and also practice some data structures and algorithms at the same time!

We will implement a `MinHeap` class. It will keep track of our `TaskNode`s, a modification of our previous `Node` and `TreeNode` classes, in an array. It will also store the number of elements in the heap through a `size` property and whether or not the heap contains any elements with another property, `isEmpty`.

We will be working with the [Date](https://developer.apple.com/documentation/foundation/date) data type. This structure is found in the Swift package, `Foundation`, and will be a necessary import at the top of our file. `Date` represents a single point in time that is independent of any calendar or time zone. Internally it is stored as a floating-point number of seconds from 1/1/2001 at 00:00:00 UTC and will display to the console based on the current operating system (or selected) date/time format. You’ll get to see it in action as we progress.

For now, let’s begin filling out our classes!


I'm Late, I'm Late!

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.


Heaping It On

With the bulk of the work offloaded to the `hasOlderChildren(_:)` helper function, it is time to implement the `heapifyDown()` functionality and then add it to `finishTask()`. This way, each time we want to finish a task and remove it, we maintain the heap.

This version of heapify starts at the top of the heap and works its way down through the tree structure, swapping children with parents when the children violate the heap rules. If you remember from the `finishTask()` exercise, in order to remove an element from the heap we first swapped the first element with the last element but we left the tree out of order.

In order to heapify down the structure we will use a `while` loop to iterate through each of the subtrees that we identify as violating the heap rules. We will only traverse through one path though, either the left or the right child. Each time we swap, we are swapping with the lesser of the two children, ensuring that we don’t need to explore the other branches of the tree, or to put it another way, we are being selective in the branches of the tree that we are disrupting.

The boolean we use to control the while loop and the index we use to swap the parent and child value with both come from the return of the helper method, `hasOlderChildren(_:)`. We will create a named tuple so we can access the values of the return in a more user friendly way. 

Effectively, this iteration will only run at most H times, where H is the height of the tree. Our binary tree is always balanced, that is, each left and right node is always full, with the exception maybe of the very last subtree. We can calculate the height of the tree at any point by taking the log<sub>2</sub> of the size, rounding down, and then adding 1. All completely balanced binary trees follow this logic. In asymptotic notation, this is O(logN), where N is the count of elements in the heap.

```swift
let height = Int(floor(log2(size))) + 1
```


HeapifyDown

Now that we can add a task to our heap and we can see that our `heapifyUp()` function is working as advertised, it is time to start getting access to the items we add to our To-Do List so we can get things done!

The first access function we are going to create is `getTask()` which will work the same as a `peek()` function. It would be a pain if every time we accessed the heap we had to remove the top item to work on it and then put it back into the heap if we didn’t finish it. Besides making our code base less readable, it also eats up processing power every time we have to reorganize the heap.

Our `getTask()` will give the user access to the task on top of the heap without actually removing the `TaskNode` from the heap. To execute this process first we check if the heap has items and if it does, we read the top task and present it to the user so they can begin work. Since we are storing our heap in an array, the top of the heap is located at index 0.


Taking a Peek

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).


Finishing a Task

A heap is a specialized data structure used to keep track of the **minimum** or **maximum** values in the structure. We visualize a heap as a binary tree, although in implementation it is most common to use an array to store our values. Binary trees, a subset of a classic tree structure, will be discussed more in-depth in a later lesson, but essentially means that each parent can have at most two children, a left child, and a right child.

The beauty of modeling the data as a binary tree allows us to take one small chunk of a large data structure, a single tree branch (parent, left child, right child) and apply an algorithm to just that branch and then repeat it throughout the whole tree. This technique of reducing a problem down to its smallest solvable chunk is called dynamic programming, a common topic of technical interviews. In order for our data structure to be truly classified as a heap one of two conditions must be met for each branch in a binary tree:

- In a min-heap, for any given element, its parent’s value is less than or equal to its value.
- In a max-heap, for any given element, its parent’s value is greater than or equal to its value.

One of the most recognizable advantages of a heap is the ability to get the minimum or maximum item from a data structure in O(1) or constant time. Since we are working on a type of binary tree, we can assume that each time we add or remove an item from the heap and re-sort it will run in O(logN) times where N is the total number of nodes in the tree. These are quite good run times for our basic get, add, and remove functions!

Heaps are commonly used as priority queues, think a standard FIFO (first in first out) queue except we want the first out to be the min or max of the items in the queue. Most famously though, a heap is used when implementing Dijkstra’s algorithm for finding the shortest path in a weighted graph (road networks, character move sequences, or finding how many [degrees of separation](https://oracleofbacon.org/) you are from Kevin Bacon).

Heaps commonly come up on interview questions, though rarely as the primary question and more as the hidden optimal solution to a problem that can be solved another way with a brute force method.

Throughout this lesson, you will learn how to implement a min-heap that will be responsible for keeping track of a To-Do list of tasks and due dates.


Introduction to Heaps

Wow! Now that we’ve got a handy data structure for our To-Do List, we can get all caught up on the lessons we need to finish! Let’s review some of the things we’ve learned as we’ve built our MinHeap implementation.

To review
- A heap is a data structure that stores the minimum or maximum values at the top of the heap, depending on how it is set up
- Each subtree, that is a parent node and its left and right children, will also maintain order. The parent node is always less than its children in a min-heap, or greater than its children in a max-heap.
- The top of the heap is accessed in O(1), or constant time, since the value at index 0 is always the priority value, no need to search for it.
- Adding and removing elements from the heap run in O(logN) time, where N is the count of all elements in the heap.
- Heaps, though visualized as binary trees, are most commonly stored in an array. Parent and child elements are not stored sequentially but rather separated by a factor of 2.
- When we add an element to a heap, we add it at the end of the array, we then must heapify up until we find a place in the tree that satisfies the heap conditions.
- Removing an element is not as easy as removing the first element in the array, if we did that we would fracture the tree. Instead, we swap the first and last nodes, remove the last node, and then heapfiy down the tree from the new top node until its placement satisfies the heap conditions.
- Heaps are integral to the famous Dijkstra’s algorithm, which uses a min-heap to find the shortest path between two nodes of a graph.

Heaps are invaluable data structures to add to a software engineer's toolkit. While not the right technique to use when sorting a data set, they are excellent when you only need to know the next value you need to work on.
Congratulations on expanding your understanding of this structure!
