Hi, everyone.
So in the last video, reimplemented, our only minimum priority queue, and we're this close to what
is he?
So if you remember the time complexity of Heap's art was and Logan and the space complexity was big
of an.
Now, in this video, we wanted to discuss such an algorithm such that the space complexity should become
bigger.
Even so, that means constrained space.
So why the space complexity was big often.
So the space complexity was big, often because we were creating a vector and this vector became so
distracted, was actually containing our minimum hype.
So this vector was containing the elements of our minimum heap.
So that's why you do this with the space.
Complexity was big often.
Now, this input that is given, so this input that is actually given to us now, what will do so in
this algorithm?
So in this video, in this lesson, what we will do so I am going to convert this area into a minimum
heap.
So I'm going to build a minimum heap inside this area only.
So if we're able to build a minimum heap in this area only, basically you are going to change this
area into a minimum heap.
So if you are able to do that, then your time, complexity aside, your space complexity will become
big often because you are not you will not take any extra space.
So this is called in place or so in place means you will not take any extra space.
So the space complexity will be big.
Goffman and approach is very simple.
So instead of taking a new area, a new vector for building the minimum, what material?
We will convert the input into a minimum.
So we will build minimum Hipp inside this given area only.
So I'm going to change the input very simple, so that we can achieve constant space.
So now let's discuss the algorithm.
So if you remember the heap short, so he has two parts.
So first part was basically building the minimum up.
And the second part was actually to call the remove minimum function and times and is basically the
size of the area.
So he thought was to part first part is to build them up.
And second part was to remove minimum function and times so that we can get the minimum element.
And simple.
So now let us first discuss how can we build minimum help inside this input area?
So now let us try to understand.
So let's take this example.
Only 10, five eight one four.
So, Avineri.
So the first element is 10, then I have five, then hit, then one, and then we have four.
So this is the input.
That argument was simple.
Now what we are going to do, so we will assume that this part is actually.
So this part, we will assume that this part has been converted into a minimum.
We will assume this and the rest of the and minus one element is actually our answer today.
So we are going to assume this.
So if this is a part of heap, so that means this is Maitri simple now one by one.
But we will do we will take the element one by one inside the heap, just like we used to do in Oceanside.
So what we will do now put five to now take five into consideration.
So now what I'm saying so this part I'm saying this part is part of my hip and this is normal, just
our unsorted area.
So basically you are starting five, so let's insert five.
Now, after inserting five CBD property has been satisfied, but again, you have to satisfy the many
properties or what you have to do, you will swap.
So I will step down in five.
And here, the slapping will take place over here and will come, and here it will come.
So we have done this thing many, many times morning to explain again and now what we will do.
We will take one more element into consideration.
So now take it into consideration.
So now what I'm saying so I'm saying these three elements are now part of my hip and these two elements
are actually unsorted elements, so I have one more element to it.
So let us insert it so it will be inserted here.
Now, this is Sebti and this is also I mean, I'm hip, simple.
So this is it.
Now, let's insert one more element.
So this time I'm taking one into consideration, so let's take one into consideration.
So what will happen when will be present at this partition?
So our CBT is correct, but this is not a minimum.
So, again, we will do the comparison and we will do the typing part.
So I will have one in 10.
So then we'll come here and one will come here.
So here, what will happen so is going to come here and one is going to come here.
Simple.
Again, what we will do I will not stop here, I will I will have to compare one in five, so compare
one in five and then you will slap so five will come here and one will come here.
So similarly, I'm swapping one in five.
So one is going to come here and five is going to come here.
Simple.
Now we have to take the last element into consideration also.
OK, so we have already took one element, one into consideration now that us look forward into consideration.
So Element four will be inserted at this position.
Again, we will do this.
We will do the comparison and disappointing.
So far, it is actually less than five.
So again, you have to do shopping.
So I will come here and Ford will come here.
So it is five.
So here we have four.
And here we have five.
Now compare Ford with one.
So it is correct.
Now we will stop at this point.
So finally, what is my ETA?
So the shape of is one, then I have element four, then I have element eight, then I have element
then and then I have element five.
So this is my.
Minimum heap, and similarly, you can see this, so this is one, then I have four, then I have eight
and then I have 10 and then I have five simple one four, eight, 10, five.
Now you can notice.
So basically this area is not a certain area.
So why this has not sorted?
Because you remember that he has two parts.
He was having two parts, first is building the minimum hip and second is actually to call the Raymore
minimum function and times.
So we have done the first part.
We have done the first part.
So our minimum hip is ready and we converted.
So what do we do?
So we converted this in, put it into a minimum hip.
We can order this input.
And what was the element?
So it was one four eight, then five one four eight and then 10 and then five.
So we are using constant extra space.
We just build the minimum hip in this area.
Only no need for any extra space.
Now we have to do the second part, remove minimum.
So we will apply the removal minimum function in this area and times.
Now, after doing this, after performing a minimum function and times everyday, we'll get get to.
So let's see, so this is my area one four eight nine five, so let's do it.
So I have one, then four, then eight.
Then 10 and then five.
And by this time, you should be very well aware of how removed minimum function work.
So, again, you can.
Let us build a trials also one four, then eight, then 10 and then five, simple.
So what we have to do, we have to remove the minimum function five times because the size of the arrays,
five.
Simple.
So let's start.
So what removing minimum function will do so it will remove the minimum element.
So remove the minimum element.
So for removing the minimum element, first work is to swap.
So I will swap one in five.
So what will happen when will come here and five will come here.
Now the second step of removing minimum function is to delete the last element.
So this is basically deleting.
So this works in normal, normal, remove minimum function.
But in our case we do not have to remove elements.
So this step is actually wrong.
We will not remove element.
We will just assume that element has been removed.
I'm repeating myself what happens in actual algorithm.
So actually no function what it will do.
So it will up the first element with the last element.
So five will come here and one will come here.
Then we used to write be good back if you remember.
But here what we will do.
We will not write be back, we will not write it, but we will assume that the last element has been
removed.
So we just have to assume this one.
We will not perform this.
We will just assume so.
Let's do so.
What will happen to one in five has been said.
So this is one and this is five now.
Now just assume that the element one has been removed.
Just assume now again what we will do, we will do the standard approach.
So compare five with four and eight.
Forward is the smallest.
What we will do, we will do the trappings of what will come here and five will come here.
Now compare five with the ten, but do not compare five with one because one has been removed.
It is not actually removed, but we have assumed that it is removed.
So five will get compared only with ten and then we have to do nothing.
So basically we did one more step in.
The five is actually slept with four, so four will come here and five will come here.
Simple now again.
So what is my three.
So this is four then I have five here and then we have eight and then we have ten.
So I am writing a different color.
So actually this one is removed but I am writing a different color so that you can assume that the one
element one has been removed.
Simple.
Now let's do it again.
So I want to remove the minimum element.
You can see the remove minimum function and times we have to perform and times now let's perform one
more time so four will get slapped with the last element.
Last element is ten.
Now four is here and then is here.
So let me do this.
Four so four and then so this is four and this is ten.
Simple.
And now this forward, you have to assume that this vote has been removed.
Now, again, do the same thing, compare 10 with five and it five is the smallest.
So you will separate five.
So five will come here and then will come here.
Now, compare then with its left and right children, but left and right children does not exist, so
you will not do anything.
So you will simply stop here.
So what did I do here?
So I said and in five surveyed, so so is here, I just saw 10 in five.
So 10 will come here.
And this is my element.
Five.
Simple.
So what is my Greenall?
So this is.
This is five, then I have ten here, then I have it here and the elements four and element one.
So this has been removed.
Now I want to remove element five, so element five will get swept with it.
So five will come here and it will come here, so do the stepping.
So element, it is going to come here.
And similarly, element five is going to come here.
Now, what are you going to do?
You will assume that Element five has now been removed.
So basically you will compare it with 10 and it is correct.
So do not do anything.
Now what is Maitri?
So my tree is very simple.
I have eight and 10, so I have only two elements left and all the elements has been removed.
So five is removed for it is removed, one is removed.
Simple.
Now I want to delete the minimum element so I will remove minimum function.
So I will separate and then so it is going to come here and it's going to come here.
So where is it.
So it got swept with 10 Beristain.
So it will come here and then will come here.
Simple.
Then what we will do.
So then now you know you will compare ten with its left and right children.
So left children does not exist, right.
Children does not exist.
So you will do nothing because left and right does not exist.
Now finally, what is your eddy.
So do you.
Finally, what is your tree.
Now I have only one element left, so I have been and basically all the elements has been removed.
So this is it.
This is five.
This is four.
And this is one.
Now what you have to do.
So basically you will step 10 with 10 because 10 is the last element also.
And then you will assume that element 10 has been removed.
So swept 10 with 10, so 10 will get seven with ten.
And then you will assume that element 10 has been removed.
So basically your tree is empty.
So by empty, I mean the tree is still there, but all the elements has been diluted, you have to assume.
OK, so we have called removed function and so here and this way, so we can remove the minimum function
five times and you can see so what is the condition of your area?
So your area now looks like this?
First I have then.
Then I have it.
Then five, then four, then one.
So 10.
Then I have it.
Then I have five.
Then I have four.
And then I have one.
Now you can notice.
So this area is actually sorted, but this area sorted in decreasing order.
That it gets sorted in decreasing order, but that's just fine.
So one thing is very clear here.
So in the in place he sought in the in place he sought, if you will, apply the minimum priority queue,
if you lose the court of meaning prior to you, then you really will get sorted in descending order
and in the in place.
He thought if you will use the card of if you will write the code for the maximum priority queue, then
your area basically then you will get sorted in the increasing order.
Simple now again, what is the time, complexities or time complexities still and Logan, we are just
using the report, but since.
We are building we are creating the we are building the heap in the given area only, and then we are
planning to remove minimum function in this area for the time.
So the space complex complexities big often.
So we are improving on space.
Simple, so if you have confusion, what you can do, you can just take one more example and you can
apply the algorithms.
So let me take one more example.
So this is my area, so I have element 15.
So let's say I have 15, then let's take it six, then three, then let's take two and then let's take
20.
Simple.
So Heap's Ortez, two parts.
He has two parts.
So, again, the first part is basically the building heap, so first parties, you what you will do,
you will build the heap in the given that only and second part, basically, you have to call the remove
minimum function and times and it's the size of the area.
So in times.
Simple.
So, again, we will do the same thing, so we will assume that this area, Element 15, has been inserted
into the hip.
So let me take me some variables.
So.
Let us take.
Let's take child index and let us take one multivariable parent index and let's take one more variable
index.
So what this index represents, so it will represent.
It will represent the starting point of the uncertainty.
So, for example, this is zero one, two, three and four.
So what is the starting point of the uncertainty that is?
So this part is actually the uncertainty.
So the starting point is the next one.
So this is containing one simple now element 15 has been pushed into the other heap, into our heap.
So we should write 15.
So I'm writing 15 here.
So 11, 15 has been inserted.
Simple.
So now let's insert elements six.
So I'm inserting elements, so it's a Nexus one, so that's why when it's presented, I'm inserting
sex.
So let's insert sex here.
Now, your child index is same as the index, so this is one on less than what you are going to do.
You will find out the parent index, which is zero, and then you are going to compare again the same
thing.
I'm comparing six and 15 and it will get set.
So 15 is going to come here and six will going to come here.
So again, we will do the September 15 is going to come here and six is going to come here and then
we will not stop here.
So what I'm going to update my child index.
So the child index just the same color child index will become zero.
And if you remember, in the last quarter we have written Gile Index for bigger than zero.
So the index becomes zero.
I'm going to stop.
So I will stop here.
So this is next zero and this is index one simple.
Now, let's take one more element into consideration.
So I am taking element into consideration.
So the value of it is to try to index.
So first, take three into consideration.
Its index is actually two, so that's why the index is doing so.
This is same as this one index.
Simple.
Now again, we are going to calculate the index for the comparison.
So being index is zero.
You remember the formula Gile index minus one, but also this is Giler index minus one by two.
So this formula you should remember now I'm going to compare three and six.
So what will happen?
Obviously, this will take place.
So six is going to come here and it is going to come here.
So let's do that sweeping so six and it will be three.
Simple.
And then what are going to do?
So now the trial index is actually zero.
So there does appear the child index.
So child index becomes zero.
As soon as the child index becomes zero, you are going to stop.
Simple.
Now, let's take one more element into consideration.
So I am taking element two into consideration.
So element two has index three.
So this is my element too.
And this has index to be simple.
Now, again, we are we are going to do the same thing, so.
Joel Index is actually three, and then you are going to find the painter next to paint the next one
and then you are going to compare two and 15.
So obviously something will take place.
So 15 is going to come here and two is going to come here.
So let's do it here.
So it do so instead of two, 15 will come here and instead of 15 it will be there.
And then your child next becomes one, so you will copy.
The challenge, next one now calculating, abandoned six, abandoned Nixon zero, and then let's do
the comparison to 20 again, you have to do the slapping part.
So two is going to come here and three is going to come here.
So barriers to entry.
So three is going to come here and two is going to come here.
Simple.
Then what will happen?
So now the child next becomes a zero.
So let's copy this one.
So as soon as a child next becomes zero, you will stop.
So I'm gonna stop.
Now, let's take one more element into consideration.
So this is the last element.
So take element into consideration.
So the value of AI becomes for the value of the value of AI becomes for Sottile.
So the element distantly so right on here.
So it's indexers for again, the child index is actually four.
Then you will calculate the into next to be Nix's one.
The index is one.
Then what you're going to do you will compare twenty with three to compare to the entry.
So this is correct.
Since this thing is correct then what do you, what do you want to do.
You will stop.
The Konstanty is at its right position so you will stop.
So finally, what is your eddy.
So your already do then you have three and then you have six and then you have fifteen and then you
have twenty and you can.
So what is your minimum.
So first I have element to.
Then I have elementary here, then 11, six, so two, then elementary, then Elliman six and then 15
and 20.
So then you have 11, 15 and then you have 11, 20.
So the first part of hip start to the first part.
So this is this is in place.
He sort.
So this is in place Cheapside, so the first part of in place, he is actually first building up, so
we have built the heap.
Inside the area, inside the Internet, now, we have to call the removed minimum function and times,
so I hope you can call remove minimum function on the city five times.
But just remember one thing.
You will not actually delete the element.
You will just assume that you have deleted the element.
For example, first 20-20 will get swabbed.
Then you do not have to call pop back function.
You will not call malfunction.
You will just assume that Element two has been removed.
You just have to assume so.
I really hope that you guys can implement this in place.
So what you have to do, you can just copy paste our zip code and you can also copy paste our remove
minimum function code, but you have to do some modification.
So just you have to just slightly, slightly modify our existing code.
I really hope that you guys can implement in place he brought.
I will write the code in the next video.
See you there.
Bye bye.