Welcome back.
Let's now go ahead and construct the max binary heap, which we discussed in the previous video.
For this we will need to write a class and let's call it max binary heap itself.
And inside this we have our constructor.
And we are not passing anything to the constructor.
All right.
And over here we just say this dot heap is an empty array.
Now we could implement the max binary heap using a node class, etc. like we did the binary search tree.
But over here we are going to implement it as an array.
Now over here we need to write the functions.
Now as per the question.
We need to have a build heap function which will take in an array.
And this function over here will rearrange the positions of the elements of the array such that the
array follows the max heap property.
That's what we are going to do over here.
Now let's get started.
Let's have a variable called length.
And let that be the length of the array which is passed to the function.
All right.
And let's also have another variable last parent right.
So let last parent is equal to.
And remember the range of the internal nodes is zero to floor of n by two minus one.
So floor of n by two minus one will be the last parent right.
So that's not a leaf.
So it's a parent right.
So let's say let's find the index of that.
So that will be math dot floor.
And then we have already here length which is the length of the array.
So we just need to divide that by two length divided by two.
And then you have to subtract one from it.
So this will be the last parents index.
All right.
Now as we discussed in the previous video we have to call the Heapify function bottom up right.
So it will start from this index till zero.
So for this we will have a for loop.
Now let's code that.
For let I is equal to last parent.
And then this has to keep happening till I greater than or equal to zero and I minus minus.
All right.
Now for each of these indexes what we have to do is we have to just heapify it.
Right.
So for this we will have to write a function.
So we call it bubble down.
All right.
So this dot bubble down.
And then over here we will pass the array and then we will pass this particular index which is I.
All right.
So that's that's the end.
Right.
So by this time the array will be rearranged such that it follows the max heap property.
And then we just have to set this over here which is an empty array to the array at this point.
Right.
So we are doing it in place.
So over here we can just say this dot heap.
Is equal to the array.
And then we will just return this, right?
We can just return.
This.
So that's just optional.
So over here we are just returning this so that when we call this function we can see the output.
All right.
Now we need to write this function.
Let's continue.
So this will be a function again we will write it over here.
Let's have it bubble down.
Now this is just the Heapify algorithm, right?
So this has to just heapify that particular index.
So again it receives an array.
So let's write that over here.
And an index.
Let's call the index ID.
Now what does it do.
Let's again think about it.
We have to bubble down right.
So it has we have to find its child two children.
We have to look at the greater child.
And then if the greater child is greater than that particular element at that index, then we have to
swap.
And we have to keep doing that until, uh, the element is greater than its children, which is the
max heap property.
So let's do that.
So over here again let me have a variable const length is equal to array dot length which is the length
of the array.
And let's say the current element is array at I.
So again I say const current is equal to.
Array at ID.
Which is the index.
And again we are passing this over here.
Right.
So we are passing that index over here.
So at this instance of the bubble down function we are just dealing with this element.
So that's why I've made it a const.
All right.
Now we keep looping.
So let's say while true and we will have some condition to break out of it.
So we'll discuss that.
Now what do we do.
We have to find its children right.
So let's say let left child.
ID is equal to two into id plus one, and the right child index will be two into id plus two.
Right.
So let's do that.
Let write.
Child ID is equal to two into id x plus two.
All right.
So we have found the children.
Now again let's have two variables to hold the value.
Let left child and right child.
Again we're not directly doing it because it may be a case that there is no child.
Right.
So it may be out of bound or it this index may turn out to be greater than the length.
Right.
So then in that case we will not be able to find this left child.
So over here I'm just creating the variables left child and right child.
Now, before we assign the value, we will check whether the index is within the range.
All right.
And finally we will also need another variable to see whether we need to continue or whether we can
come out right.
Now we can come out if the children are lesser than in this case, the current element.
Right.
Are I at ID?
If the children of this are less than this, then we can come out right.
So we will need to keep track of that.
So for this let's have largest.
Initially it will be null.
Now in case the children are less than the current element then we will keep it null and we'll just
check null.
And if it's null we will come out of the while loop.
Now if it's not null, we'll identify with which among these two children we should swap this element.
So we will use this for that for tracking that index.
All right.
Now let's continue.
Now let's say if the left child index.
So we are going to see whether the left child and right child are there or not.
So for this we will just say left child index.
If it is less than the length right.
So if it's less than the length so it's within the bounds.
So in this case we can say left child is equal to we can say left child is equal to array.
At left child index.
Right.
So this is just to ensure that this is actually a valid child.
So we are just checking whether it's within the length.
And if it's so then we are finding left child is equal to array at left child dot index if left child
index.
All right.
So we have found the left child.
Now we have to check whether we have to change this or not like largest.
So we are going to use this to track whether we need to swap anything or not.
Now for this let's check whether the left child is actually bigger than the uh, the current element.
So we'll do it inside over here only.
So if left child, if it is larger than the current element, what do we do in this case?
In this case we say that largest is equal to left child index.
So that means that we have to swap it with the left child index.
But hold on, we have not yet checked the right child.
Now let's do the same thing for the right child.
So if.
Right child index is less than length.
So there is a right child.
All right.
So we say right child is equal to array at.
Right child index.
So we have found the right child.
Now we have to see whether we need to change the value of the largest.
So what are the possibilities.
Right.
So there is a possibility that largest is still null.
Or there is a possibility that largest is equal to the left child index.
So let's check that.
So let me write the condition.
So if.
I'm saying largest.
Is equal to null, right?
So that means that left child is not greater than current.
So if this is the case then if we want to swap, at least the right child should be greater than the
current.
Right.
So we say and right child greater than current.
All right.
So if this is the case then we need to swap.
Our largest should be the right child index.
Now this is one possibility.
Or what is the other possibility.
The other possibility is that.
Largest is not null.
Right?
So again earlier I discussed there are two possibilities.
Largest can be null or largest is not null.
So over here we have dealt with the case where largest is is null.
Now what if largest is not null.
So let let's write that over here.
If largest is not null and if right child is greater than left child right.
So again what is this over here?
Largest is not null means the child.
The previous child over here is actually greater than the current.
Right.
So this if only if left child is greater than current largest is equal to left child index.
So only in this case largest is not equal to null.
So we know that the left child is greater than the current element.
Now already we have stored the left child index as largest.
We are.
We are seeing whether we need to change this to the right child index for this.
If this is the case, then right child has to be greater than left child.
If this is true, then if any of these is true right?
So this is an or operator.
So if any of these is true.
So let me just have brackets over here so that this is one if condition.
So if any of these is true then we have to set largest to right child index.
All right.
So what is it that we have done over here?
In this part, we are checking whether there is a left child.
If there is a left child, we are checking whether the left child is greater than the current which
is the array at ID, right.
So we have set current is equal to array ID.
So if there is a left child we are checking whether that child is greater than the current element.
If so we are setting largest to left child index.
Now we over here we are checking whether we need to change the largest to right child index.
Again remember we have to swap the current element with the larger one among the two children, right?
The two children may be both of them are greater than the current.
In that case, we have to swap it with the larger one and maybe only one of them.
So maybe the left child is smaller than the right child then the current element.
So in this case it will it will be still largest will still be null over here.
And then we come over here and we see largest is still null.
And then if the right child is greater than current we need to swap.
All right.
So we are setting largest is equal to right child ID over here.
All right.
Now now once we are done with this all we need to do is we need to check whether largest is still null
or not.
So let's write that if largest is equal to null right.
So that means both the children are less than the current element.
And in this case we can just break right.
So we can just break and come out.
So let me just write it in a succinct manner so I can just write it over here.
So if largest is null then we can just break.
Right.
So there's no more swaps to be done.
We come out.
Now if that is not the case then we have to swap, right?
So if that's not the case we will swap.
So we have to swap array at ID and the array at the largest right.
Whether it's the smaller left child or the larger uh right side child, any of the it can be either
the left child or the right child.
So we say array at largest and then we say array at largest.
Is equal to.
Current because we have stored that already over here.
Right?
We have stored current over here, which is R-rated.
So that's why we did not use any other variable over here for swapping.
So R-rated is equal to array at largest and array largest is equal to current.
So we are swapping.
Now the last thing is we just need to set ID is equal to largest.
All right.
Because we have to go down.
Right.
So this is the bubble down function.
So let's say we did a swap.
Remember we have discussed that again the in the new position we have to check that element and its
children whether further swaps are required or not.
So that's why we have the while loop over here.
So this will keep continuing until the situation is such that largest is still null, which means that
both the children are less than the current element.
In that case, the element is at its right position, right?
So we are done.
And, uh, let's test our code.
All right.
So.
Let's just do that over here.
So we have the max binary heap.
So let's create an object of this class right.
So let's say um let heap is equal to new.
Max binary heap.
All right.
Now we will just call the build heap function heap dot build heap.
And we have to pass in an array.
Right.
So that's how we do it.
So let's pass in an array.
So let's say we have the same array for.
Seven.
309326, the same one which we used in the concept video.
Now let's call, let's run it and see what's happening.
All right.
So we have.
The heap object over here, and it has eight elements.
And we see it's 97364320 which is correct.
Right.
So we have used the same example which we used in the uh explanation video.
So we use the same array.
And you can see that the elements now follow the max heap property.
So our build heap function is working.
Now let's proceed and go ahead and write the next function which is extract Max.
Let's start with uh extract max because it's very much similar to the build heap because over there
also we'll have this Heapify algorithm used.
Right.
So we will use bubble down there also when we remove.
So let's go ahead and write that.
So this is the bubble down function.
So below that let's write extract max.
All right?
And we don't need to pass anything.
We are just extracting the maximum value.
All right, so let's get started.
Now we have a variable let's say maximum value because this is a max binary heap.
So when we extract the first element from the array we will get the maximum value.
So this will be equal to this dot heap and the element at zeroth index right in this array.
So that would be the maximum value.
Now let's go ahead and complete this.
So we also need to pop or take out the last element from that array.
Right.
So let's say const last is equal to this dot heap.
Dot pop.
Right.
So we get the last element out.
Now we need to check whether the heap is now empty or not.
Right.
Because we are now going to reinsert that element in its right position.
That's what we're doing, right.
We are taking this value out and we will place it in the first value, and then we will bubble it down
to its correct position.
So that's what we are.
That is what we are going to do.
Right.
But we need to do that only if the heap is not empty, if this is the last element, if we just took
out the last element, if there was just one element, let's say the array was looking something like
this, it just had one element.
Let's say this is our max binary heap.
In this case, if we just take out the ten it should be empty, right?
We don't need to insert it back.
So we need to insert it back only if the length of the array at this point is greater than zero.
So let's put that check over here.
If this dot heap.
Dot length greater than zero.
Now, if this is the case, then we have to put it back.
And then we have to bubble down to its correct position.
Right.
So we say this dot heap at index zero that would be equal to last right.
So this value over here the last value is taken and put into the first value.
Now we just have to bubble down right.
So we say this dot bubble down or heapify.
And in this case we pass the whole heap which is an array.
Right.
So array and then the index is zero.
Now we are using the same function bubble down which we wrote over here as well.
Right.
For the build heap uh function over here also we were bubbling down on each element over here.
The parameters are array and index.
Now when we call bubble down over here we pass in the heap this dot heap.
And the index is zero right.
So we are going to uh heapify.
Or we are going to put the element in the zeroth index in the correct place.
Because over here we have inserted the last element in the zeroth index.
All right.
So that is it.
So this should work.
Now at the end let's just return the maximum value.
All right.
So let's just return that.
Return maximum value and that's that.
So we are done with our extract max function.
Now let's check it.
Now, over here, we have our heap.
Let's just, uh, run this.
And.
If we look at our heap, we can see.
These are the elements over here.
97364320.
Now let's call heap dot.
Extract Max.
And we get the maximum value, which is nine.
Now if you call this again, we get seven, which is the second largest value.
If we call this again we get six, which is the third largest value right now.
If you do this again we should get four because that's the next largest value.
Then we get three.
Then again we get three.
Right now we are just left with two and zero right.
So we should get two.
Then we should get zero.
And then when we do this we get undefined because we have put this condition over here that we insert
it back only if this dot heap dot length is greater than zero.
Right.
So if we are removing the last element like for example this case, then we don't put it back.
We just return that and that's that.
So the heap is empty at that point.
So we are done with this function also.
Now let's proceed and write the insert function.
So let's write it over here.
Now in this case we have to pass a value.
So insert and then we pass a value.
Oops.
Insert value.
All right.
Now what we do is.
We push this value to the array.
Right.
So it's just an array right.
So we first we say this dot heap dot push and then we push this value right.
And so it's inserted at the end of the array.
Now we need to bubble it up to its correct position.
So we need to write another function.
So let's call it bubble up.
Right.
So this dot bubble up and that's it.
So always we will bubble up at the the last element.
So I'm not passing anything over here.
And at the end of this we can just return the heap.
So return this.
All right.
So now let's go ahead and write the bubble up function.
So let's write it over here.
Bubble up.
It has not taken any parameter.
Now let's do this.
So the index of the last element let's find that out.
That would be.
This dot heap which is an array.
So we can say dot length.
Minus one.
So that would be the last index right.
It will be zero index.
So that's why we are doing minus one.
Now that's the index.
And what's the value.
Let's find the value.
So const value is equal to this dot heap.
And the index will be ID which we have just found out.
All right.
So this is the value.
Now we will bubble up and we'll have a while loop.
Right.
So this will iterate till ID is greater than zero.
So when it when we reach zero we can stop.
All right.
So we are starting at the end.
And then we move till ID is greater than zero.
All right.
Now what we need to do is we need to find this parent.
Right.
So we have the ID over here.
Now we know that we can find the parent by doing math.
Dot floor the ID minus one by two.
Right.
So we have already seen that.
So let's find its parent.
So let's say let parent ID let's call it parent ID.
That's equal to math dot floor.
And then we have an ID right.
So ID minus one by two.
And I'm just adding a back bracket over here so that we have sufficient brackets.
So this will give us the parent index right.
Now let's find the value at the parent index.
All right.
So instead of let I can use const again we are not going to change it.
So let's just write const.
Now let's find the parent value.
Parent value is equal to this dot heap at the index where the parent index right.
So we have just found that index.
All right.
So that's the value.
Now we need to compare this value and this value.
So that's what we are going to do.
And if the value is less than equal to the parent value then we can just break.
Right.
But if it's greater than the parent value then it's not following the max heap property.
And we need to swap them.
So that's what we are going to do.
So if value less than equal to parent value in this case it's in the right position and we can just
break.
But if that is not the case then we need to swap right.
So this dot heap we say parent index is equal to the value.
And we say that this dot heap at IDF.
Is equal to the parent value.
So we have swapped these two.
All right.
And now we just need to set ID is equal to parent ID.
And then again we have to keep doing this as long as we don't break out.
Right.
So if we will break out if the value is in its current position or if ID is not, if this condition
over here, that is ID is greater than zero does not become true.
Now that could happen if ID for example, is equal to zero, right.
So let's say over here we got the parent ID as the root node.
So ID is equal to zero.
And then we don't need to again check it.
Right.
So at this point we just swapped right.
We just swapped the value with the parent index.
Now there's nothing more to go up right.
So at that point we can stop.
So either we break out or if ID is no longer greater than zero we come out of this loop.
So we are done with the bubble up function.
All right.
So yes there's nothing to clean up over here.
So this should work.
Now let's try to insert a value over here.
We will try to insert the value nine.
All right.
So let's just call this we have called our code.
So we have the heap object over here.
Now let's say heap dot insert.
And let's say we give the value 20.
Now 20 is the greatest among these elements, which over here, which we have over here.
So we should see that it's at the root.
Right.
So let's see that.
So we have 20 over here which is correct.
Right.
So this is the same example that we used in the explainer video.
So it's easy to test it out.
So our insert function is also working right now.
Let's quickly do the last function which is the peak function which is pretty straightforward right.
So we just need to return that particular value.
So let's write the peak function.
And this just has to return this dot heap at index zero.
Which is the greatest value.
Right.
So that's it.
Right.
So the peak function is pretty easy.
Now if we say let's again run this.
So we have our heap.
And if I say heap dot peak.
It should give us.
Nine.
Right.
Again, at this point, 20 is not there, right?
Because I've run the code again.
So the heap is starting at nine, which is the largest value.
And when I peek I get back the value nine.
All right.
So we have successfully coded this solution.
We have created our max binary heap.
We have written the build heap function.
And this uses the bubble down function as a helper function.
And then we have returned the extract max function.
This also uses the bubble down function as a helper function.
Then we have written the insert function which uses the bubble up function and we have written peak.
Now let's take a few sample inputs and relook at the code to thoroughly understand it.
And we will also take a quick look at the complexity of the solution.