Hi, everyone.
We discussed that priority to Kukan, we have two types in one priority queue and I would argue and
we discussed that we will use help to implement our protocol and help us to properties first.
It is a complete minority.
We discussed what is a complete binary in our last video so we know what is a complete planetary.
And the second property was it has something called keep order property.
So just like Vertigo's heap can be of two types.
So first one is minimum hip hip and the second one is Max hip.
And now let's discuss what is a border property, so let's discuss border property, so first let us
consider what is a minimum hyp.
So in minimum, the definition is very simple.
So basically the root value will be less then left value and the root value will be less than the retail
value of everything myself.
So in minimum heap, the heap other properties is the root value will be less than the lovechild value
and the root value will be less than the retail value.
And you can guess in the in the maxim it will just be opposite.
So in the maximum, what will happen.
So the root value will be then left gile value and similarly the root value will be greater than the
original value.
So this is called Mexi property.
Now let's take an example to understand it better.
So this is a complete by Nutri.
This is a complete ministry.
So one thing is very clear.
This is a complete bindery, but it also satisfy he bought the property.
So I am taking example of minimum EHP.
So is this truly a minimum?
So first of all, it is a complete binary take and then it sets the minimum order property.
Many properties or root value one is less than two and three.
So this is a minimum.
This is a valid example of minimum.
Now, is this a minimum?
Yes, it is a by Niddrie and two is basically less than four.
So it is a minimum VEB.
So is it now a minimum?
Yes, it is a complete military and also two is basically less than four and five when it's basically
less than two and three.
So this is the minimum he property.
So that's why this is a valid example of minimum cheap.
So to check for the minimum, we have to check for the two properties first, we have to check whether
the inventory is accompanied by any and then we have to check the heap other the property.
So two properties we have to check.
Now, let's take one more example.
So you have to tell me whether the given tree is a minimum heap or not.
So let's take this example, 10, 20, 40, then 30, 35, and let's say a hundred.
So first tell me whether it is a minimum or not.
So for checking minimum, we have to check two properties.
So first, is it a complete by.
Yes, it is accompanied by an entry and now you have to check minimum property.
That is route value should be left and left and right.
Jalula.
So let's check what Avenal 10 is less than 20 and 40.
Correct.
So 20 is less than 30 and 25 correct.
40 is less than 100.
Correct.
So yes, it is a minimum.
It is a minimum EHP.
Now, if I had an order, for example, I am adding an old.
Tattie, so tell me whether it is a minimum or not, so first let us discuss whether it is accompanied
by military or not.
So, yes, it is accompanied by military.
So this story is a complete binary.
Now let's check for the medium property, so 40 is less than a hundred, but 40 is a good identity.
So this tree is a complete binary, but this tree is not a minimum heap.
Because it doesn't satisfy the minimum property, so this is a valid, complete binary tree, but it
is not a minimum.
Let's take one more example.
That said, thirty sixty, two hundred and one zero one, and let's say I have 41 here.
So again, we have to check for the minimum.
So is this street.
So for minimum, we have to check two properties.
First, the complete banditry.
And secondly, he bought the property.
So first check, is it a complete by nutri?
Yes, it is a by Nutri.
Now, let us check for the minimum he property.
So 10 is less than twenty.
One hundred twenty is less than 30 and 60.
So today is less than 41.
60 doesn't have left or right.
So now let's check for another 200 is less than two hundred and one zero one.
So yes, it is a minimum.
Correct.
Now what is a maximum?
Hipp.
So as discussed, Makhzoumi will be just the opposite of the minimum.
So the root value will be bigger than the left Gyula value.
And obviously it's also bigger than the right child.
Will you let us take an example to understand it better?
So this is a complete binary tree.
This is a complete monitary this is a complete binary tree and this is a computer monitor.
This is a computer binary.
This is a complete binary.
Now, given this tree, you have to check whether it is a maximum heap or not.
So, again, we have to check for two things.
So first, we have to check whether it is a complete binary tree.
Yes, it is a complete binary tree.
Then for them then we have to keep order property.
So basically a root value should be good value and real value.
So 10 is good than five and nine.
Similarly, five is greater than three and one.
And similarly, nine is greater than eight.
So yes, it is a mixed heap.
It is a valid mexi.
Simple, now, if you will add one more node, for example, if you will add 12.
So this is still a complete binary tree, but this is not a max heap because nine is less than 12.
So it violates our Mexi property.
So it is still accompanied by Niddrie, but it is not a maximum heap anymore.
So I hope you understood the definition of minimum and maximum.
Now let's see how we can insert in our heap.
So I want to discuss how we will insert and let us take a minimum heap.
For the maximum help, you can do the opposite.
So let us take the example of minimum hyp.
So let's say I have this story, so 10, then 20 to 40, 60, and it's a 45, 50 and 80.
So first let us check.
So is it a complete buy Niddrie?
Yes, it is a complete Pinetree.
So is it a Minyip?
You can check 10 is less than 20 and 40.
So 20 is less than six hundred.
Sixty is less than 80.
Similarly for these, less than 45 and 50.
So, yes, it is a minimum hyp.
It is a minimum.
Now, let's say I want to insert a number 15.
I want to insert this number 15, so minimum hip is actually acerbity can be bindery, and we know in
a competitive binit there is only one position at which we can insert 15, and that position is basically
this one.
So 15 will be inserted towards the right of 60, so this is the only position available so that this
remains a complete by Nutri.
But if you will insert 50 at this position, then what will happen, this is not a minimum heap anymore
because 60 is not less than 15.
So this is still a CBT, but this is not a minimum help anymore.
So what we have to do, what we will do, so we will compare 15 will be around 60.
Now, what should happen?
We will swap.
So 60 will come here, then 15 will come here.
Now, is it a minimum EP, so 15 is actually less than 20, so this is not this is still not a minimum.
So what we will do, we will step down, 15 or 20 will come here and a 15 will come here now.
So 15 is at its right position.
So compared 10 and 50.
So, yes, 15 is good.
And then so this is now a minimum.
So what is our tree?
So this is our final tree.
Then then 15, then 40.
Then 45, then 50.
Then 20 and then under.
So here I have 60 and here I have 80, so that's how we will in a certain element.
So this is a complete binary tree and this is also a minimum EHP.
So what I did, I want to insert 15, I want to insert 15.
So the only option available is this one, because this is a complete binary.
Now, when you will insert 15 here, our minimum property will get violated.
So what we will do so we will put 15 to it, correct position.
So that's why we will compare 15 to its parent.
Its parent was 60.
That's right.
We will swap.
So 60 will come here and then 15 will come here.
Then when 15 will come here, we will again compare 15 to its parent.
So interesting that it's right.
But, you know, so we will slap again.
So 15 will come here and 20 will come here now.
So now 15 is at correct position.
Yes.
Now 15 is at its conclusion.
So we will stop.
Simple.
Let's take one more example for better understanding.
OK, so let's take this one example only, so what I want to do, I want to insert an element literately
I want to tell you, ELEGANTE So what is the only equation available for me?
So this is the only position in the left hand side of 100, but if it will insert three in the left
hand side, so this is still a complete binary tree, but this is not a minimum heap.
So what we have to do, we will put three to it, the right position.
So compare and so to use less than a hundred.
So we will swap.
So 100 will come here and three will come here.
Now check whether three is added side position No.
15 is greater than three.
So I will swap.
So 15 will come here and three will come here.
Now check is three added.
Right.
You know basically ten is a good entry.
So what we do, we will swap with it.
So three will come here and then will come here.
Now what happened?
Basically, three reaches the top position, topmost position, basically the root position.
So there is nowhere to go.
So I will stop.
And what is Mitry?
So my final Griese, I have three here then I have ten here, then 40.
So this is 45 and 50.
Then I have 20 here, so I have 15 here.
This is it, this is 60 and this is hundred, so this is accompanied by binary and this is also a minimum
help you can check through.
Less than 10 and 40 then is less than Grondin, 15 during these less than 1860, 15 is less than hundred
for these, less than four to even 50.
So it is a complete binary.
It is a minimum also.
So that's how we will insert.
So if you will see in the worst case.
But the complexity of the insert function, the worst case, so you can see.
So he was present here now to use present at the topmost position, so how much of what we do, how
much swearing we do?
So this is high tech.
So we have to do something each times, maximum at times, and what is inside.
So instead will take off each time big of each time.
And we know in a complete binary at just nothing.
I did and I think it is just logon.
So it is login.
So insert function will always take a longer time.
In the worst case, also hide in a complete binary tree, it is fixed, it is always log often and we
have to do something maximum number of times.
So that's why the time complexity for insertion is log often now what we did here.
So basically three go from down to up.
So this process is also called up ifI.
So three go from the bottom to the top masterbation, so we call this process up here Biffy and this
is the time complexity for In Session.
Now let us see how we can delete a node from a minimum.
We know how to insert.
Now let's see how we can delete.
So deleting a node in a minimum heap for maximum help, you can do it yourself.
We just have to ensure that it satisfies the maximum property.
So let us take an example.
So let's say I have this example.
Then then let's say 20, 30, 40, and let's say 100.
OK, so suppose I want to delete 10, I want to delete 10.
So the system so I want to delete the top most position, the topmost element.
But I told you so.
Minimum is actually a CBT and it can be divided.
We can also we can only delete the last element.
So I want to delete then but we can only delete hundred.
I'm repeating myself, I want to delete then.
But since it is a complete binary, so the only element that I can delete is actually handed.
So how we will delete and you can guess what we will do.
We will swap.
So it will come here and then will come here.
We will basically swap the element that we have to delete with the element that can be deleted.
So then we come here.
Then what we will do, we will delete this element.
So let us delete this element.
Now, after reading this element, this tree is still a complete by nutri, but this tree is not a minimum.
So what we have to do, we will put a hundred bolts right position, will put a little side position.
So what we'll do, we will compare words with its left and right child.
So 100 is good then 20 and 30.
But among turned down today is the smallest element.
So I will slap a hundred with 20.
So 20 will come here and 100 will come here.
Now it is handed is added sideways you know, so I will come back handed with its left child.
So right child doesn't exist anymore.
So 40 is less than a net.
So I will, I will swap again.
So hundred will come here and forty will come here.
So what will be my final three.
So I have 20 then I have 40 here, I have 30 here and I have 100 here.
So this is my completely.
So let us take one more example.
Of the a minimum.
So let's take this example.
I have one then let's say I have 10 and 15 and let's say I have 18, then 20, and then let's say I
have 30 here.
So let's make it 80.
So this is an example of a minimum hyp.
Minimum, he or we can say minimum prior, dequeue they both him.
Now, if you remember, in the immediate priority queue, I will get the element, I will get the element
first, which has the minimum priority.
So if you can see, for example, I want to get the minimum element.
So what is the minimum element in the minimum?
So topmost element is the minimum element.
So I can get minimum element in constant time.
I just have to return the root element.
So if you remember what is a proper minimum, so raw data will be less then left Giulietta and raw data
will be less than the Retaliator.
So that means in the minimum keep, the minimum element will be present at the topmost position.
That is, the root element is going to be the minimum element and in the maximum keep, the maximum
element will be present at the topmost position.
That is the root position.
Now, if you remember in the minimum protocol, I have one more function and the name of the function
is actually remove minimum.
So remove minimum.
What it will do, it will remove the minimum element.
So what I want to do, I want to remove element one.
So this is the minimum element and I want to remove the minimum element.
But what we can do, we can only remove the last element because it's a complete binary.
So Minyip or you can say prior to Q So since it is a complete binary, so I can only remove the last
element and the last element is 80.
So I have this function, this function wants to remove one, but I can only remove it.
So we will follow the approach that we discussed above.
So we will step one entity.
So it will come here and one will come here.
Then what we will do, we will delete the last element.
So we will delete this element.
Now we will check.
So this is still accompanied by Nutri, but this is not a minimum heap anymore.
So for minimum, he property will be satisfied.
We will compare it with its left and right children.
So it is a good 10 and 15 vote.
And among 10, 15, 10 is the smaller one.
So I will slap penalties entity.
So it will come here now again.
So it is a stronger then 18 and 20, but it is the smaller one.
So I will strap it in and 80.
So what will be my final three.
So the suspense then.
I have 18.
I have 15 here.
I have a here and I have 20 here now again, so this is a complete by Nutri.
Yes.
So is it a minimum?
Yes, Ben is less than 18 and 15 and 18 is less than 18, 20 at the end 20.
So now check again, if you will, get if you call the function, get a minimum.
So, again, the minimum element is Element and Dennis Besant at the topmost position.
Simple.
Now, if you want to remove the minimum element again, you will do the same thing.
You will strap 10 and 20.
So again, 20 will come here.
Then 10 will come here.
Then you will check 20 and they will do the last element.
Then you will check 20 with left and right.
So 15 is the smaller one.
So you'll step during David 15.
So 20 will come here and it will stop.
So finally I have 15, then I have 18.
So here I have 20 and here I have 80.
So again, check the minimum element is always present at the top position.
Simple.
Now what we did.
So what would be the time complexity for the deletion.
How much time it will take so you can see, for example, it was here with the last element, with the
first element, so it will be it is going to be present here.
And then what we are doing, we are going to lock down and it will present at the last position.
So in the worst case, last level, basically.
So in the worst case, what will happen?
I will do the stabbing at a number of times higher times.
So deletion function takes big off height and we know in a complete binary height is always logoff often.
So that's why the deletion function time complexity is long often.
And one more thing, this process, what we are doing, we are going from top to down.
So this process is called down heap biffy.
This is called Down Deep ifI.
So now let's discuss what are the time complexities for insertion deletion and get the minimum element.
So again, in session we are doing up so maximum number of times it will be the setting will take off
each time.
And that is always a log often because in a complete binary tree, height is always log, often similarly
interpolation.
Again, the maximum that we have to perform will be the Gulf edge.
So it will again be big off log in time.
And let's say you are discussing about minimum.
So in the minimum there's are function, get the minimum function and we just have to return the root
element.
So this is constant and here deletion is actually remove minimum.
Remove the minimum.
So what we will do?
Let's take one more example, and this time we will construct our Minyip.
So I want to construct them in hip and elements will come one Vivan elements will come one by one.
Let's say I have an element then.
So this is my minimum hip then.
Now let's say I have an element five so five can be inserted only at the leftmost position due to the
complete binary tree now.
Is it a minimum?
No, it is not.
So then in five they will be swabbed.
Simple.
Now let's insert one more element.
Let's say my element is 18, so 18 can be only inserted at the right position.
Now, is it a minimum?
Yes, it is a minimum.
So do not do anything.
Now, let's insert one more element, let's say I want to insert 20 so 20 can be inserted on the left
hand side.
So is it a minimum?
Yes.
Let's insert one more element to it.
Or two can be inserted only at this position.
Now, is it a minimum?
No, this is not a minimum.
So what will happen?
I will say up to 110.
So two will come here then.
Will come in.
Now, Jack is to decide which handle.
So I will separate again or two will come here and five will come here.
Now, I want to insert one more element, let's say I want to insert three.
So the only option available to me is basically the left hand side of 18 again.
So it's three at the side.
So what?
We will do something.
So it will come here and three will come here.
So finally, what does Mitry.
So I have to here then I have five.
Three, and then this is 20, this is 10 and this is 18, so this is my final three for these elements.
Now you can check, so the stories are complete by Niddrie industries also minimum.
So, too, is less than five three five is less than 20 and 10 and three is less than 18.
So this is a minimum.
Now, let's perform the also.
So, for example, if you want to get the minimum element.
So what is the minimum elements or top motivation is the minimum element.
So I can return to.
You can see in these elements who is the smallest, so I'm getting the minimum element, I'm able to
find out the minimum element in Question Time.
Now, let's say I want to call the function remove minimum delete minimum element, so which element
we have to delete, I have to delete the topmost element.
And for the deletion of the topmost element, what we can do, we can only delete the last element that
is 18.
So again, we will do the same thing.
I will Sep 2010.
So, too, will come here and then what do we do with this element?
Now, is there an inside position?
No.
So it is greater than five and three, but among five entry three is the smaller one, so I will separate
three.
So it will come here and three will come here and now I will stop.
So what is my three?
Three, then I have five, then I have 18.
So this is 20.
And the system now again, this is a complete binary and this is also a minimum heap.
So you can also check again what is the minimum element to use the minimum element after the two element
of the element is removed.
So that is how it is working.
Now, let's say I again want to call this function reward minimum so this function will remove the topmost
element.
So three will be separated then.
So three will come here and then will come here.
So again, then I will delete elementary now which then is added eight points or ten is greater than
five.
So I will trap.
So 10 will come here and five will come here.
Now ten is less than 20.
So this is correct.
So what is my finally five.
Then 10.
Then 18.
And grunty.
So this is a complete binary tree and this is also a minimum.
You can check five years, less than 10 and 18 and then is less than 20.
And if you want to call, get the minimum function so you can return the topmost element in question
time.
So that is how minimum heap is looking for maximum.
We will do just the opposite.
So I'm giving you a break discussion and we will discuss the solution, the next video.
So this is you will do this question yourself.
So what you have to do, you have to construct a minimum heap, just like we did above, and the elements
will come one by one.
So let's say my first element is, well, then element the element five, then let's say hundred, then
one, then let's say nine, then let's say zero and then let's say 14.
So what do you have to do?
You have to create a minimum heap and after creating minimum heap, you have to remove minimum function
two times.
So after getting the minimum, you will call remove minimum function two times, twice.
So basically you have to do down here, Biffy.
So this discussion and we will discuss the solution in the next video, so I will see you in the next
one.
Bye bye.