Now, that we understand exactly what it means to be a minimum heap, let's go ahead and think about how we might build one, through a series of insert operations. We're going to use an existing tree and see how we insert into that tree. Then, we'll generalize this out to understand how we can start with an empty array, enter to that array and create the tree itself. So in this next example, I'm going to do two inserts and you'll notice after every single insert, I'm going to go ahead and as part of doing the insert, check to make sure that every level of my minimum heap is balanced and that the minimum heap property maintenance is true. We'll do that after each of the two inserts and we'll see what elements need to be swapped. Let's look at this example. So I'm going to go ahead and insert the element eight initially. So to insert eight, I'm going to go ahead and just put eight down in the very last element inside my array. So putting this first empty element or the last element inside of my full list of array, I know that this is the same as representing this element inside my visual model and so the tree model has put in eight right here. What do you need to do now is ensure that every single parent has a smaller value than the node I just inserted. So here we look at eight to seven, we see that that value is smaller and we're good. We know that seven small, and six and six smaller and four, because of the insert operations that happened previously. Now, let's insert a second element. Let's insert the element three. So inserting three, again, putting three at the end of the array and then represent that in a tree model as the left child of 20. Here, we have a problem. Now, 20 and three are out-of-order. Three is a small element of 20, which means it needs to be the parent node. So fix this, we simply just swapped those elements. So do that, we find the parent node inside our array and swapped three with 20. Now, three belongs here, 20 belongs at the end. We can do that again, moving up the tree, looking at three versus six. Again, this is out of order. So we go ahead and swap three and six. We do this in the array, which would update our visual structure with three being here and six being here. Next thing is we swap three and four. Three now goes at top, four goes here. In the visual structure, three's at the root and four is on the right child of the root. At this point, we successfully inserted the elements into the array. We maintained the heap property in the tree that we make from this array and see we do this through repeated checks, on whether or not the parent node is smaller than the node that we just inserted. Let's look at the source code to see how this was done. The first thing we need to do every time we insert an element, is check whether or not the array is large enough to accept this element. So here on line five, you're going to see that we're going to check the size of the array versus the actual capacity of the array. If they're the same, we don't have room to insert and therefore, we need to grow the array. So the array is an unordered array in our dataset structure sets. So being in an unordered array, that means that we need to think about how we need to expand it. Going back a couple of weeks, we know that to get the O\ of one amortized runtime performance, we absolutely have to double array every single time. In doubling the array every single time, that means that we are going to have to ensure that we add a whole new level to our heap tree. So what this looks like is the slide that I have next. When we double the array, notice that our old array is going to contain all of the elements in the blue and orange layers. Here, when I filled up this last blue layer, I need to expand the array to add an entire knew layer of the tree. This is equivalent to doubling the size of the array, by making a left and right child at every single node. By adding those 16 elements to the tree that already has 15 elements, plus a node right here at the beginning to denote our zeroth index, we have an array that grows from 16 to 32, then 32 to 64, and 64 to 128. We're doubling in size every time, so we know that this is an amortized O of one operation, as we're running the size of algorithm. So we know how to grow the array. We know it's amortized of one. Let's look at the next chunk of the code. The next line you're going see is line eight. We have the item. This is our array. We're going to insert at the end of our array, the size of our array added by one. We're going to insert the key at that location. Only then, do we go ahead and heapifyUp. This is the name of the function that we're using to ensure the heap property is maintained. Notice the importance to heapifyUp. It is size, it is an index into the array. So we know it's an integer or the index, that's where we're going to heapifyUp on. It's not a value, it's actually index. So we can call this parameter an int index. This parameter is going to then be checked to make sure on line three our base case, that we're not at the root node. So remember the root node is going to be the index one because we've skipped to index zero. So if index is greater than one, we're not a root node. Then, if our value is smaller than a parent value, we go ahead and swap those values. Then, we heapifyUp on the parent node to continue this recursive operation. So the parent of index, which remember this is the floor of our index divided by two, is going to be called to continue our heapifyUp process. At the inner or heapifyUp, we've either reached a root node and swapped the node just entered all the way up to the root, or we've swapped to their correct location and we can stop running the algorithm. In both cases, we ensure that the heap property is maintained by the time we finished this algorithm. So now you know one of the two basic operation in the heap, you know exactly how to insert it. In the next video, we'll dive into how we can actually remove from our heap by removing the minimum element. So I'll see you there.
