Hello, everyone.
So in this lesson, we will discuss the ways to implement our priorities.
But before starting the topic, let us discuss what is practical and let us revise what is exploding
you.
So suppose these are my elements.
So Minecraft, Casey's first main element will come the element.
Having the least Baradi will come first.
So first, when will come?
Then Elemental will come.
And let's say now I'm inserting the element 20.
So elementally welcome.
Now, let's say I am again inserting the element zero.
So now this time zero will welcome.
Because zero has the least priority now, let us consider this example makes it a priority to eliminate
having them exempt.
They will come first.
So first 14, welcome.
Then I will come, then let's say I'm inserting 20, so then they will come now let's say I'm starting
zero, then element it will come.
So in this way, the element having the mix priority are coming out first and in the minimum priority,
the element having the least priority will come first.
Simple.
Now let us discuss the ways to implement triadic you.
So as discussed in the last video, we need to function, we need insert function, we need to get the
minimum function in case of you, we need to get the maximum function in case of make simpler dequeue
and similarly remove minimum and remove maximum function.
So the first year, the structure that we can use for implementing protocol is Eddie.
Now, Eddie can be of two types.
First, let's discuss about unsorted Eddie.
So in case of unsorted Eddie.
Here, I will read the -- complexities over the time, complexity for session, so since the phrase
unsorted so you can insert the element at the last time, complexities, constant big ofman.
Now the Eddison ordered and you want to find out the minimum or the maximum limit.
So what you have to do, you have to perform the edit reversal to find out the minimum or make some
element because our arrays unsorted.
So the time complexities big often.
Now, third function, remove minimum or remove him, so here you will need two drivers.
So first, drivers basically.
We will try to find out the minimum or the maximum limit and then what they have to do, so basically
we have to shift all of that elements.
So in this case, so suppose this is my area now you want to remove this element.
So for removing this element, you have to shift this area.
The words left by one unit, so.
First big event to find out the meaning of the Maksym element, and then you have to shift all the other
elements.
So in the worst case, you have to shift end elements.
So, again, the time complexities, doing and doing is actually big often.
So I insert will work perfectly fine, but these two are very expensive, big often and big often.
Now let's discuss our security structure so that we can use we can use our edit instead of edit artillery,
OK, we can use this already.
So in case of minimum priority, our address will be sorted in ascending order.
In case of mixing particular, our area will be sorted in descending order.
Simple.
Now, let us discuss the time complexity now you want to insert an element.
So since the area started, so first, what do you have to do?
You have to find out the correct position for the element to be inserted and then you will insert the
element and you have to shift all the other elements of the.
So, again, and placenta's actually big often.
Now you want to find out the minimum or the maximum limit.
So, again, minimum or the maximum will be present at the first index.
So it will be question time.
And if you want to remove minimum element, so we know the minimum element is present at the first index
or the maximum limit, especially the first NICS.
And then basically you have to shift the area.
You have to shift all of the elements.
So Konstantine plus linear time.
So it is big often.
Now, in this case, I will get the minimum, get maximum function is performing really good, but instead
function as expensive.
Similarly, remove minimum and maximum function is also expensive.
Now let's discuss the target, the structure that we have.
So we have linked lists.
Now first, let's discuss about unsorted linked list.
So unsorted means we do not consider we do not care about the order in which the elements are present.
So first, let's discuss about the insert function, so there are two ways you can insert that head
or you can insert detail.
So if you are inserting it had the time, complexity is big often, and if you're inserting a little
material, you will maintain a little pointer.
So inserting a tail is also a big government.
Now get me nor get the maximum.
So finding out, get the minimum or you for finding out the minimum, the maximum element.
But you have to do you have to traverse the complete length list because I will include this unsorted
so time complexities again big often now four remove minimum and remove maximum function.
First you have to find that element.
So basically you have to perform the traversal now for removing.
So EnLink list removal is on.
So time complexities big often now and linked list in third function is very good, but get the minimum
and remove many more to make them function is expensive.
Now, the fourth traders actually can use is basically a long list sorted.
So inserted link list, again, if I'm implementing minimum priority queue, our linked list will be
sorted in ascending order, otherwise it will be sorted in descending order for the maximum variety.
You know, let us discuss first insert function.
Now, what do you have to do so first of all, you have to find out the correct position at which you
have to searched so for finding out the correct position, you have to add to the list.
And then basically the insertion is question time.
So, again, the time complexities big often for finding out the M.O., the MAKSYM element.
So since the Linklaters started, so minimum or the maximum element will be at head only.
So again, question time now for removing the minimum, the maximum element.
So for removing we know the maximum or the minimum element will represent dopehead.
So over time and finding out the minimum element and then again over time for removal.
So time complexities, big one.
Now these two functions are performing really, really good, but is function is expensive.
Now, the next to the structure that we can discuss is let's discuss about Best Baynie surgery so we
know what is a by necessity.
So all the left values are smaller than the root.
All the right values are good and simple.
Now, if you want to insert in a body safwat insertion in the time complexities, big of Etch Sketch
is the height of the tree in worst case.
It will be big off and the worst case and the worst case I would hide will be in so far and complexity
will be big, Wolf.
And.
Now let's discuss about get minimum or get mixed maximum function, so if you want to find out the minimum
element in what you have to do, you will go left, left, left, left, left.
So extreme left will have to go extreme left.
So order of age for finding out the maximum element.
So maximum will be present at the extreme right.
So you will go.
Right, right, right, right, right.
So time complexities big of each.
Now, again, in the worst case, it will be big off and.
For the movement, functionality will make him function again, the time complexity will be of which
simple in the worst case, again, it will be big.
Often in the worst case, it will be big often.
So now let's discuss our next new structure.
So what we can use, we can use a balance to be bisdee.
Instead of using normal bisdee, we will use balanced bisdee.
So what is a balanced body?
So the difference between the left and the right substrate.
So this is more or less so difference between the left and the right supplicate will be denoted close
to one.
Now in the balance to be used again, but over time, complexity for In Session Big off edge and we
can assume so.
This is Logan.
Because we have balanced obviously so high, it will always be Logan, so again, get a minimum or get
maximum function time complexities.
Begovic and height is always Logan.
And this case also our is always log-in.
So big off, big off logging now all three functions are medullary, they are neither good nor expensive.
So now let us compare all these data.
So suppose I have inquiries.
Now, in these inquiries, what I have to do, I have to insert names so you will insert and times and
you will remove any names, so names in association and names removal.
So now let us try to discuss the time complexity for each investigator.
So first of all, let us discuss about unsorted Eddie.
So you are inserting and time constraint time, but for removing it will take and time and data and
elements of time, complexities and squit again.
So avoiding section and square time again and square and square is simple and square.
For unsorted, long list in session is constant name, but.
Any movement you want to make, some it will take and it's a good time because for one element it will
take time and we have an element.
So it's great again for Citilink List.
So this is and square and this is constant.
So Anscar time for the best and the worst case.
This is this will be the time complexity of organization and this will be 40 remould.
So again the time complexity will be squared plus and square, so simple and square.
Now let us discuss about the balanced body.
So this will be and Logan Glass and Logan so and Logan percent.
Logan two and Logan so simply.
And Logan.
So if you will compare, this is performing the best.
This is giving me the best performance and Logan arrest and really the structures giving me and square.
Now, you can think of one as a picture, so we can also use an order to map.
So in another map, what is their time, complexity for inception, so time complexity is constant.
Now get them in order to make them function, but they have to do you have to traverse over the complete
map so for traversal it will take a lot of time.
And similarly, if you want to remove the minimum, the maximum limit, you first have to find out the
minimum element and for finding out the minimum element.
First, you have to perform the traversal and the removal is constant.
So again, it is Magoffin and modular time complexity.
So this constant insertion is constant, but you have to in certain elements and for one element it
will take and time.
So time, complexities and square.
Now again, if you will compare, balanced bisdee gives us the best performance and.
And so this is best.
So in the next video, we will discuss how we can implement our own priorities.
You I will assume the next one, but by.