Hello, everyone, so in the last video, we discussed the algorithm for implementing in place observed,
and I told you guys to just give it a shot, try to write the code yourself.
So what is the time, complexities or the time?
Complexity is actually in Logan and the space complexity.
So as the name suggests in place.
So the meaning of in place is that it will actually constrain time so that space is going to be big
of one.
Now as discussed.
So what we will also consider this area.
So let's say the array elements are five, eight, three, one and six.
And what was our approach?
So I will divide the array into two parts.
So the first part is actually containing the hip element and the second part is actually containing
our unsorted area.
And we discussed it.
But we will also I will start reversing the area from the next one.
So this is an this is an X zero, so I will start traversing the area from the next one.
And our approach is very simple.
So one by one, I will push the elements into my hip.
So what will happen to the hip range will increase and the unsorted range will decrease.
So you can insert elements and obviously the next zero is one.
So this is my child index.
And again, you have to find out the pain index, which is simply index minus one by two.
And this loop is actually it is containing the child makes such an index value when then its value will
become three.
It will become two.
And then it's three.
And then it will become four.
So simply you have to compare it in five and nothing will happen.
Then you will take elementary inside your heap.
Then heap sizes increase and assorted sizes will decrease.
So similarly, three will come.
So the index will become two.
You can see child index will become two, then you can swap that image.
Three will come here, five will come here.
And similarly then you will take one.
So basically one will be in this position.
So the child index is three.
You can see the child index is three.
Again, you will do the comparison to one and it will get stabbed.
So this is when then one in three will get stabbed.
So this is one and this is three.
And similarly, you will take the element forward into consideration.
So finally, I he will increase and the state will that elements.
There are no certain elements left.
So you will push six at this position, so finally, what is my hip?
So this is one, then it is three, then it is five, then it is containing eight and this is six.
Simple.
So basically, if you will convert it into an area again to the level of traversal.
So this is one.
This is three.
This is five.
This is it.
And this is six.
So very, very simple.
But we have to do we will just reverse from index one.
We will start reversing from the next one and we can copy paste our old code, our old insert function
called now one thing we cannot directly use our one triadic because our own priorities create a vector.
So we cannot just blindly copy our code.
So we just have to do minor, minor changes.
Now let's start writing the code.
So this is my file and the place he ordered CPV, so let us create a function so that the function will
be void because it will just sort Meyera, it will not do anything else.
It will not return anything.
So the name of the function is inbuilt.
He sort.
So what this function will take, so this function will take two things as input to first, one is actually
the Eddie.
And let's say the name of that is in and the second one is actually the size of the ADL and.
So what is the first step?
So first step is very simple, but we are going to do it so we will build keep inside the area.
So first step is very simple.
We will build deep.
In prudery.
We will not use any extra space for building the ship, I told you, we have to start our trading from
next one because we can assume that index zero is already in a heap.
So you can see.
So the value at index zero is already inside the heap, we have to start premising from index one and
then we will take element in to help one by one.
Simple.
So I will start from one and then I listened and I placeless, simple.
So what they have to do, we have to copy paste of something called.
So this is my Plotka class, this is insert function now what we are doing, so this is our elemental
I was pushing elements.
Now, this thing is not required.
We have to copy paste only this much amount of gold.
So after copy pasting the code.
So this is the situation.
Now we have to do some changes, for example, because nothing peculiar to say so.
This is my child index, so what is child index, you can see so the index is nothing.
It is just the index of the area, so it will start from one, then it'll become two, then it will
become three and so on.
So first, I have to update my child index.
Which index is actually the index of the area.
So this is simply a.
So first thing.
So this is very simple, very minor change, so child indexes, a and one more thing.
So here, the name of the is input, but we are actually using Piku everywhere, so let's change the
name to the name of the input that is Piku.
So first I am finding out the child index, which is correct, then this is the standard code.
So while Calix is good then it'll find the index, then do the comparison.
If the child index is Milovan, so do the part then update the child index as to the break.
So this break is actually.
So this statement actually makes the inner most loop.
So the innermost loop is by loop.
So this big statement can only break by loop.
It cannot break for loop.
So this thing you should remember now after doing this.
So actually, our help is right now, our help is ready then what we have to do.
So basically now we have to call the remove minimum function and times.
So what we have to do, we have to call remove minimum function and times now what we are doing here.
So after this cold, so let's say my input at is actually, let's say five eight, one, two and zero.
So let's say this is my input area five it one to zero.
So after passing through this code, what will happen to.
This is the value of I, so I will vary from index one to the last index.
So index is nothing.
It is just.
The value of the added, just the index of the area, so first five elements.
So this element, five inside our heap, so take element.
So nothing will happen.
So this condition will become false and we will break.
So I have element one Satake element one, then compared element one with element five.
So we will do the stripping then you will take element to so element to it.
So then you will find out your paint index.
So this is element to the index is basically.
So this is index zero one, two and three.
Again you have to do the slapping part of this is it.
And this is to again take the elements.
And also this is element zero.
You will do the slapping.
Part of this is two.
This is.
So this is zero, then you will slap one in zero, so when will come in and zero will come here?
So finally, this is your area.
So this is 01, then I have five here, then I have it here and then I have two here.
So this is your.
Minimum heap, so this school is actually for minimum.
We are trying to implement our minimum priority queue and if you convert converted into an area.
So this is zero, then I have one, then I have five.
Then I have it.
And then I have two.
So 015 eight two.
Now, this is our input area.
So this area has now been converted into this area and now we have to do so.
We just have to call the remove minimum function and times.
Or you can also call and sometimes both will be correct, because if you recall, and minus one times,
so what will happen, only this element will be left.
So it is your choice whether to.
So this is not irrelevant.
So basically, the size will be one, size will be one.
And it is your choice because the element is going to establish itself.
So it doesn't make any sense to call.
And times you can also call and minus one times, let's say we will call and times.
So if you remember how they removed minimum function, Wilberg, so this was my area zero, then one.
So this was my minimum 015 eight and do so I have to call the minimum function.
So it will going it will Sub-Zero and also zero will come here and two will come here.
Then actually in the original code we were trying to delete element zero, but here we will not delete
zero.
We will just assume that element zero has been removed.
We just have to adjust.
So what we will do, I will take a variable size and instead of doing B good artpop back.
So work bob back function do so it also decrease the size it removed the elemental back function, do
two things so it will remove the element and it would also decrease the size by one.
So we will not use proper function material.
So we will just reduce size minus minus.
So size minus minus indicates that the element has been removed.
Because we do not have to actually remove the element, we just have to assume so for assumption, we
will just take a variable size and we will lose size minus minus and size minus minus indicates that
the element is removed.
Simple.
So let's do this.
And also, after stepping, we have to put two added side operations here compared to with one in five.
And again, I will say absolutely will come here.
And when will commercial now to compare to with it, but do not compare two with zero because this is
removed, this element has been removed.
So that's why I will lose size minus.
Minus.
So what we have to do, so let's take a variable size, so initially my initial my area is containing
N elements.
So what we have to do so first thing is basically we have to swab the first element with the last element.
Because I want to remove medium function and time so that the first element, which is zero with the
last element to what is the last element, so I will use size minus one to size minus one will give
me the index of the last element and then if you will see.
So here's what I was doing, so I was calling the function back, but here I will just write says minus
minus Simbel.
So this indicates that the element has been removed, but this is only assumption to element is removed.
Now you can just copy paste the code.
Because we have to don epiphytes.
It's down here, Biffy.
OK, so this is the code for down here, Biffy.
So let me check the loops first.
OK, so this is correct.
So, again, we have to do down here.
If I saw the paint index zero, correct.
While Drew, I am finding out the left index, right index, then the index is actually the paint index,
then left index is less than I should be good outside.
So here I will not use peculiarities.
I will simply use the size variable.
So the size variable.
Now this is correct.
So again, instead of peculiar because we do a simple vector here, so simple simply I will use the
same variable.
So this variable.
Then this is correct.
So I'm scrapping and then Bendix is getting ablated with the index, so correct.
So this is one time I have to perform it and times I have to call remove Menom function and times.
So let's do it.
So now to call the function and times what I will do.
So while size is guerdon or goes to one.
We have to call the movement function and.
So, yes, everything seems fine.
So as discussed, how many times we have to remove minimum function, so we have to remove minimum function
and times, so the size, the value of sizes and while size is bigger than order, close to one end
size, minus minus.
So let me save this loop.
So this law will run and time's simple, this loop is going to run and times are good, then are close
to one end size, minus minus.
And see what I was trying to tell you, that instead of using this condition, says the Noriko's to
one, you can also write the condition, says guerdon one.
Why?
Because see if the value of sales is one, then what is happening here.
So the value is one.
So one minus one that is zero and this is also zero.
So what you are doing, you're swapping AOF zero with zero.
Where is the eddy?
So you are swiping the same two elements.
So that's why I told you that you can also write is lower than when both are correct if you will is
good then one.
So the least value of sales will be to and in that case you will be swapping the element of zero with
each to both are correct.
It is your choice.
So this is our standard called.
We do not have to do anything here, we just have to right size here instead of peculiarities, you
will use the size, variable and similarly size.
So everything will remain the same.
So afraid of the cold, we have to test whether our goal is working, correct or not.
So let's make our input very.
So let's say the elements are five one, two zero and eight, so this is zero and eight.
So I have five elements then I have to call the function in place.
So let's copy the name I have to pass to I have to pass booting the area.
And this is.
So the name of the ad is and put.
And there are five elements.
And now let's try to pin down our elements.
So this is my input today, I am calling the function in place, he observed, and we know it is advised
by a defense.
And in C++, that is our best bet, if it's by default and then I'm bending the elements.
So what will be my output?
So basically, we have written the code for implementing minimum prior queue, so virtually all parts
of my output should be it, then it should be five, then it should be two, then it should be one,
and then it should be zero.
So basically our output will be in decreasing order.
Why it is in decreasing order, because if you will see the last video, so in the last video, I already
explained to you that the output is coming out to be in decreasing order.
So you can see if we are going to implement the minimum protocol, then basically our output is going
to be sorted in descending order.
There are is going to be in descending order if you want Iraq to be in ascending order.
So you have two options first implemented prior to go and then apply the reverse function, you can
just reverse the error.
And the second way is just write the code for the maximum priority queue.
So this should be my output, eight five two one zero.
So let's see.
So you can see the output is coming out in descending order.
So eight five two one zero.
So our goal is working fine.
Now, again, if you want, we can analyze the time and the space complexity.
So, first of all, the space complexity and this is very simple.
We are just creating very few variables.
So the space complexity is constrained.
If you want to analyze the time complexity.
So let me do that.
So we have to function first inside function and then we have removed minimum function, so we are using
to loop.
So this is the first loop.
So this loop will run and times and this is the insert function called insert at the right place.
And we know insertion takes longer in time.
So this is a login so and login for building the heap and login for building the heap in the input area.
And then we have to call remove minimum function and times.
So I am calling the function and times and each time removal.
So we are doing down here biffy and here we are doing up by so end times and each time login time so
and login.
And if you will add these two to the time complexities and login and the space complexity is very simple.
This is big of one.
So this is the code for the minimum priority queue.
And the output is going to be in descending order.
So if you want to implement maximum protocol, so what changes you have to do?
So first of all, you have to change this code, building the heap so you will just change a few variables.
So, for example, instead of less than you will.
Right, good.
Then then similarly, you have to do minor minor changes in remove function, for example, where you
are writing the condition less.
You will write the conditions there then.
So these are very few minor changes that you have to do for implementing maximum protocol.
And I have confidence in you guys that you can definitely implement, mix and protect yourself.
So if you will implement makes improved, you are getting the time and the space complexity.
So they will be same time is going to be and Logan and the space is going to be big often.
And basically your input array will be started in ascending order.
So I will share this quote with you.
You can analyze this called.
So I will see you in the next one.
Bye bye.