Hello, everyone.
So I hope you all give it a try for writing the removed minimum function.
So now let's discuss how we can write, remove minimum function.
So as discussed in the previous video.
So let us take one example first.
So let's say ten hundred and let's say fifty, two hundred and thirty three hundred and let's say I
have it here.
So this is my minimum.
Now what I want to do.
So basically this remove minimum function, what it will do.
So it will remove my top element.
So again so.
This is my vector, Diana Nyad, then two hundred, three hundred and eighty.
So first step is very, very simple, but they have to do so, you have to have these two elements so
they will come here and then will come here and then you will do Bulbeck.
So slap the.
And then and then you will do Bobic.
So first let us write the code for this one.
So if you will do this then you're complete by property has been certified, but the property he bought
the property is not satisfied.
So first let's write this much amount of code.
So the return type of the function is void.
Remove minimum.
So what this function will do, the first step is very, very simple, what we have to do, we have
to accept the first element and the last element.
So I haven't built by I have inbuilt functions swab so you can skip the first element, which is zero.
And the last element is basically to get this index, we can use site function, so Biggart says minus
one.
Now, after sweeping the elements, but we have to do so, we have to be accurate, Bombeck.
So is this thing correct, what we are doing, we are swapping the first element that we have to remove
with the last element.
So is this thing correct?
So it is not correct?
Why?
It is not correct, because first we have to check whether my priority queue is empty or not.
So basically, you have to copy this so-called.
If there are elements in the to go, then only you can remove the minimum element.
But if there are no elements, so if you are prepared to guzik Chilean president, you will return zero.
So this is an arbitrary function.
Similarly, this is empty function.
So we'll call, so you will call is embassy function.
And if the key is not if the Braddick is not empty, then only you will remove that element.
OK, so let's change the function.
So what we will do, we will also return that element, the element which we are, the element which
we are trying to delete.
We will also return that element.
So before deleting that element stored that element.
So because of zero.
So I'm storing that element in as a variable, then I am deleting that element and then what I will
do, so I will return that element.
So we are doing two things here.
I'm storing that element.
I will return the minimum element and I will also destroy the minimum element.
I will also remove the minimum element from my priority.
You now at this point and what is happening.
So my CBT property has been satisfied, but my mini property, so the keyboarder property is not satisfied.
So what we have to do, we have to do down here if I.
So we have done many examples how we will do down here if I.
So let's understand one more time.
So for doing down here, if the logic is going to be very, very simple, we need three variables sorry
for the variables.
We index left index, right index and one more variable minimum index.
So initially, what is so these are indexes zero, one, two, three and four.
So this does not exist.
So beyond indexes, initially zero this one.
So index is zero left this one right at two.
So left index is one right next to you can use the formula the way plus one.
And here you can use the formula the way Plaistow.
So this is one actually.
And initially, let's say my parent is the minimum element, so minor indexes, zero, then really have
to do so, compare the parent element with the child.
So compare it with hundred.
So it is less than under do nothing.
Now, compare your parent index with the right index, so compare it with 50, so 50 is less.
So what you will do, you will do the slapping part.
So it will come here and 50 will come here.
So what you have to do so you will update your minimum index because index is containing the index of
that element, which is the smallest, so smallest index is now two.
So we will update you index and then we will do we will do the shopping.
So we will set the value value present at the parent index and the value present at the minimum index.
So the value presented parent index was 80, the value presented index was 50.
Now we have said so after this, the next step, but we have to do so.
It is now presented.
So it will compare with its left and right child.
So basically, what is the index of its index of it is actually two and two is the minimum index.
So what will happen to will come here.
So too is my new parent index.
Simple.
So I will initialize my minimum index with I have my index with two.
Now what you have to do to find out is left and right jel index.
So left and right index is actually five and six.
So what you will do, you will compare two with five the value index to the developers index five.
But Index five is actually out of range.
So you will not compare.
And similarly, if the index is out of range, then automatically the right next is also out of range.
So similarly, you will not compare.
You will not compare.
And then what you will do so again, you will write the same code srep the value that the parent index
with the value present at the minimum index.
But here both the index is the same.
So this is also true and this is also true.
So this is my shopping criteria.
This is my stopping.
So if the parent index become equal to the minimum index, that means the parent.
That means the node has been positioned at the right position.
So I will stop.
So at this point, I can stop.
Simple.
So now let's write the.
So far down here, Biffy, first of all, what you have to do, so let us find out the spirit index.
So Birand Index, so what is index?
It is zero simple.
Now, while so suppose you do not know the.
Suppose you don't know the stopping conditions, so let's make it while true.
So this look learned time, and then we will figure out what will have a stopping idea.
So what we have to do, we have to find out our left index.
That will be two times of.
Brent, so let's make it small, because I will do a mistake again.
So this is through times of pain and index plus one, what is my right index?
So right index is two times of being index plus two.
Simple, then what they have to do, you have to take one more variable.
Minimum index, so this minimum index is actually, let's say initially, this is equal to the index,
you can see.
Initially, the minimum indexes, actually the index.
So if this was zero, then initially my band index was also zero.
Similarly, if the band index was too slow, initially my index was also to.
And then what do you have to do so you have to do the comparison part.
You have to find out so you can see what I'm doing.
I have to do this comparison, but I will compare these two values and then I will compare these two
values.
So let's do that.
So if the value presented left index is less than the value presented the parent, less than the value
presented the minimum index, then what they will do?
You will update your main index will be the left index.
And similarly, if the value.
Present presented right next is less than the value president dead, the minimum index, then what he
will do?
You will update your Menom index, but with the right index symbol.
Now, after doing all this, what do you have to do so after reading the index, what we have to do
so we have to do this step in part.
So I'm sweeping the value plays in that index with the value that the minimum index.
So it's representable function.
So I have to scrap the value present at the index with the value present at the minimum index.
Simple.
And then you can see what I'm doing.
So after doing this I am updating my.
So this is for the next iteration.
This is for the next iteration.
So this was my first iteration, so for next iteration, what I have to do, so I have to update the
value of my parents next to be the minimum child index.
So for next iteration, my parent index, it is nothing but the minimum child index.
So the minimum index symbol.
Now, let's take one more example to understand what is going on.
So let's say I have this binary tree, this minimum hip, so 10 hundred, let's said this is equal to
this is 200, this is four hundred.
And let's say this is 18.
And let's say this is 15.
So this is a valid manip now I want to delete the minimum element, so I will call the remote minimum
function and I want to remove them.
So this is index zero.
This is index one.
This is index to index three.
Index for index five and index.
So what I will do, I will set these two values.
So 15 is going to come here then is going to come here and then I will pop.
OK, so I was also starting.
So before swiping.
Before stepping, I was starting my own second variable answer and then I'm returning my answer, so
I will return.
Ben Nonissues So after 15, what is my band.
Index of parental index is zero.
So I am writing here.
So this is my parent index.
This is going to be left index.
This is the index and this is the index.
So index zero.
Left index is one, index is two, and initially my minimum index is actually parent of parent index,
so zero then compare the value presented left index with index.
So index is hundred to compare one hundred with fifteen.
Nothing will happen.
Then compare the RAYCHELLE index with index.
So right index with index of twelve is less than 15.
So what I going to do, I will update my index values or index value is now containing two.
And then in the next lane, we are stepping, so I will step to I will come here and 15 will come here.
Then in the next lane I am updating my spirit index.
So what will happen?
These two will come here.
You can see for index for 2015, new indexes do so.
Now, again, the next iteration will start.
So find out the left index.
So left index is actually five.
Find out the index, which is six.
And initially your index is actually parent index.
Apparently indexes do now again compare so left index or the index or left index is eighteen, so eighteen
is good and fifteen do nothing then.
Right index an index.
Raychelle index is six but six is not a valid index.
So we have to add a Jacare.
So index is not a index so you will not compare.
OK, we will not compare and then there is no need to set because in this web the parent index, in
the minimum index the voters seem so two and two, they both are same.
So what we have to do so we have to do two things.
First thing, we have to add checks.
Rejects, for example, you are comparing the left index or left index should exist, you are comparing
the right index to right Jellinek should exist.
And second, this is messed up in great detail.
You can see 15 is now 15 is present at its correct position.
So you can see the index and the minimum index, the articles when they are equal, that means my bindery,
my heap or their property has been satisfied.
So let's do this.
So first of all, we have two checks.
We have to add checks.
So left index should be a valid index.
So that means it should be listin be good size.
And similarly, the Rachell index should be a valid index index should be listing the accurate size.
And before stepping check, what we will do, we will add a check, so if the appendix is actually.
So if the Menom index is actually the index, so that means.
My hip.
That means my hip or the property has been set aside, so you can do break.
You can go back and this value will be over.
We can write this big statement.
So I think our culture work fine.
So now let us try to test our culture.
So let us first create an object of Depay ridiculous.
Many of the objectives be and let us insert so we have to test insert function, so let us insert some
elements.
Today, elements are 100 percent under 10 to 15, 34 to 17 to 21 and led to 67.
So I am inserting these elements and now let us bring something so suppose I want to print size so that
if the object is B and the function, then the function was Getz's.
And now let us also try to find out the minimum element.
So we don't get the minimum, so it will be done me.
It will be done with the minimum element present in the priority queue and now let's also bring.
Let us also test our removed minimum function.
So while my verdict is not empty.
Well, I bet you guys are pretty what we have to do.
Give me the remove give me the minimum element each time, so I will call remove medium function.
And it will give me the minimum element.
So what is happening here?
So these are the number of elements, so I am inserting hundred, so first hundred welcome.
Then I'm inserting tents or tent will go in the left direction, so Dennis, less than hundreds of zapping
will take place and it will come here and then will come here.
Then I'm adding 15.
So 15.
So 15 is correct.
Now four.
So four will come here again.
You have to do stepping.
So this will become four and 100 will come here, then compare four and ten.
So then we'll come here and four will come here.
Next element is 17 to 17.
Yes, 17 is correct.
17 is basically lower than 10 now 21.
So 21 or yes, 21 is greater than 15.
Correct.
67.
So 67 is good and 15.
Correct.
So what is my hip.
So this is for then.
This is 10, then this is 15, then this is 100, then this is 17.
So this is done doing and this is 67.
So this is my minimum hip.
This is my minimum hip and now what I'm printing, so first time printing gets out.
So how many elements are there?
So seven elements are so output should be seven then.
I'm calling it the minimum function.
So four is the minimum element.
So I will get four then I'm calling while my priority queue is not empty.
I am removing minimum element each time.
So what happened?
So fast food.
Then next time 10 will be printed because it will become the minimum element.
Then 15 is the minimum element, then 17 is implemented, then 21, then 67 and then 100.
So basically these two things will be my output seven, then four.
And then and so I did a method.
So let's try to test our gold.
So what is the added?
OK, so.
See, this record is actually corresponding to this one by loop, so I have to add one more record here.
So you can see so this is so let me run my program again.
So you can see our court is working fine.
So first I am bending my size, so I inserted seven elements that slide.
The output is coming out to be seven.
Then I am printing the minimum elements.
Among these, the minimum element is four.
So let's say four is the output and then what I'm doing.
So while my priority is not to remove one element each time and you can see so in the remove minimum
function, I'm storing that minimum number, I am storing that number, then delete that minimum number
and then I'm returning that minimum number so you can see the output is in mind.
So this is four, then 10, 15, 17, 21, 61 and 100.
So our output is coming out in a sorted of.
Now, if you remember, we have covered starting algorithm's.
So you can see the output is coming out in assorted manner and this thing is actually called Ahepe.
So we have discussed many sorting algorithms like Selection Bubble.
So this is new sorting algorithm, heaps hard.
Now, let us discuss the time complexity for Cheapside, so suppose you are given an elements.
So you are provided with the elements and what do you have to do so you have to sort those end elements?
So we are talking about.
So in salt.
I want to discuss the time in the space complexity.
So he is basically you are given an elements and you have to sort those elements, so the first step
is very simple, what they have to do.
You have to insert those elements into our minimum hip.
So we have created a minimum hip.
If you remember, we have written the code for the medium vertical.
So what I'm doing, I'm inserting those elements into our protocol.
So if you remember the insertion function, so the time complexities log often.
We have discussed it many times and similarly, the deletion function, it is also log often.
So we have discussed it many, many times.
So first of all, we have to insert any elements and for inserting one element of time, complexity,
slogan software, inserting an element of time, complexity will be a login.
Now, after inserting the elements, but we have to do so, we have to remove any elements and for removing
one element time complexities log off and you can see what we are doing.
We have to remove any elements.
And for removing one element, the time complexity is long, often so over time complexity.
So we want to remove an element for removing one element from complexities.
Log.
And so this is the total time complexity and Logan to San Lorenzo, this and Logan to time complexity
for Heap's Art is and Logan.
Now, let us discuss this complexity, so can we say space complexity is big often?
No, we cannot say because you can see what we are doing.
We are creating a vector.
So my complete binary is actually stored in a vector.
So if I have an element where the size of my vector, so first I'm inserting those elements into my
vector so the space complexity will become big often.
So this is basically due to vector.
Now, this was he thought so because we created a minimum priority, so that's why our element was present
in increasing order.
So if we will implement the maximum player dequeue.
Then our elements will come out in descending order so we can start in ascending order and we can also
start in descending order, simple.
And this is the final time and space complexities of time.
And Logan, he saw this taking a long time and the space is actually big and.
Now, in the next few days, we will discuss how we can optimize on space complexity, so I will see
you in the next one by.