[MUSIC] At this point, you know what it means to be a and you know how to insert an element into the heap. Let's go ahead and remove an element from the heap. To do so, we are always going to be removing the minimum element. There is no operation on the heap that we can do except for removing that minimum most element. So to do so, we're going to going to have to figure out the algorithm to take the top element of the tree, the root of the tree itself and actually maintain the heap property even after removing the tree. So let's look at an example of removing a couple of nodes. So here's a tree we had in the previous video before we did any inserts. Now I want to remove minimum on our root node. So removing minimum is going to take four out of the tree. To do that, I'm going to go ahead and use a clever approach of actually just swapping the very last element on our tree with 4, to ensure that we don't mess up the tree structure itself. So as removeMin, I'm going to take 4 out and I'm going to put that very last element, 11, into this tree. So doing that means that we have complete tree still, we haven't ruin our tree structure, we've just ruined the order. In the previous example, we did a heapifyUp to do insert. Here, we're going to heapifyDown to do or remove minimum. So looking at our root node, we need to compare with the child and take the smallest of the two children and swap the smallest child with the note above it. So here 11 and 5 needs to get swapped so that 5 five becomes a new root and 11 becomes a left child. Here, we can then compare again to next level, 11 versus 9, 9 is smaller, we need to bring 9 up and bring 11 down. Here, 11 is smaller than both 14 and 12. Therefore 11 has found its proper spot and we've maintained the heap property. Let's do one more example here on this slide to understand exactly how this works. So going to our second example, we're going to removeMin again. Removing min a second time means that we're going to remove the element 5. So 5 gets removed and 12 becomes our new root note. We remove 12 entirely from the tree. What this means is here, we're going to be updating their rate every single point of view, the way but I'm here just updating the tree to make it simpler. Looking at 12 we're going to compare our two children nodes. Here 6 is going to be the smallest element. So 6 become a root, 12 becomes of a child. Again, comparing the two children in 12, we have 7 versus 20, 7 is a smaller element. We swap 7 and 12, bringing 7 down here, and 12 here. So again, we've maintained the heap property by doing a series of heapifyDown operations. It's going to ensure that after we finish doing our remove, that we'll ensure that the tree is a complete tree and that every single level has nodes whose the smallest element is the root node and larger elements are always below that root node. The next thing we can look at is how do we actually run this? What's the actual code? Here, looking at the code, we see the codes really simply for removeMin. The first key operation here is we're going to swap with our last element. The second key operation going to do is we're going to heapifyDown so this is what will stores it to heap property. And like heapifyUp, we have a helper function that's going to do this he will heapifyDown again always starts at the end the with the root node. So we know exactly how to begin the call heapifyDown. Looking at heapifyDown, we'll go and start this at element one, the root of the tree. We're going to heapifyDown, check if it's a leaf node. If it is not a leaf node, we know that we need to compare again to children. We're going to compare whether on the item at our current index is going to be the item at the minimum child's index. So we want to check whether or not our current item is larger than the item of the currents smaller. If it is, then we can go ahead and need to call our heapifyDown recursively after doing the swap operation on line 6. So the very last thing we're going to do is we're going to heapifyDown, again on an index. So this will be the minChildIndex, which says that we are going to heapifyDown, by swapping the element with the minimum of our two children. And in doing that swap, we're going to ensure that heap property is maintained because the smallest element among the two children is now placed on top. So we know after the swap that among the sub tree that includes our root node and our two children, that the root node is the smallest. Then we need to recursively continue down the path that we did the swap in. After doing this recursive operation, we know by the time we reach a leaf node that we found the proper spot to restore the heap property of this tree. So through two really clever algorithms, inserting using heapifyUp, and removing minimum by using heapifyDown, we're able to maintain a minimum heap through a series of simple tree operations that offers us an extremely efficient structure to maintain an ordered insidered array without having a totally ordered array. This is going to be a really useful property, and we're going to start building properties on top of heaps, in the next lecture, so I'll see you there.
