OK, so who to another lecture on heaps and this lecture, we're going to go over deleting a value from
a heap.
And we also have something that kind of goes along with that called heap of Phi, which is basically
making sure that the heap maintains all of its properties for it to be called a heap price.
So once we delete, if it misses the heap up, we have to kind of reheat it right.
So let's get into it.
So deletion from a heap.
Well, if you think about deleting something, the simplest case is if you were to just delete the last
value, it's very easy.
So we're thinking about twenty one here.
You see, it is the last thing in the array and also at the bottom right.
Most last thing in the heap that's described as a tree here, right?
So deleting that thing is simple.
We just remove it, right?
Take it out of the array.
It's done.
But what about a different position?
So more specifically, let's look at the root, because that's kind of the one that has the most like
dependent connections on it, right?
It has all these children, these sub trees, the rest of the heap, if you will, sub heaps technically,
right?
So if we want to delete any other position in the last position, we have to kind of follow these steps
right here.
So we have to first swap it with the last position structurally.
So that means the bottom right and of course, corresponding to the last position in the array.
After that, we can delete it.
So if we want to delete that three, we can move it down here, move the one here, delete that three.
But then when we have to do is sift down that 21 to the correct position.
So the heap still maintains that numerical property, right?
So we go ahead and do that.
We swap it with the last position.
So you notice it got swapped down there and then we can go ahead and delete it.
So now it's deleted.
But now we have 21 here and you know, that's not OK to have five here and 21 as a parent.
So we need to start doing the next part, which is 50 and down to the correct position.
And this is what we actually call the heap of five part.
This is this is the heap application process.
So this process has its own steps to kind of sub steps, right?
So what we want to do first is compare it to the left child and we will of course, compare it to the
right if necessary, kind of get to one of those situations down here.
But first, we compare to the left and then what we're interested in is comparing the left and the right
child to see which one is smaller.
And we will just swap with the smaller child, right?
Because this process, unlike insertion insertion, was bubbling up, right?
This process is sifting down, so we're swapping down rather than swapping up.
So the 21 needs to go down and buy it, swapping the it'll basically grab whatever is smaller than it
and move it up.
So it maintains the key property, right?
But we're not going to continually move the smaller values up.
What we're continually doing is trying to move the twenty one down right, the bigger values down in
this case.
So we compare it to the left child, right.
Twenty one and five.
So five is definitely less than 21.
The next thing we're going to do is compare five and the right child retinol, also 21 five, as we've
already said, is less than 21.
Right.
So it's less than the right child.
And then we want to swap with the smaller child.
So we go ahead and swap the 21 with the five like that.
We start the process over again.
Let's go ahead and check the left child of where twenty one is now twenty eight bigger than twenty one.
No, it's not.
So we're actually going to have to consider the right child in this situation.
So what we want to do, though, is compare the left and the right child.
So we want to see, OK, well, which one is smaller?
So 18 is smaller than twenty eight, right?
So that's the one we want to swap with.
But we also have to make sure that we compared 21 with 18 to make sure that the value down here was
in fact smaller.
So we could do the swap kind of like we already did with the left child right.
So that's where that right, if necessary thing comes in.
So we'll go ahead and swap with the smaller one of the children, which was 18.
So we go ahead and do that.
And then at this point, we have arrived with a normal heap, right?
And we can check that because everything, all the children of the parents should be larger values,
right?
So let's check out five.
Are its children larger?
Yeah.
Eighteen and five.
Twenty one thousand five.
Let's look at 18.
Yeah, eighteen left child is twenty eight.
That's bigger.
Eighteen right child is twenty one.
That's bigger.
So this satisfies the heap numerical property and the structural property in the fact that it has only
been building out from the left right.
So this is we could consider this a complete proper heap.
So what is the time complexity of this?
Well, we can safely say that the worst case time complexity of delete slash heap of pie is, oh bigo
of log in.
Why is that?
Well, the reason why is because in the worst case, what we have to do is sit down that value all of
the levels of the heap, right?
So basically, when we're talking about 50 and down all the levels of the heap.
If the reason that it becomes law in time complexity is because a heap has long in levels and that is
where a. the number of values.
So if you check this out, we have one two three four five.
So we have five nodes in the three or five values in the array, respectively.
And we have we have, let's see, one two.
So it will be like zero one two, right?
The number of levels that we would consider it.
So what you can say is basically if you did a log of five, you notice that it would be two point seventeen.
And we would kind of round that down and that would end up being the levels of how many levels are in
our heap.
So the reason that that works out well is because let's say we have some more nodes in here, so right
now we've got five, right?
But if we were to add one here, we would have six right and it would still have the same number of
levels, right?
So this is like, you know, one two.
If we add another note off to the right, like a right child here, it would still have the same number
of levels right now would be seven.
And so if you look that up, you know, like log five and log of six.
And we're talking about log base two, right?
So log a five log of six, log of seven and those are two point seventeen.
So we can write that down, you know, it equals the level, the number of levels in the heap.
So that's how we can safely say that the worst case time complexity would be Bigo of log of it for the
delete heap of fire.
And we'll talk some more about the time complexity of the other operations on the heap in the next lectures
when we talk about those operations in specific.
We'll get back to the insertion and how the time complexity of that insertion we already looked at is
when we compare it to kind of another way to build a heap.
All right.
So with that, I will see you in the next lecture.