1
00:00:02,360 --> 00:00:03,110
Hello, everyone.

2
00:00:03,140 --> 00:00:06,740
So in this lesson, we will discuss the ways to implement our priorities.

3
00:00:07,220 --> 00:00:14,550
But before starting the topic, let us discuss what is practical and let us revise what is exploding

4
00:00:14,660 --> 00:00:14,810
you.

5
00:00:15,500 --> 00:00:17,560
So suppose these are my elements.

6
00:00:17,990 --> 00:00:22,100
So Minecraft, Casey's first main element will come the element.

7
00:00:22,100 --> 00:00:24,020
Having the least Baradi will come first.

8
00:00:24,050 --> 00:00:25,790
So first, when will come?

9
00:00:26,660 --> 00:00:28,280
Then Elemental will come.

10
00:00:28,520 --> 00:00:31,040
And let's say now I'm inserting the element 20.

11
00:00:32,560 --> 00:00:33,710
So elementally welcome.

12
00:00:34,290 --> 00:00:36,840
Now, let's say I am again inserting the element zero.

13
00:00:37,210 --> 00:00:39,010
So now this time zero will welcome.

14
00:00:40,250 --> 00:00:47,060
Because zero has the least priority now, let us consider this example makes it a priority to eliminate

15
00:00:47,150 --> 00:00:47,930
having them exempt.

16
00:00:48,110 --> 00:00:48,950
They will come first.

17
00:00:49,370 --> 00:00:50,690
So first 14, welcome.

18
00:00:52,010 --> 00:01:00,260
Then I will come, then let's say I'm inserting 20, so then they will come now let's say I'm starting

19
00:01:00,260 --> 00:01:03,290
zero, then element it will come.

20
00:01:03,650 --> 00:01:09,480
So in this way, the element having the mix priority are coming out first and in the minimum priority,

21
00:01:09,690 --> 00:01:12,690
the element having the least priority will come first.

22
00:01:13,220 --> 00:01:13,850
Simple.

23
00:01:15,020 --> 00:01:17,660
Now let us discuss the ways to implement triadic you.

24
00:01:19,410 --> 00:01:25,050
So as discussed in the last video, we need to function, we need insert function, we need to get the

25
00:01:25,050 --> 00:01:30,730
minimum function in case of you, we need to get the maximum function in case of make simpler dequeue

26
00:01:30,750 --> 00:01:34,050
and similarly remove minimum and remove maximum function.

27
00:01:35,650 --> 00:01:40,120
So the first year, the structure that we can use for implementing protocol is Eddie.

28
00:01:41,940 --> 00:01:43,450
Now, Eddie can be of two types.

29
00:01:43,490 --> 00:01:46,230
First, let's discuss about unsorted Eddie.

30
00:01:47,160 --> 00:01:48,990
So in case of unsorted Eddie.

31
00:01:50,430 --> 00:01:57,150
Here, I will read the -- complexities over the time, complexity for session, so since the phrase

32
00:01:57,190 --> 00:02:03,540
unsorted so you can insert the element at the last time, complexities, constant big ofman.

33
00:02:04,590 --> 00:02:09,169
Now the Eddison ordered and you want to find out the minimum or the maximum limit.

34
00:02:09,419 --> 00:02:13,830
So what you have to do, you have to perform the edit reversal to find out the minimum or make some

35
00:02:13,830 --> 00:02:15,990
element because our arrays unsorted.

36
00:02:17,030 --> 00:02:19,280
So the time complexities big often.

37
00:02:20,400 --> 00:02:25,540
Now, third function, remove minimum or remove him, so here you will need two drivers.

38
00:02:26,040 --> 00:02:27,640
So first, drivers basically.

39
00:02:29,020 --> 00:02:34,270
We will try to find out the minimum or the maximum limit and then what they have to do, so basically

40
00:02:34,270 --> 00:02:35,980
we have to shift all of that elements.

41
00:02:36,890 --> 00:02:42,460
So in this case, so suppose this is my area now you want to remove this element.

42
00:02:42,670 --> 00:02:45,970
So for removing this element, you have to shift this area.

43
00:02:47,290 --> 00:02:50,260
The words left by one unit, so.

44
00:02:51,770 --> 00:02:56,870
First big event to find out the meaning of the Maksym element, and then you have to shift all the other

45
00:02:56,870 --> 00:02:57,340
elements.

46
00:02:57,350 --> 00:02:59,660
So in the worst case, you have to shift end elements.

47
00:03:01,110 --> 00:03:05,610
So, again, the time complexities, doing and doing is actually big often.

48
00:03:06,720 --> 00:03:12,940
So I insert will work perfectly fine, but these two are very expensive, big often and big often.

49
00:03:13,620 --> 00:03:20,960
Now let's discuss our security structure so that we can use we can use our edit instead of edit artillery,

50
00:03:21,690 --> 00:03:23,180
OK, we can use this already.

51
00:03:23,370 --> 00:03:27,770
So in case of minimum priority, our address will be sorted in ascending order.

52
00:03:28,050 --> 00:03:31,930
In case of mixing particular, our area will be sorted in descending order.

53
00:03:32,220 --> 00:03:32,760
Simple.

54
00:03:34,130 --> 00:03:38,450
Now, let us discuss the time complexity now you want to insert an element.

55
00:03:39,780 --> 00:03:43,350
So since the area started, so first, what do you have to do?

56
00:03:43,380 --> 00:03:48,780
You have to find out the correct position for the element to be inserted and then you will insert the

57
00:03:48,780 --> 00:03:51,960
element and you have to shift all the other elements of the.

58
00:03:52,650 --> 00:03:55,020
So, again, and placenta's actually big often.

59
00:03:56,050 --> 00:03:58,840
Now you want to find out the minimum or the maximum limit.

60
00:03:59,080 --> 00:04:02,740
So, again, minimum or the maximum will be present at the first index.

61
00:04:03,220 --> 00:04:04,710
So it will be question time.

62
00:04:05,440 --> 00:04:10,810
And if you want to remove minimum element, so we know the minimum element is present at the first index

63
00:04:10,810 --> 00:04:12,830
or the maximum limit, especially the first NICS.

64
00:04:13,120 --> 00:04:15,220
And then basically you have to shift the area.

65
00:04:15,790 --> 00:04:17,320
You have to shift all of the elements.

66
00:04:17,950 --> 00:04:19,779
So Konstantine plus linear time.

67
00:04:20,140 --> 00:04:21,430
So it is big often.

68
00:04:21,700 --> 00:04:27,030
Now, in this case, I will get the minimum, get maximum function is performing really good, but instead

69
00:04:27,040 --> 00:04:28,560
function as expensive.

70
00:04:28,930 --> 00:04:32,440
Similarly, remove minimum and maximum function is also expensive.

71
00:04:34,060 --> 00:04:36,550
Now let's discuss the target, the structure that we have.

72
00:04:37,210 --> 00:04:38,660
So we have linked lists.

73
00:04:39,070 --> 00:04:41,830
Now first, let's discuss about unsorted linked list.

74
00:04:42,460 --> 00:04:47,500
So unsorted means we do not consider we do not care about the order in which the elements are present.

75
00:04:48,550 --> 00:04:53,500
So first, let's discuss about the insert function, so there are two ways you can insert that head

76
00:04:53,500 --> 00:04:54,790
or you can insert detail.

77
00:04:55,120 --> 00:05:00,700
So if you are inserting it had the time, complexity is big often, and if you're inserting a little

78
00:05:00,700 --> 00:05:02,710
material, you will maintain a little pointer.

79
00:05:02,980 --> 00:05:05,320
So inserting a tail is also a big government.

80
00:05:06,010 --> 00:05:07,690
Now get me nor get the maximum.

81
00:05:08,160 --> 00:05:12,820
So finding out, get the minimum or you for finding out the minimum, the maximum element.

82
00:05:12,830 --> 00:05:17,140
But you have to do you have to traverse the complete length list because I will include this unsorted

83
00:05:17,500 --> 00:05:23,240
so time complexities again big often now four remove minimum and remove maximum function.

84
00:05:23,560 --> 00:05:25,180
First you have to find that element.

85
00:05:25,300 --> 00:05:28,570
So basically you have to perform the traversal now for removing.

86
00:05:28,570 --> 00:05:30,730
So EnLink list removal is on.

87
00:05:31,980 --> 00:05:40,050
So time complexities big often now and linked list in third function is very good, but get the minimum

88
00:05:40,050 --> 00:05:42,930
and remove many more to make them function is expensive.

89
00:05:43,950 --> 00:05:48,810
Now, the fourth traders actually can use is basically a long list sorted.

90
00:05:49,950 --> 00:05:55,980
So inserted link list, again, if I'm implementing minimum priority queue, our linked list will be

91
00:05:55,980 --> 00:06:01,370
sorted in ascending order, otherwise it will be sorted in descending order for the maximum variety.

92
00:06:01,440 --> 00:06:05,220
You know, let us discuss first insert function.

93
00:06:06,750 --> 00:06:11,730
Now, what do you have to do so first of all, you have to find out the correct position at which you

94
00:06:11,730 --> 00:06:15,840
have to searched so for finding out the correct position, you have to add to the list.

95
00:06:16,200 --> 00:06:18,710
And then basically the insertion is question time.

96
00:06:19,080 --> 00:06:24,580
So, again, the time complexities big often for finding out the M.O., the MAKSYM element.

97
00:06:25,170 --> 00:06:30,510
So since the Linklaters started, so minimum or the maximum element will be at head only.

98
00:06:30,990 --> 00:06:34,950
So again, question time now for removing the minimum, the maximum element.

99
00:06:35,460 --> 00:06:39,180
So for removing we know the maximum or the minimum element will represent dopehead.

100
00:06:39,930 --> 00:06:44,250
So over time and finding out the minimum element and then again over time for removal.

101
00:06:44,860 --> 00:06:46,830
So time complexities, big one.

102
00:06:47,550 --> 00:06:53,190
Now these two functions are performing really, really good, but is function is expensive.

103
00:06:54,790 --> 00:07:01,630
Now, the next to the structure that we can discuss is let's discuss about Best Baynie surgery so we

104
00:07:01,630 --> 00:07:02,820
know what is a by necessity.

105
00:07:03,160 --> 00:07:05,680
So all the left values are smaller than the root.

106
00:07:05,830 --> 00:07:08,410
All the right values are good and simple.

107
00:07:09,070 --> 00:07:16,380
Now, if you want to insert in a body safwat insertion in the time complexities, big of Etch Sketch

108
00:07:16,390 --> 00:07:19,480
is the height of the tree in worst case.

109
00:07:20,460 --> 00:07:27,150
It will be big off and the worst case and the worst case I would hide will be in so far and complexity

110
00:07:27,150 --> 00:07:27,800
will be big, Wolf.

111
00:07:27,810 --> 00:07:28,110
And.

112
00:07:29,280 --> 00:07:35,230
Now let's discuss about get minimum or get mixed maximum function, so if you want to find out the minimum

113
00:07:35,230 --> 00:07:39,270
element in what you have to do, you will go left, left, left, left, left.

114
00:07:39,300 --> 00:07:41,510
So extreme left will have to go extreme left.

115
00:07:41,530 --> 00:07:44,400
So order of age for finding out the maximum element.

116
00:07:44,400 --> 00:07:46,940
So maximum will be present at the extreme right.

117
00:07:47,160 --> 00:07:47,820
So you will go.

118
00:07:47,820 --> 00:07:49,160
Right, right, right, right, right.

119
00:07:49,170 --> 00:07:51,480
So time complexities big of each.

120
00:07:52,670 --> 00:07:55,310
Now, again, in the worst case, it will be big off and.

121
00:07:56,910 --> 00:08:01,800
For the movement, functionality will make him function again, the time complexity will be of which

122
00:08:02,670 --> 00:08:05,460
simple in the worst case, again, it will be big.

123
00:08:05,460 --> 00:08:08,670
Often in the worst case, it will be big often.

124
00:08:09,120 --> 00:08:11,980
So now let's discuss our next new structure.

125
00:08:12,420 --> 00:08:15,530
So what we can use, we can use a balance to be bisdee.

126
00:08:15,570 --> 00:08:19,510
Instead of using normal bisdee, we will use balanced bisdee.

127
00:08:19,530 --> 00:08:20,940
So what is a balanced body?

128
00:08:21,270 --> 00:08:24,780
So the difference between the left and the right substrate.

129
00:08:25,080 --> 00:08:29,640
So this is more or less so difference between the left and the right supplicate will be denoted close

130
00:08:29,640 --> 00:08:29,980
to one.

131
00:08:31,080 --> 00:08:38,460
Now in the balance to be used again, but over time, complexity for In Session Big off edge and we

132
00:08:38,460 --> 00:08:39,210
can assume so.

133
00:08:39,210 --> 00:08:40,230
This is Logan.

134
00:08:41,230 --> 00:08:47,680
Because we have balanced obviously so high, it will always be Logan, so again, get a minimum or get

135
00:08:47,680 --> 00:08:49,240
maximum function time complexities.

136
00:08:49,260 --> 00:08:51,400
Begovic and height is always Logan.

137
00:08:52,460 --> 00:08:55,070
And this case also our is always log-in.

138
00:08:56,150 --> 00:09:05,010
So big off, big off logging now all three functions are medullary, they are neither good nor expensive.

139
00:09:05,990 --> 00:09:08,130
So now let us compare all these data.

140
00:09:08,600 --> 00:09:10,310
So suppose I have inquiries.

141
00:09:11,660 --> 00:09:19,640
Now, in these inquiries, what I have to do, I have to insert names so you will insert and times and

142
00:09:20,030 --> 00:09:26,180
you will remove any names, so names in association and names removal.

143
00:09:26,750 --> 00:09:30,200
So now let us try to discuss the time complexity for each investigator.

144
00:09:32,530 --> 00:09:35,530
So first of all, let us discuss about unsorted Eddie.

145
00:09:36,690 --> 00:09:42,900
So you are inserting and time constraint time, but for removing it will take and time and data and

146
00:09:42,900 --> 00:09:46,170
elements of time, complexities and squit again.

147
00:09:46,380 --> 00:09:53,490
So avoiding section and square time again and square and square is simple and square.

148
00:09:55,420 --> 00:09:59,140
For unsorted, long list in session is constant name, but.

149
00:10:00,390 --> 00:10:04,380
Any movement you want to make, some it will take and it's a good time because for one element it will

150
00:10:04,380 --> 00:10:06,390
take time and we have an element.

151
00:10:06,720 --> 00:10:09,680
So it's great again for Citilink List.

152
00:10:10,530 --> 00:10:13,260
So this is and square and this is constant.

153
00:10:13,260 --> 00:10:17,240
So Anscar time for the best and the worst case.

154
00:10:17,250 --> 00:10:21,570
This is this will be the time complexity of organization and this will be 40 remould.

155
00:10:21,690 --> 00:10:26,090
So again the time complexity will be squared plus and square, so simple and square.

156
00:10:26,580 --> 00:10:28,820
Now let us discuss about the balanced body.

157
00:10:29,460 --> 00:10:34,080
So this will be and Logan Glass and Logan so and Logan percent.

158
00:10:34,080 --> 00:10:35,820
Logan two and Logan so simply.

159
00:10:35,820 --> 00:10:36,420
And Logan.

160
00:10:37,530 --> 00:10:41,400
So if you will compare, this is performing the best.

161
00:10:41,490 --> 00:10:46,950
This is giving me the best performance and Logan arrest and really the structures giving me and square.

162
00:10:48,880 --> 00:10:53,350
Now, you can think of one as a picture, so we can also use an order to map.

163
00:10:54,420 --> 00:11:01,770
So in another map, what is their time, complexity for inception, so time complexity is constant.

164
00:11:02,660 --> 00:11:07,610
Now get them in order to make them function, but they have to do you have to traverse over the complete

165
00:11:07,610 --> 00:11:10,970
map so for traversal it will take a lot of time.

166
00:11:11,420 --> 00:11:16,160
And similarly, if you want to remove the minimum, the maximum limit, you first have to find out the

167
00:11:16,160 --> 00:11:18,590
minimum element and for finding out the minimum element.

168
00:11:18,950 --> 00:11:22,790
First, you have to perform the traversal and the removal is constant.

169
00:11:23,900 --> 00:11:28,570
So again, it is Magoffin and modular time complexity.

170
00:11:28,880 --> 00:11:34,310
So this constant insertion is constant, but you have to in certain elements and for one element it

171
00:11:34,310 --> 00:11:35,230
will take and time.

172
00:11:35,240 --> 00:11:36,880
So time, complexities and square.

173
00:11:37,760 --> 00:11:43,850
Now again, if you will compare, balanced bisdee gives us the best performance and.

174
00:11:44,200 --> 00:11:46,370
And so this is best.

175
00:11:50,150 --> 00:11:53,970
So in the next video, we will discuss how we can implement our own priorities.

176
00:11:53,990 --> 00:11:55,700
You I will assume the next one, but by.

