Welcome back.
So we have successfully coded our max binary heap.
We have designed it.
Now let's take a sample input and walk through the code that we have written.
Now first we look at the build heap function.
And let's say that this array over here is passed to this function.
It's eight, six, one, 15, 12 and five.
Now we can visualize this array as a binary tree.
In this manner we are just filling from left to right.
So we have eight, then six and one, then 15, 12 and five.
All right.
So now we are over here.
We are inside this function.
And we find the length of the array which is equal to six over here.
Right.
This length is equal to six.
Now let me just write the indices over here.
So three four and five.
Now we find the last parent.
We know that the range of the internal nodes is zero to math.floor n by two minus one where n is the
size of the array.
So over here it's six by two.
And my math dot floor.
So this gives us three three minus one gives us two.
So the last parent has the index two which is this one over here.
And that's this element right.
So 012.
And then we have 345.
So here visually we can see that these are leaf nodes.
So they are not internal.
So yes this is the last parent node.
So we find that index two over here.
Then we go from I is equal to two.
So from I is equal to two till I is greater than equal to zero.
So two one and zero.
So for these values of I we will go through the for loop right.
So we will loop again and again.
So initially I is two.
Then I will be one.
Then I will be equal to zero.
So for these values of the indices we will call the bubble down function.
And we will pass the array and that particular index.
And then that's it.
So that's how our build heap function works.
So let's try and look at the bubble down function.
And let's see what's happening when we call this for the index two.
So that's this element over here.
All right.
So over here we have our bubble down function.
And we are calling it for index two.
So this is zero.
This is one and this is index two.
All right.
Now again this is three.
This is four and this is five.
Now we are inside this function.
We find the length of the array which is equal to six over here.
And then we say current is equal to array at index.
And the index at this instance is equal to two because we called it for I is equal to two.
Now the current over here is array at index two which is equal to one.
So let me just write it like this.
So that's current.
So current is pointing to this node over here.
All right.
Now we loop again and again.
As long as this is true.
Now let's see when we break out we will see that we will break out over here right when.
And again we will analyze this.
So what happens over here.
First we find the left hand child left and right children right.
So left index is two into I plus one.
So two into two is four four plus one is five.
So this is the left child index.
So we get that the left child index is equal to five.
And then right child index is two into two plus two which is equal to six.
Now again we over here we have a variable largest and it's set to null.
So this is something that we are going to use whether we can stop or not.
Right.
If we find that the node is in such a position that we don't need to make any swaps, then we can stop.
So we want to know when we can stop bubbling down.
So we will use this variable for that.
So initially it is null.
And once we are through with this part, if it is still null we will break out of the while loop.
All right.
So that's the condition.
Now let's look at what is happening over here.
First we are going to check whether the left child index which is five is less than the length which
is equal to six.
So five is less than six.
That means there is a valid node over here.
All right.
So we say left child is equal to array at left child index which is five.
So this over here the left child is identified at this point.
And then we are checking whether the left child is greater than the current value.
So the left child value over here is five and is five greater than the current value which is equal
to one.
Yes, that is true.
Right.
This is true.
So that means we need to make a swap.
Right.
So this order is not correct.
We need to make a swap again.
Remember we are building a max binary heap over here.
So the parent has to be greater than the child.
So over here we say that largest is equal to left child index.
So at this point largest becomes equal to five.
So let me just store that over here.
This is largest.
So largest is equal to left child index which is equal to five.
Now we are going to check whether right child index which is six whether six is less than six which
is false.
Right.
So this is not true.
So that means that there is no child over here.
So we don't go inside over here.
Now over here we are going to check whether largest is null now.
Largest is not null right.
Largest.
We have set it to left child index which is five.
So that means we need to make a swap or we cannot break out of the while loop.
So at this point we don't break and we come over here.
And at this point we swap array at index and array at largest.
So we swap these two right.
So we get five over here and we get one over here.
So these are swapped.
And again we said that the ID is equal to largest which is equal to five.
So now ID is equal to five.
All right.
So let's now just clear this up a bit.
So let me just clear this up.
Now at this point we have five over here and we have one over here.
Right.
So five is over here and one is over here.
And we have I'd let me just write that over here ID is equal to five.
This is the index five.
All right.
Now again we come and it's still true right.
So again we come inside the while loop.
So let me just clear this up so that we can see what's happening.
Now we are again inside the while loop, right?
So we come over here and we find that find the left child index two into five plus one which is ten
plus one which is equal to 11.
And then we find the right child index which is 12.
So if this node had children it would have been 11 and 12.
Right.
So six, seven, eight nine, ten and then 11 and 12.
So we are just finding these indexes over here.
And then at this point largest is set to null.
Now we are going to check whether there is a left child after all.
Right.
So left child index which is 11 is not less than length which is six.
Right.
So we don't go inside over here and we do the same thing.
12 is 12 less than six.
No.
So we don't go over here as well.
Now we come over here.
And at this point largest is still null.
So we understand that there is no more child.
So we break out and we have got this structure like this.
So we have five over here and we have one over here.
And yes this element that is index.
Two is been typified, or the element which was over here, which is five, is placed in its correct
position.
All right.
So we have done that for I is equal to two.
Now we go ahead and do that for I is equal to one.
Now how does this look at this point.
Let me just draw it over here.
We have eight.
We have six and we have five over here.
And we have one over here because we swapped them.
Right.
We have five over here.
We have one over here.
And then we have 15 and we have 12 over here.
Now we are going to again call the bubble down function for the element at index one, zero and one.
So this is the element at index one right.
So we are going to call the bubble down function.
Again what will do.
It will again let's see what's happening.
So we have this over here we have six.
So we come again inside we find its children.
And then we are going to check whether the child is greater than the current.
So that's what we're going to check.
So what about 15 and 12.
Yes these two are greater.
So again we will swap.
Right.
So this will become 15 and this will become six.
Now how do we ensure that we take 15 and not 12.
So let's see that over here.
We will see that in this case let me just bring this.
So we have 615 and 12.
All right.
So let me just write that over here.
So we have six, 15 and 12.
Now when we come to this part of the code.
We have found the children.
Everything is the same thing, right?
So once we reach over here, we will see that the left child, which is 15, is greater than current.
So yes, largest is set to this index over here.
All right.
Now we come over here and we see 12.
And we know that 12 is larger than six.
But over here we are going to check whether largest is equal to null.
No that is not true.
Right.
Because we have set largest to this index over here which is three.
Right.
So this is three now over here we have mentioned that right.
So this is index three.
Now largest is not null.
So then we are going to check whether right child is greater than left child.
So 12 is the right child is 12 greater than 15.
No.
So we don't go inside.
We don't go over here right.
We don't go over here.
And largest is still equal to this.
That is the left child index.
And then we are going to just swap these two over here.
That is right.
Index is right.
Largest and over here largest is left child index.
And then right largest which is the left child index is equal to current.
So these two are getting swapped.
So we get six over here and we get 15 over here.
And then there is no more child.
So we will break out because largest will still be null.
So let me just write that over here.
So we have 15 over here and six over here.
Now we will again call the bubble down function for the zeroth index, which is this element over here.
Now what about eight, 15 and five?
Are they in the right position?
No, right 15 is greater than eight.
So again we will swap these two values.
We will see that this over here is not greater than this value.
So we are only dealing with this value.
So we swap these two.
So we get eight over here and we get 15 over here right.
Now what about eight six and 12.
Is this in the correct position.
So let's see whether this is larger than its children.
So it's not the case right.
12 is larger than eight.
So again we will have to swap.
So we'll get 12 over here.
And we will get eight over here.
And that gives us the uh binary max binary heap.
Right.
So the array now will look like this.
We have 15, then we have 12 over here we have five over here we have six over here and we have eight
over here.
And yes, there is one over here.
Right.
So this is the array.
Now if we are just going to write it out let me just clear this space.
So this array will look like this.
We have 15, 12, five, six, eight and one which is a max binary heap.
So we have discussed the build heap function which we have written.
And we have walked through the bubble down function which we have written.
Now let's quickly take a look at the extract max function.
Now over here.
What how does it works.
Let's say we call the extract max function.
So we say const maximum value is this dot heap at the zeroth index which is 98.
Right.
So at this point maximum value is equal to 98.
So let's do it with this sample max binary heap which I have over here.
Now we say last is equal to this dot heap dot pop.
Right.
This is stored as an array.
So the array will look like this 98 then 5782.
And then we have 44 1175 and 22.
So we are going to pop out the last element which is this one over here.
Right.
So last is 22.
Right.
And then we are checking whether there are still elements in the heap array.
Once we have taken this out, which is yes which is the case.
So we say this dot heap at zero is equal to last.
So over here we make the value as the last which is 22.
Now visually we can see that over here we have just taken this out.
So this is no longer there.
And then over here we put the value 22.
So that is what we have done.
Now afterwards we will call the bubble down function for this uh, which the same function which we
have written already, which we have discussed.
So we are passing the array and we are passing this as the index which is zero.
So again what happens.
Let's quickly see.
We come over here.
Let me just clear this up.
So we have called the bubble down function and the array has been passed.
And the index which is given is zero.
All right.
So this is the old example.
We are dealing with the new one.
So let me just write that over here.
We had 98 then 57 then 82 over here and 44 and 11 and 75 and 22.
So that's how it was looking.
The example which we were just dealing and we popped this out and we put it over here.
Right.
So we have 22 over here.
Now we are calling the bubble down function.
Now what happens again we find the length.
So at this point the length is 12345 and six.
So we have the length over here as well.
Six is also six and the current value is 22.
So this is 22.
Now we are going to find its children right.
So by this part.
So we find that one and two are its children because this is zero right.
So zero plus one is one and zero plus two is two.
So we find its children.
And then over here we are going to check whether the child is greater than current.
So is 57 greater than 22.
Yes.
So largest is equal to at this point left child index which is equal to one.
Again we are going to check whether 82 over here we are seeing that largest is not null because we changed
largest at this point.
Now we are going to compare 82 and 57 right?
Right.
Child 82 is greater than left child which is 57.
So we are changing largest to two right.
So largest now is equal to two.
And now we are going to swap these 282 and 22.
So over here we get 82.
And over here we get 22.
All right.
So again we come back to the while loop.
And again we loop.
So for this node now we find its children right.
So this is uh one two.
Then we have 345 and six.
So over here we'll get five and six.
And from this formula we will also get that right because over here it's two.
So two into two is four.
Four plus one is five.
Again two into two is four four plus two is six.
So that's how we get five and six over here.
Now let me just make some thing clean.
So let's just clean this up a little bit so it's legible.
So at this point we have 82 over here.
So let's delete everything else.
So I have 82 over here.
And I have 22 over here.
So again let's clean this up as well.
And there is nothing over here.
So this is how it looks at this point.
Now we found that its children are five and six.
Now we find that yes there is a left child.
And when we check this part right child less than length which is six is not less than six.
So we don't come over here.
Right.
So there is no right child.
Now when it comes to the left child, we find that the left child is 75 over here.
And then we are comparing 75 and 22.
And we see that yes a swap is required.
So largest is set to this index over here which is zero.
Uh this is uh five right.
So this is index five.
So we set that to index five.
And over here we swap these two.
Right.
Right index is right largest and largest is left child index.
So we swap them so we get 75 over here.
And we get 22 over here at this point.
Now let me just clean this up.
So we have 75 over here.
We have 22 over here.
And again we come to the while loop over here.
Right.
So we are back again over here.
Now we calculate its possible children's indices.
Right.
So this is, uh.
What what was this?
This was five.
So five into two is ten.
Ten plus one is 11 and ten plus two is 12.
So 11 and 12 are the possible indexes of its children.
And again over here we have we will check whether 11 is less than six which is wrong.
So we don't come over here.
Over here we will check whether 12 is less than six which is again a no.
So we come over here and largest is still null.
So we break out.
So at this point we were able to extract the maximum.
And then we ensured that the remaining elements follow the max heap property.
So this is how the extract max function works.
Let's look at the insert and the peek function which are the two remaining functions over here.
First we look at the insert function.
Let's say we want to insert the value 25.
All right so I have a node with value 25.
And let's say we want to insert it.
So how does it work.
Let's take a look at it.
So always we will insert at the end.
Now this is stored as an array right.
So this will look like this 98.
Then we have 5782.
Then we have 44 1175 and 22.
And we push 25 to this array.
So we have 25 over here.
Right.
So we have 25 over here.
Now visually you can see that we are just inserting it over here.
So this is 25 at this point.
Now what we do is we will bubble up.
We will call the bubble up function.
And we are over here.
Now we say ID is equal to this dot heap dot length minus one.
So the length at this point is 3456788 minus one is seven.
Right.
So the length the id at this point is equal to seven.
Now what about value.
Value is equal to this dot heap at id.
So let's look at the value which is the latest one.
Right.
So this is 01234567.
So that's why we calculated this.
So we are just taking the last value and putting it over here.
So value is equal to 25.
All right.
Now we are going to loop as long as ID is greater than or equal to zero, or we are going to bubble
up right.
So we can stop if we reach the ID as zero because there's nothing more to go up.
Right.
So either one condition to break out of this while loop is if ID is equal to zero, or if ID is no longer
greater than zero, we break out.
Now we also have a break condition over here.
Let's discuss that now.
Once we are inside this loop, what we do is we find its parent right?
So its parent.
Now at this point the index is seven.
We know that we can find the parent by doing math dot floor seven minus one by two.
Right.
So seven minus two seven minus one is six six by two is three.
So 0123.
So this is three.
So yes we get that the no the value at index three is its parent which is 44.
Right.
So we find the parent value as 44.
Now we are going to compare these two.
If it was the case that the value is less than the parent value which is the case over here.
Right.
So 25 is actually less than 44.
In this case we can break out.
So we are sure that it's in the correct position.
So in this case we would break out.
Now let's say we were inserting a value like something greater than 44 like for example 50.
In that case we would have swapped these two values over here.
All right.
So that is how the insert function works.
Now once we swap let's say we were inserting um 60 for example.
All right.
So let's say we were inserting 60.
So this is 60 and this is 60.
And this is also 60.
So over here we are comparing 60 and 44.
We see that they are not following the heap property.
So we swap over here right.
So we say this is 60 and this is 44.
So we have swapped.
Now we set ID is equal to parent ID which is this index over here.
Right.
So that is three.
So we say ID is equal to three.
And again id is still greater than zero.
So we again come into the while loop.
Now let me clean this up a little bit.
All right.
So we are again inside the while loop.
And at this point ID is equal to three.
So we do three minus one by two which is two by two which is equal to one.
So we find that the parent is this element at index one which is 57.
Right.
So yes, we can see visually that it is the correct parent.
Now again we are going to check over here whether this value which is 60, whether it is less than equal
to the parent value.
If that is the case we would have broken right.
We would have broke out and come out.
But it's not the case.
So again in this part we are going to swap these two.
So we get 60 over here and we get 57 over here.
All right.
Again it is set to the parent ID which is equal to one.
So parent is now one.
Again ID is greater than zero.
So we again come inside the while loop.
So let's clean this up.
And again we are over here.
So ID is equal to one.
Now what about the parent index.
So that's one minus one by two which is equal to zero.
Right.
So we get that the parent is this one over here 98.
Now we are going to compare these two values right 98 and 60.
And we see that value is actually less than the parent value 60 is less than 98.
So we break out.
And by this we have successfully inserted the element 60.
And it's at the correct position.
So that this is actually a binary heap a max binary heap.
So this is how the insert function works.
And finally let's look at the peak function.
So let me just clear this up.
All right.
So we are just going to return the first value in the array.
So we are going to store this as an array as we discussed.
So this will be 9857.
Again I'm coming to this example only 57 8244 1175 and 22.
So this is the array.
Now in the peak function we just want to know what is there over here.
Right.
We don't want to remove it.
We just want to see it.
So we will just return this dot heap at index zero which is this value over here.
So we will just return 98 over here.
And that is our peak function.
Now let's quickly look at the complexities over here.
You can see that all of these functions run in constant space right.
We have implemented it in an iterative manner.
So again the peak function runs in O of one time and space.
We are just returning this value right.
What about the insert function.
The insert function runs in.
O of log n time complexity.
Right?
So time is equal to O of log n.
And again it's the maximum number of comparisons which are required.
So again the binary heap can never be one sided.
So this is going to be the best worst and average case.
So the time complexity is O of log in.
And log log n is the maximum depth or the height of the tree.
And again the time complexity of the bubble up function is also O of log n space.
Complexity of these is O of one right space is O of one space.
Over here is also O of one.
Now what about the bubble down function?
This one also has a time complexity of O of log n, right?
Again it's it depends on the number of comparisons which are required.
And again then that will depend on the height of the tree or which is the maximum depth right which
is log n.
So over here also the time complexity is O of log n space complexity is O of one.
Now what about the build heap function?
We have discussed the proof right?
Even though you may feel that it should be n log n, the time complexity actually is equal to o of n,
and the space complexity is equal to O of one.