Welcome back. Today we're going to look at how to remove elements from a binary heap. This is Part Four or five in the priority queue series, make sure you watch the last video, so we understand the underlying structure of the binary heap. So let's get started. In general, with heaps, we always want to remove the root value, because it's the node of interest. It's the one the highest priority is the smallest or the largest value.

When we remove the root, we call it pulling a special thing about removing the route that we don't need to search for its index. Because in an array implementation, it has position or index zero. So when I say pull, in red, we have the node we want to remove and in purple is the one we're going to swap it with. So the note in purple is always going to be the one at the end of our array, which will also have its index. So we swap them, we get rid of the one. And now, since 10 is at the top, well, we're not satisfying the heap invariant.

So we need to make sure that the heap invariant is satisfied. So we need to do what's called bubbling down now instead of bubbling up, what we do is we look at 10s, children five and one, and we select the smallest, and we swap with the smallest, so 10 would go to one. So make sure you default selecting the left node in case there was a tie. So as you can see 1010s children are And two, they're both equal. So we're going to select the left node to break time. And now we bubble down 10 again.

And now the heap invariant is satisfied. Now we want to remove value 12. So pulling was removing the element at the root, but 12 is not at the root. However, we still want to be able to remove 12. So what we do is we have to search for 12 in our tree, even though we don't know its position yet. So we start at one and we do a linear scan through all our elements until we find 12.

So five is not 12, two is not 12, and so on until find 12 and now We found 12. And now we know where its position is. So we can mark it as the node we want to remove, and also swap it with the purple node being the last node in our tree, swap them remove the 12. And now we're in violation of the heap invariant. So now we want to bubble up three, until the heap invariant is satisfied. And now we've satisfied the heap invariant so we can stop.

Now we want to remove three. Same thing as last time, search for three in the tree. Three wasn't far it was just two nodes away. So now to remove an element, again, swap it with the last note in the tree. Drop it Now the question is, do we bubble up or bubble down the value? Because you don't really know what the value of the note in the last position is when you're swapping it in.

So, do we bubble up or bubble down? Well, we already satisfy the heap invariant from above. So we need to bubble down 15. So, so five was smaller, so we swapped it with five. Now eight is smaller, so we swap it with eight. And again, the heap invariants are satisfied.

Now he wants to pull. So Mark, the root node, red, swap it, remove the one and now we want to bubble down and he'd been very dissatisfied. Now we want to remove sinks, so search for six in our tree. Okay, we have found six and do the swap, remove six. Now, do we bubble up a bubble down? The answer is neither the heap invariant is already satisfied.

So we don't even need to touch our node, we got lucky. So from all this polling and removing, we can conclude the following. That polling takes logarithmic time, since we're removing the root, and we already know where to find it. And also that removing a random node can take up to linear time, since we have to actually find the index of that node we want to remove before removing it. However, if you're as dissatisfied this linear removal as I am, you'd figure out that there has to be a better way. And indeed, there is and I'm about to show you a hack to improve this complexity to be logarithmic in the general case, so stay tuned.

Okay, so now we're going to look at how to remove nodes from a heap with the improved time complexity. To do this, we'll need to make use of a hash table, a data structure I have not yet covered. So buckle up, things are about to get a little wild. I promise I'll cover the hash table thoroughly in a later video. But right now it's going to look like magic. Back to the central issue, we have a bunch of nodes scattered across our heap at some positions, and instead of doing a linear scan to find out where the node we want to remove is, we just want to be able to do a lookup and figure that out.

The way we're going to do this is that every node is going to be mapped to the indexes found that. So when we want to remove a particular node, just look up its index. And so doing it linear skin. Sounds good, right? That sounds great except for one caveat or two. What about if the heap has multiple nodes with the same value?

What problems with that cause? Well, just a few, but nothing we can't handle. To begin with, let's talk about how we can deal with the multiple value problem. Instead of mapping one value to one position, we will map one value to multiple positions. And we can do this by maintaining a set or tree set of indices for which a particular node value or key she want maps to. So can I example, okay, so observe the blue heap remark that has repeated values.

Namely, we can see that the two is there, three times seven is They're twice 11 and 13. Once the low I have drawn the index tree, a tree, which can help us determine the index position of a node in the tree 11, for example, is that index 313 at index five, and the first two at index zero. On the left is the hash table with the key value pairs. Notice that two is found in three positions 02 and six, while sevens found two positions, one and four and so on. So this is how we're going to keep track of the positions of the valleys in the tree. If notes start moving in the tree, we also need to keep track of that, for example, for bubble up or a bubble down cursory to track of those movements, and where the swaps go to so we can update the index position in our map we swap 13 The last seven, for example, the following should happen.

So we look at where seven and 13 are in our table. And then I've mapped those respective positions as red for the seven and yellow for the 13. And this is what happens when we do a swap, we do a swap in the tree, but also in the table. And that's it. Okay, so this all sounds great. We keep track of repeated values by maintaining a set of indices, a party or a node, the particular value is found out.

But now let's ask a further question. If we want to remove a repeated node in our heap, which node do we remove and doesn't matter? Because if we look in our heap right here, there's three possible two values we can remove. Doesn't matter which one we remember. Move? The answer is no, it does not matter.

As long as in the end, we satisfy the heap invariant. That's the most important thing. So let's look at an example. Not just removing but also adding and pulling elements with this new scheme I just proposed. It's not that hard, trust me. The first one, we want to insert three, sweet place three at the bottom of the heap in the insertion position.

We also need to track where the new node is. So we add three to our table along with its position which happens to be at index seven. Look at the index, tree and grade confirm this. Now that three is has been inserted, we need to make sure the heap invariant is satisfying. Currently it is not. So what we do is we bubble up three The parent of three is 11, which is greater than three, so we need to swap those two notes.

I've highlighted the seven in the index tree because it maps to three in the heap and three in the index tree because it maps to the value 11. Now swap those both in the tree and in the table. Awesome. Now the heap, they're in some not satisfied. So do a similar thing. For the note above, regard the parent and do a swap in the tree in the table.

And now that the bat invariants are satisfied, so three has been inserted successfully. The next instruction is to remove two from the heap. So which two should we remove? Well, as I said, it doesn't matter as long as we satisfy the heap invariant in the end. If we remove the law too, we can immediately satisfy the heap invariant with one swap. But for learning purposes, I'll simply remove the first one found in our set, which happens to be located at index zero.

So we want to remove the to at position zero. So how do we remove a node again, so we did a look up. So we didn't have to do that linear scan, which was nice. And now we swap it with the end, the last node, which happens to be 11, we remove the last node. Now we need to satisfy the heap invariant. So we need to bubble down 11.

So we look at 11 children which happens to be three and two. Two is smaller, so it's the one we're going to swap with. So swap it in the table and in the tree. Now We are still not in satisfaction the human variant. So look at 11th children being 13 into two smaller, so swap it with two. And that's it, we're done.

The last instruction says the pole, so get the value of the route, just two and swap it with 11. Get rid of the two and bubble down 11. So as you can see, we're constantly updating our table but still doing the same operations. So that's how you do quick removals in a priority queue. So guys, thanks for watching, and in the next video, I promise we'll look at some source code for all this crazy stuff that's been going on. The source code can be found at the link provided on this page.

Stick around if you want to see an implementation and D Tell also the link to that should be in description below. I'll catch you in the next video. Thank you so much for watching.