Hi everyone.
Let's do this question right.
A max heap class that supports the following.
Building a max heap from an input array.
Inserting integers in the heap.
Removing the heaps.
Maximum or root value.
Peeking at the heaps.
Maximum or root value.
The heap is to be represented in the form of an array.
All right.
So this is a basic question.
So these are the four functions that we have to write or methods that we have to write for the class.
Right.
So these are instance methods.
So let's go ahead and understand how we can solve this question.
So we need to write the instance methods to build the heap insert into the heap remove from the heap
and peek at the heap.
All right so let's get started with the first function which is to build the heap.
And remember we are representing the heap as an array.
So in the previous videos we have discussed how we can do that.
So we will be using that over here.
All right.
Now before we go ahead and discuss the method which will be used to build a heap from an input array,
let's discuss the Heapify algorithm.
Because to do this to build the heap from the input array, we will be repeatedly calling the Heapify
algorithm on a set of indices.
So we will discuss that.
So first we will discuss the Heapify algorithm.
So over here I have a binary tree.
All right.
And notice that you have an element seven over here.
Now we know that this element over here does not follow the max heap property.
Right.
So over here you have 21 and 22.
And clearly the children are greater than the parent.
So let's say we want to implement an algorithm to heapify this element over here.
Now if we write the indices we know that seven is at index one.
Right.
So writing the indices means let's convert this into an array.
So I would be writing 95.
Then I have seven then 45.
Then I write 2122, then 30, 35, etc..
Right.
So this is what we have discussed before, right?
So it follows the relationship between the parent and the child with the indices.
So over here you can notice that seven is at index one.
So we are going to write and we are going to discuss an algorithm to heapify the element over here in
this tree at index one.
All right.
So again what is it that we are trying to do.
We are going to change the position of the element seven such that it follows the heap property in this
case the max heap property.
All right.
Now you can do this right.
Again we are trying to heapify the element at index one which is this one over here.
Now there is a prerequisite for us to be able to do this.
The prerequisite is that we can do this only if all the elements in the left and right subtree follow
the heap property.
So let's take a look at this.
So the left and right subtree of seven are these right.
So all the elements over here and here follow the heap property.
For example 21 is greater than 19 and 20 and 22 is greater than 15 and 16.
So because this is satisfied that is why we can heapify the element at index one, which is this one
over here.
So remember this is important.
We can heapify an element at an index only if all the elements in the left and right subtree follow
the heap property.
And it's followed over here.
All right.
So let's proceed and see how we can do this.
So let's clear this now if I want to element if I want to heapify this element over here, what I have
to do is I have to check its children.
So its children are 21 and 22.
Now the bigger among these two is 22.
Right now let me check whether seven is greater than 22.
Is that the case?
No, it's not right.
Seven is actually less than 22.
Or I can say 22 is is greater than seven.
So this does not follow the max heap property.
So in this case we have to swap seven.
And the bigger one among these two which is 22.
So let's swap that.
So 22 comes over here and seven comes over here.
All right.
So we have seven over here at this point.
Now we need to continue this right.
So we we need to continue this.
Let's check its children at this point which is 15 and 16.
So the bigger among these two is 16.
Now over here again you can see 16 is greater than seven.
So it does not follow the max heap property.
Right.
So we have to again swap seven and 16.
So let's do that over here.
We get seven over here and 16 over here.
Now you can see that this is how the tree looks like right.
You have seven over here.
Now it's in the correct position.
Right.
So this is now a max binary heap.
So we have successfully heap defied the element at index one which was this one over here.
So what did we do.
We had the element seven over here.
And we bubbled down or sifted down this element to its correct position so that it follows the heap
property, in this case the max heap property.
So this is what we call the Heapify algorithm.
Now that we have understood this, let's go ahead and come back to the build method which we have to
write.
And remember you can heapify and index only if all the elements in its left and right sub.
Follow the heap property.
So that is something that you have to keep in mind.
We will use this over here as well.
All right.
So let's get back to our build function.
Now for example let's say this is the array which is given to us.
And we have to convert this into a max binary heap.
So let's write the indices of this array.
So zero one up to seven.
All right.
Now if I were to just picturise this as a binary tree it would look like this.
Right.
We have four seven and three are its children.
Then zero nine, three, two and six.
Right.
So four.
Then you have seven and three.
Then you have zero nine and three two.
So that's this level.
And then you have six.
So this is how we would picturise it right now.
Let's proceed.
Now notice that the Leafs over here are 693 and two.
All right.
Now over here there is another interesting thing that you can see.
The leaf nodes always follow the heap property.
Right.
Because it does not have a child.
So you can easily say that the leaf node follows the heap property.
Or it is the greater one among its children and its children are just null, right?
They don't have children.
So the leaf nodes always follow the heap property.
So that's an interesting observation.
Now we just have to heapify the internal nodes.
So again we want to convert this into a max binary heap.
And the leaf nodes are already following the heap property.
So the remaining nodes are the internal nodes.
So we just need to call the Heapify algorithm which we just now discussed on the internal nodes.
All right.
Now there is one more interesting thing that you have to notice over here, which is the order in which
you have to call the Heapify algorithm on the various internal nodes.
Now the order to be followed is this order over here, which is bottom up, which is you have to call
zero first, then you have to call Heapify on three, then on seven and then on four.
Now there is an interesting reason for this.
We have discussed that you can call or you can execute the Heapify algorithm only if all the elements
in the left and right subtree are following the heap property.
Now we have to call the Heapify algorithm in this order, because we can be assured that these, for
example zero over here for for zero, its left and right subtree will follow the heap property, because
we know that leaf nodes are always following the heap property.
So internal nodes near the leaves, right?
So these are the internal nodes near the leaves.
So for them the left and right subtree will follow the heap property because for them the left and right
subtree are just leaves.
So this is the interesting thing you have to notice over here.
And that's the reason that we have to call the Heapify algorithm in this order which is bottom up.
So again remember we have to just call the bubble down function in this order.
So that's the Heapify algorithm which we discussed is nothing but the bubble down or sift down algorithm.
All right.
So let's go ahead and implement that over here.
So this is the current array which we have picturized or visualized.
But it's not stored like this.
It's just stored as an array.
But we know the relationship between the parents and the children.
So now let's call the Heapify algorithm in this order.
First we call it on zero.
So we have zero.
We check its children, which is only six.
Now this does not follow the heap property right.
So we have to swap these two.
So we get six over here and zero over here.
Now we proceed.
Now we come to three.
And we call the Heapify algorithm or the bubble down algorithm on this node over here which is three.
Now we can see that this is already in its correct place, right.
Its children are not greater than this over here.
So it's already in in the correct place.
So we don't do anything and we move forward.
We come to seven right now over here we have seven.
Its two children are six and nine.
The greater among these two is nine.
And that's greater than seven right.
So we have to swap these two.
So let's get nine over here and seven over here.
Now seven is over here.
And it does not have any more children.
So we can stop.
So again now we move forward and we come to four.
Now its children are nine and three.
And you can see that nine is the greater one and nine is greater than four.
Right.
So we swap these two.
So we get nine over here and four over here.
Now four is over here.
At this point again we have to check its children right.
Its children are six and seven.
Now the greater is seven and seven is greater than four.
So again it does not follow the heap property.
So we have to swap four and seven.
So we get seven over here and four over here.
And that's the end.
So by this time four is in the correct place.
So we have called the Heapify algorithm on 037 and four.
Or we have called the bubble down algorithm on 037 and four.
And all the internal nodes are now in their correct position.
Now if we just write this as an array it's 973.
And then you have six, four, three, two and zero.
So this is the output.
So this array over here is now a max binary heap.
So this is how we do the build function.
Right.
So we have discussed this.
So let's just keep this aside.
So this is a valid max.
Binary heap now.
Now let's proceed now with the remove function.
Because over here also we will be using the same bubble down algorithm which we had have used to uh,
execute our build function.
Right.
So we called the bubble down function on many elements.
So the same function will be used over here.
So let's first do the remove and then we come back to insert.
So when you remove an element from a binary heap whether it's a max binary heap or a min binary heap,
we always remove from the root node.
All right.
So in this case we remove nine.
So this is the root node.
And because this is a max binary heap this value will be the greatest value in this whole array.
All right.
Now again that's an interesting thing to notice.
So in the case of a max binary heap the root node will be the maximum value.
And that will be the value that we take out or remove.
And in the case of a min binary heap the root node will be the minimum value.
And that's what we will be taking out.
So we can call this remove function extract max.
Right.
So that's why we can call this extract max.
All right.
Now let's proceed.
So we have discussed that we always remove from the beginning of this array.
Let's go ahead and visualize the array.
So we have 9736432 and zero.
Now we always remove from the beginning right.
So this one over here.
So we will return this value.
If we are we we call the extract max or the remove function.
We return this value over here.
Now after we have returned this value what we will do is we will take the last element which is this
one over here.
And we will put that over here in the root.
Right.
So we take the last element and we put it in the root.
So this is the last element.
So we can just take the last element from the array by popping it out.
And then we set the zeroth element of the array as this element which we just now popped out.
All right.
So this is just returned.
And then we pop this out.
So this is removed right.
And this is placed over here.
So we have zero over here.
Now what we do is let me just write this take this to the side.
And it looks like this now right.
We have removed we have just returned nine.
We have removed this value and we have put it at the zeroth index.
So this is how it looks now.
Now what we will do is we will bubble down.
Right.
So we will bubble down or we will heapify this index.
That is the zeroth index.
We will just bubble down.
All right.
So let's see how that works out.
Now its children are seven and three.
Now what is maximum among these two.
It's seven right.
And seven is greater than zero.
So it does not follow the max heap property.
So we have to swap zero and seven.
So seven comes here and zero is over here.
Now again what are the children of zero.
It's six and four.
And the greater one among these two is six and six is greater than zero.
So it does not follow the max heap property.
So we have to swap zero and six.
So let's do that.
So we get six over here and zero over here.
Now this zero is at its right place.
So now the max binary heap looks like this right.
We have seven six and three are its children.
And then over here we have zero and four and three and two.
So yes this is how it should be.
So we removed the last element, placed it at the root, and then we bubbled it down to its correct
position.
So this is how we extract the maximum value or remove the root node in the case of a max binary heap.
So we are done with the build function and the remove function.
Now let's proceed and look at the insert function.
So we have our max binary heap over here.
And I've just visualized this over here.
Now let's say we want to insert a node with value 20.
Or let's say we want to insert 20 into this max binary heap.
Now what do we do.
We insert at the end.
Right.
We always insert or we push into the array.
We put it over here.
All right.
So after we put it over here we just have to bubble up or sift up to its correct position.
So in the case of build and remove we had a bubble down or sift down function.
Right.
So in the case of insert we need a bubble up or sift up function.
So again adding here let's visualize this.
That means we are adding it over here right.
So let's visualize this.
So 20 is over here now.
Now we need to place this in the correct position such that this follows the max heap property.
So for this we will compare this value and its parent right.
So its parent is six.
So we compare these two.
Now in this case they are not in the right position.
Right.
Because 20 is greater than six.
So we just swap these two.
So let's swap it.
We get 20 over here and six over here.
All right.
So this is how it looks now.
Now again what do we do.
We have 20 over here.
We check this with its parent.
So its parent is seven at this point right.
So we compare them and we see that they are not in the correct position because 20 is greater than seven.
Right.
So again we swap.
So we get seven over here and 20 over here.
All right.
So this is how it looks now.
Now we compare 20 and its parent.
So its parent is nine at this point right.
So again they are not in the right position.
So we swap.
Now we have 20 over here and nine over here.
And we stop.
Right.
So it does not have any more parent.
So we bubble up or sift up until it is in the right position such that the parent is the greater value.
Because over here we are building a max binary heap, right?
So we bubble up until the parent is the maximum value.
Or if it's if we get to the root, then we can stop it because it does not have a parent.
So this is how we insert a value into the max binary heap.
And finally let's look at the peak function.
In the case of the peak function we just have to return the first value.
For example, if this is our binary heap max, binary heap peaking means we are just looking at the
root, right?
So in the case of a max binary heap, we want to know the maximum value.
And in the case of a min binary heap we just want to look at the minimum value without removing it.
So that's it.
So peaking just returns the element at the zeroth index in this array.
Right.
So we are just returning the first value.
So that's the peek function.
So we have successfully discussed how to implement these four functions.
Now let's quickly look at the complexity analysis of our solution.
So quickly.
Let's recap revise what we have just now discussed.
In the case of the build function what we are doing is we are just typifying the internal nodes and
bottom up, right.
So we have discussed that it should be bottom up.
Now in the case of the insert function, what we are doing is we are inserting at the end and then we
are bubbling up that element till it reaches its right position such that the parent is greater than
that particular element.
All right.
Now in the case of the remove function or extract max, in this case, what we are doing is we will
remove from the beginning of the array, and then we will replace it with the last element of the array.
And then we will bubble down that element to its correct position.
And finally in the case of the peak function we discussed, we just returned the first value in the
array.
So that's how we implemented these four functions.
Now let's quickly look at the complexity analysis.
Now in the case of the peak function it's just a it's just returning the value at the zeroth index of
the array.
So that's just an O of one or a constant space and time operation.
All right.
Now in the case of insert and remove the time complexity is O of log n and the space complexity is O
of one.
Right.
So O of log n because it depends on the depth of the tree.
Right.
So that's the maximum number of comparisons we have to make to uh, bubble down or bubble up.
Right.
Because over here we have bubble up and over here we have bubble down.
So that's actually the operation that takes time because initially we are inserting at the end or removing
from the beginning, but then we have to bubble up or bubble down to the correct place.
Right.
So and again log n is the height of the tree or the maximum depth.
We can say the height as the maximum depth right.
So time is equal to O of log n or o of d where d is the maximum depth.
And again remember that's because the number of comparisons is log n and we are doing one comparison
per level.
And again the time is taken up for these two functions, which is bubble up and bubble down.
So the time complexity of the bubble up and bubble down function itself is O of log n.
So we have discussed the space and time complexity of these three functions.
And again the space complexity is one because we are not taking up any extra space.
All right.
Now let's proceed.
Now what about the build function.
Now in the case of the build function we have to do bubble down for these elements over here.
Right.
So we have already discussed that.
So these are the internal nodes.
Now we have seen that for bubbling down one element the time complexity is O of log n.
So it may seem that the time complexity to bubble down almost n elements is o of n log n, but that
is not the case.
The time complexity is actually O of n, and we will see the proof for this in the next video.
And the space complexity is again o of one.