This week, we're going to talk about an entirely new algorithm that's getting her mind some best properties of different algorithms. The best way to introduce this algorithm is you just think about a whole bunch of data, a whole bunch of numbers that we might want to insert into our algorithm. This magical algorithm, this magical data structure is going to accept numbers or any other type of data that's comparable. Let's look an example. So here we might have the number three, the number negative 17, the number 42, i , maybe e, maybe number negative 10, maybe even the new number negative Pi. These are all numbers, we could think of any type of data as long as it's comparable. In this data structure, we don't want to maintain a total ordering, we don't want a sorted piece of data because we know that sorted data takes a really long time to maintain. Instead, the only operation we want to care about in this, is we want a data structure that can remove the minimum value and do so quite efficiently. So, if I do a remove operation on this data structure right here, I can simply say, "Remove" and it's going to remove negative 17. Then if I do remove again, it's going to remove negative 10. If I remove again, it's going remove negative Pi. Notice that every single time, the remove operation is not having any parameters, it's simply going to take the minimum value found in the entire data structure, and remove it and return it back to the user. We want to optimize for this to build ourselves something called a Priority Queue, where every single value can have a priority, and we can remove based on the value that has the highest or lowest priority. To understand exactly why we want to build this, we can look at some of the classic data structures we already talked about. Here's four of them. We have right here an unsorted array and an unsorted list. We can see that these lists have great insertion times, but terrible removement times. We have to search through the entire elements, the entire list to actually get at where element is the smallest element. On the other hand, a sorted array in a sorted list has the ability to insert into that list in a very slow manner to maintain that sorted order, but then we can always remove the front element, the smallest element in O of one time. So, unfortunately both of these have an o of n operation, which an operation we'd love to avoid using. Instead, we're going to try and build a data structure that we can do both operations in less than o of n time. To do that, we're going to think about using something like a tree. A tree can be maintained just like our binary search tree that we've talked about earlier in a sense that there's always a left child and always a right child. Though the ordering of this tree is not going to be the strictness of a binary search tree. Because remember in a binary search tree, we have detailed explanation of exactly what we need on each side, and we find that that structure's going to lead to some performance decreases that we're not going to find acceptable. Instead, we can go ahead and build out a new data structure by using the idea of a tree and sticking one property on it. Specifically, we're going to call this new type of tree a heap, and the heap is going to have a few properties. The first property is a binary tree T is a minimum heap if either the tree is empty. So, either we have a tree that has no nodes or we have a tree that has both a right and a left child such that both the left and the right child nodes are larger than the root node. So, all we care about in the heap is everything underneath our current node, all of our descendants must be larger than our self. We don't care anything about our siblings or anything that happens in another part of the tree. The only property about the heap that matters is everything that's a descendant from a node has to be larger (in a min-heap) or smaller (in a max-heap) than the node itself. So, what that means is, if we look at this heap right here that everything on the left-hand side is greater than four. We don't care anything about the right-hand side when we're just looking at the left-hand side. Likewise, everything on the right-hand side is going to be greater than four as well not caring about anything on the left-hand side, and this of course applies recursively. So, everything on the left child of five is going to be greater than five not caring about anything else in the tree itself. All we care is this local property that the parent is going to be smaller than all of its descendants. This property, we're going to actually represent using a clever data structure because we would ideally love the performance of an unsorted array, some of those all of one great guarantees for lookup that we don't have necessarily on, that we absolutely don't have on a binary search tree. So, what we'll do is we'll always ensure a heap is a complete tree. Remember a complete tree is going to be a perfect tree with every node filled in up until the last level, and in that last level we're going to have all of the nodes pushed to the left. Notice this complete tree right here. Once we have a complete tree, we can go ahead and map that tree entirely to a data structure that we're very comfortable with. When we have this tree in memory, we are going to store it as an array. So, specifically let's look at this mapping. When we have this tree, we actually going to represent this tree in memory as an array. So, if we look at this example, we see that here four is going to be the root of the tree, and it's going to be the first element in the array. Five and six will be the next two elements in the array, then the four children of those elements are going to be the next four elements. Notice from the color gradation, [in the diagram, each tree layer is shown with a different color] we have five and six are both greater than four. All of these nodes are going to be larger than their parent nodes. What I'm going to do is, I'm going to actually not think like a computer scientist for a second. I'm going to start indexing the structure from the value one. Just so I don't even confuse myself, I'm going go ahead and put it at zeroth index into this, and I'll just mark it with an X to denote I'm not going use it. So, here's index zero, one, two, three, four, five, six, seven. So, given any random nodes, so, let's look at this node nine, it has an index of five. If we know the node's index, let's look at where its parent is. The parent of the element nine is going to be the value five. The value five is here at index two. How did we get from five to two? Well, that looks like integer division. So, five divided by two using integer division is two. Let's look at the other child, 15 as the other child, 15 is index four, four divided by two is also two. So, inside of our array, we can always navigate to our parent not by having a parent pointer, but we know our parent is equal to our index divided by two. Likewise, we can navigate to our children the exact same process by inverting this equation. We know our left child given a parent is going to be equal to i times two. So, looking at the value 20 for example, we know that 20 doesn't have a left child because seven times two is going to jump to 14. Looking the value six above 20, six's left child is seven. So, six, three times two is six. So, left child can be gotten by multiplying our current index by two, our right child is going to be gotten by multiplying our current index by two and then adding one. So, what we have here is the entire memory representation of our heap is going to be entirely an array. All we're going to have in memory is our array. We're not going to have the tree structure in memory at all, but when we're actually doing the analysis, we'll draw it as a tree because it's going to be way easier to think about things in a tree. Notice that we have the exact same tree structure we've had before. This is just like the binary trees you learned about earlier, but now we're going to shrink this binary tree into an array. We're going to have special properties on this array, so that we can always go to our parent and child quickly, and we know that these operations all have simple mathematical formulas that allow us to compute them extremely quickly. Because everything is a power of two, we'll see that computers actually do this even faster than we can imagine. So, this is a setup for a heap. In the next video, I'm going to talk about how we can actually insert data in the heap and maintain this heap as we're building our priority queue data structure. So, I'll see you then.
