1
00:00:00,630 --> 00:00:01,650
Welcome back.

2
00:00:01,650 --> 00:00:05,520
Let's now code the priority queue which we discussed in the previous video.

3
00:00:05,550 --> 00:00:09,870
Now as we discussed we will be using a binary heap to implement this.

4
00:00:09,870 --> 00:00:13,740
And let's make the priority queue a minimum by binary heap.

5
00:00:13,740 --> 00:00:20,130
Now over here we will need a node class because every node will have a value as well as a priority.

6
00:00:20,130 --> 00:00:27,420
And then based on the priority, we will take the value with the minimum priority to the front or to

7
00:00:27,420 --> 00:00:32,580
the beginning of the array, because we will treat that priority one is the highest priority.

8
00:00:32,580 --> 00:00:33,090
All right.

9
00:00:33,090 --> 00:00:34,200
So we say class node.

10
00:00:34,200 --> 00:00:36,420
And then over here we will need a constructor.

11
00:00:36,990 --> 00:00:38,490
So let's write that.

12
00:00:38,490 --> 00:00:41,640
And over here we will pass the value and priority.

13
00:00:42,210 --> 00:00:46,590
And inside this we will say this dot value is equal to the value.

14
00:00:46,590 --> 00:00:51,090
And this dot priority is equal to the priority.

15
00:00:51,690 --> 00:00:52,290
All right.

16
00:00:52,290 --> 00:00:57,000
Now let's go ahead and code the priority class priority queue class.

17
00:00:57,000 --> 00:00:58,410
So we have priority.

18
00:00:59,750 --> 00:01:00,020
You.

19
00:01:00,020 --> 00:01:01,580
Let's call it Priority queue.

20
00:01:02,240 --> 00:01:05,120
And over here also we need a constructor.

21
00:01:05,120 --> 00:01:06,650
So let's write that.

22
00:01:07,070 --> 00:01:09,620
And inside the constructor we don't pass anything.

23
00:01:09,620 --> 00:01:13,010
And we just say this dot data is an empty array.

24
00:01:13,970 --> 00:01:14,600
All right.

25
00:01:14,600 --> 00:01:21,470
Now over here we will write the instance methods to insert a value to the priority queue and to take

26
00:01:21,470 --> 00:01:24,500
the element with the highest priority out.

27
00:01:24,500 --> 00:01:27,500
So the highest priority over here means the minimum priority.

28
00:01:27,500 --> 00:01:30,710
That's why we are implementing a minimum binary heap over here.

29
00:01:30,710 --> 00:01:32,900
So let's call the methods in queue.

30
00:01:34,250 --> 00:01:35,180
And Dick.

31
00:01:35,180 --> 00:01:36,680
So let's just have placeholders.

32
00:01:36,680 --> 00:01:37,520
So this is NQ.

33
00:01:37,520 --> 00:01:39,050
This is DQ.

34
00:01:39,840 --> 00:01:45,630
Now for the NQ function, we will need to pass a value and a priority.

35
00:01:46,960 --> 00:01:47,530
All right.

36
00:01:47,530 --> 00:01:50,680
So let's go ahead and finish the NQ function.

37
00:01:50,680 --> 00:01:56,350
So once we call this and a value and a priority is passed we will need to create a new node.

38
00:01:56,350 --> 00:01:59,500
So let's say let node is equal to new.

39
00:01:59,500 --> 00:02:01,660
And then we have the node class right.

40
00:02:01,660 --> 00:02:04,420
So we say node and we say value and priority.

41
00:02:04,420 --> 00:02:06,190
We pass these two.

42
00:02:06,750 --> 00:02:11,820
So we create a new node and then we just push this to the array over here.

43
00:02:11,820 --> 00:02:12,000
Right.

44
00:02:12,000 --> 00:02:14,670
We are storing the priority queue as an array.

45
00:02:14,670 --> 00:02:16,530
So we just push it over here.

46
00:02:16,530 --> 00:02:18,270
And this will be an array of nodes.

47
00:02:18,270 --> 00:02:22,530
So we say this dot data dot push and we say node.

48
00:02:23,420 --> 00:02:23,750
All right.

49
00:02:23,750 --> 00:02:24,650
So we have pushed it.

50
00:02:24,650 --> 00:02:29,570
Now we need to place this node in its correct position based on the priority.

51
00:02:29,600 --> 00:02:29,990
Right.

52
00:02:29,990 --> 00:02:33,620
So the item with the minimum priority should be at the beginning.

53
00:02:33,620 --> 00:02:36,230
So it's just like a minimum binary heap right.

54
00:02:36,230 --> 00:02:39,410
So for this we will need to call the bubble up function.

55
00:02:39,410 --> 00:02:43,520
So let's say this dot bubble up and we need to write this function now.

56
00:02:43,520 --> 00:02:44,090
All right.

57
00:02:44,090 --> 00:02:46,580
So let's go ahead and write the function.

58
00:02:46,580 --> 00:02:50,000
And as far as the enqueue is concerned that's it.

59
00:02:50,000 --> 00:02:50,180
Right.

60
00:02:50,180 --> 00:02:52,520
So we have inserted it and we could return it right.

61
00:02:52,520 --> 00:02:54,950
So let's say we say return this.

62
00:02:54,950 --> 00:02:56,870
So at the end we return the priority queue.

63
00:02:56,870 --> 00:02:57,650
So that's it.

64
00:02:57,650 --> 00:03:00,860
Now let's go ahead and write the bubble up function.

65
00:03:03,140 --> 00:03:03,470
All right.

66
00:03:03,470 --> 00:03:07,910
So this will always deal with the element with the last element.

67
00:03:07,910 --> 00:03:08,090
Right.

68
00:03:08,090 --> 00:03:09,740
Because we are pushing it to the array.

69
00:03:09,740 --> 00:03:10,250
Right.

70
00:03:10,250 --> 00:03:16,700
So we can say that that particular index where we have just pushed that would be the length of the array

71
00:03:16,700 --> 00:03:17,270
minus one.

72
00:03:17,270 --> 00:03:17,450
Right.

73
00:03:17,450 --> 00:03:24,290
So let's say let id x is equal to this dot data dot length minus one.

74
00:03:24,560 --> 00:03:25,010
All right.

75
00:03:25,010 --> 00:03:27,380
And the value let's also take the value.

76
00:03:27,380 --> 00:03:29,570
So let's say const element.

77
00:03:30,390 --> 00:03:34,980
Is equal to this dot data at ID.

78
00:03:36,090 --> 00:03:40,980
So this is the value or this is the node which we just now pushed into the array.

79
00:03:40,980 --> 00:03:41,520
Right.

80
00:03:41,520 --> 00:03:42,090
All right.

81
00:03:42,090 --> 00:03:43,470
Now let's proceed.

82
00:03:43,470 --> 00:03:45,240
Now we will have a while loop.

83
00:03:45,240 --> 00:03:48,750
It's pretty similar to the binary heap question which we did.

84
00:03:48,750 --> 00:03:55,950
So while ID greater than zero we'll just loop through and we will break out if the priority is greater

85
00:03:55,950 --> 00:03:58,170
than the parent's priority.

86
00:03:58,170 --> 00:04:02,970
So if the node's priority is greater than its parent's priority right.

87
00:04:02,970 --> 00:04:08,430
So then we can break out because again remember over here we are treating priority one as the highest

88
00:04:08,430 --> 00:04:09,060
priority.

89
00:04:09,060 --> 00:04:11,610
And we are implementing a minimum binary heap.

90
00:04:11,610 --> 00:04:12,210
All right.

91
00:04:12,210 --> 00:04:14,400
So let's now find the parent ID.

92
00:04:14,550 --> 00:04:15,840
So let parent id.

93
00:04:17,150 --> 00:04:19,550
Is equal to math dot floor.

94
00:04:21,620 --> 00:04:25,100
And we just need to do ID minus one divided by two.

95
00:04:26,650 --> 00:04:27,460
We have discussed this.

96
00:04:27,460 --> 00:04:27,790
Right.

97
00:04:27,790 --> 00:04:32,110
So it's it's similar to what we've discussed in the binary heap section.

98
00:04:32,110 --> 00:04:34,330
So we get the parent index.

99
00:04:34,330 --> 00:04:36,460
Now we can just find the parent value.

100
00:04:36,460 --> 00:04:40,480
So let parent value is equal to this dot data.

101
00:04:41,440 --> 00:04:43,690
At parent index right.

102
00:04:43,690 --> 00:04:46,300
So parent ID so we get the value.

103
00:04:46,300 --> 00:04:47,050
All right.

104
00:04:47,050 --> 00:04:49,540
Now again remember this is the node.

105
00:04:49,540 --> 00:04:52,870
So let's just say parent is not just the value.

106
00:04:52,870 --> 00:04:54,280
That's the node actually.

107
00:04:54,400 --> 00:04:54,970
All right.

108
00:04:55,000 --> 00:05:00,940
Now what we need to check is we need to check the priority of this node and the priority of this node.

109
00:05:00,940 --> 00:05:02,980
So we need to compare these two priorities.

110
00:05:02,980 --> 00:05:04,300
So let's write that.

111
00:05:04,300 --> 00:05:13,210
So if the element's priority element dot priority is greater than equal to the parent's priority.

112
00:05:14,020 --> 00:05:19,420
If this is the case, then it's the node is in the correct, the element node is in the correct position

113
00:05:19,420 --> 00:05:20,530
and we can just break out.

114
00:05:20,530 --> 00:05:20,950
Right.

115
00:05:20,950 --> 00:05:26,710
But if this is not the case, that is if the element priority is less than the parent's priority then

116
00:05:26,710 --> 00:05:28,150
we need to swap these two.

117
00:05:28,180 --> 00:05:31,120
So we say this dot data at id.

118
00:05:32,670 --> 00:05:35,790
That should have the parent node.

119
00:05:35,820 --> 00:05:36,450
Right.

120
00:05:36,450 --> 00:05:43,590
And this dot data at parent index this should have the element node.

121
00:05:43,590 --> 00:05:46,230
So these are elements nodes right.

122
00:05:46,230 --> 00:05:48,390
So we have already stored these two.

123
00:05:48,390 --> 00:05:49,530
So we can just use that.

124
00:05:49,530 --> 00:05:51,090
So we have element over here.

125
00:05:51,090 --> 00:05:53,280
And we have also defined parent over here.

126
00:05:53,280 --> 00:05:53,460
Right.

127
00:05:53,460 --> 00:05:55,950
So we can just use them over here and here.

128
00:05:55,950 --> 00:05:57,840
And we swap the values.

129
00:05:57,840 --> 00:05:58,590
And that's it.

130
00:05:58,590 --> 00:06:03,300
And we just now have to change ID to parent ID right.

131
00:06:03,660 --> 00:06:04,320
That's it.

132
00:06:04,350 --> 00:06:06,420
Now it will keep looping right.

133
00:06:06,420 --> 00:06:07,170
It will keep looping.

134
00:06:07,170 --> 00:06:13,380
So if this is the case, if the element gets to the position where the priority of the parent is less

135
00:06:13,380 --> 00:06:16,380
than the element's priority, then we just break out.

136
00:06:16,380 --> 00:06:17,880
Otherwise we keep looping.

137
00:06:17,880 --> 00:06:20,220
And if it becomes zero then there is no parent.

138
00:06:20,220 --> 00:06:21,000
So we loop out.

139
00:06:21,000 --> 00:06:26,040
So this will keep on happening till ID as long as ID is greater than zero.

140
00:06:26,040 --> 00:06:29,010
Now once this is the once we are out of this we are done.

141
00:06:29,010 --> 00:06:31,320
So we should have it now.

142
00:06:31,320 --> 00:06:31,770
Ready.

143
00:06:31,770 --> 00:06:38,340
Now what we will do over here is let's go ahead and write the dequeue function also, because after

144
00:06:38,340 --> 00:06:40,020
that it's very easy to test.

145
00:06:40,020 --> 00:06:40,380
Right.

146
00:06:40,380 --> 00:06:47,220
So whenever we dequeue we should get the element with the highest with the lowest priority because priority

147
00:06:47,220 --> 00:06:48,540
one is the highest priority.

148
00:06:48,540 --> 00:06:55,020
So the element with the lowest numerical priority let me just call it as like that, because actually

149
00:06:55,020 --> 00:06:56,700
we are treating it as the highest priority.

150
00:06:56,700 --> 00:07:03,090
If you were to think of, um, any real life scenario, if a job has a priority one and another job

151
00:07:03,090 --> 00:07:07,950
has a priority two, now let's say we define that priority one is more important than priority two.

152
00:07:07,980 --> 00:07:09,690
So we take that out first, right.

153
00:07:09,690 --> 00:07:14,130
So we say on a functional basis that it is of higher priority.

154
00:07:14,130 --> 00:07:16,320
But numerically one is lower than two.

155
00:07:16,350 --> 00:07:16,890
All right.

156
00:07:16,890 --> 00:07:19,350
So let's go ahead and write our dequeue function.

157
00:07:19,350 --> 00:07:21,180
And then we'll test this out together.

158
00:07:21,910 --> 00:07:23,950
Now for the dequeue function.

159
00:07:23,950 --> 00:07:25,390
What is it that we need to do?

160
00:07:25,420 --> 00:07:28,840
We need to just find give the minimum value back right.

161
00:07:28,840 --> 00:07:31,630
So let's have a variable const min.

162
00:07:31,630 --> 00:07:33,190
Numerically it's minimum right.

163
00:07:33,190 --> 00:07:35,290
So this is this dot data.

164
00:07:35,290 --> 00:07:39,280
And that would be at index zero because that's how we are storing it over here.

165
00:07:39,280 --> 00:07:42,550
Right when we are enqueuing it and bubbling up we are ensuring this.

166
00:07:42,550 --> 00:07:43,000
Right.

167
00:07:43,000 --> 00:07:43,390
All right.

168
00:07:43,390 --> 00:07:49,720
So we just take the numerically minimum value, the item with minimum priority numerically out.

169
00:07:49,720 --> 00:07:54,220
And then we replace it with the last item.

170
00:07:54,220 --> 00:07:57,880
So let's say const last is equal to this dot data.

171
00:07:58,420 --> 00:08:00,520
And we just pop right.

172
00:08:00,520 --> 00:08:03,460
We just pop the last node from this array.

173
00:08:03,550 --> 00:08:06,880
And then if this is not the last element right.

174
00:08:06,880 --> 00:08:10,030
So again we have discussed this in the binary heap section as well.

175
00:08:10,030 --> 00:08:11,710
But let's quickly discuss it.

176
00:08:11,710 --> 00:08:17,290
Let's say there is a node over here and there's just one node left in the priority queue.

177
00:08:17,290 --> 00:08:19,000
Let's say that's like job one.

178
00:08:19,000 --> 00:08:19,960
That's the value.

179
00:08:19,960 --> 00:08:24,310
And let's say it has a priority of two and there's nothing else over here.

180
00:08:24,310 --> 00:08:26,290
Now what are we doing over here.

181
00:08:26,290 --> 00:08:28,750
Because this is this is the zeroth node right.

182
00:08:28,750 --> 00:08:31,120
So we are going to allocate this to min.

183
00:08:31,120 --> 00:08:33,220
And last is also going to be this one.

184
00:08:33,220 --> 00:08:36,520
So we are popping it out and we don't need to insert it back.

185
00:08:36,520 --> 00:08:36,700
Right.

186
00:08:36,700 --> 00:08:37,390
So we are done.

187
00:08:37,390 --> 00:08:39,820
So if there is just one node then we are done.

188
00:08:39,820 --> 00:08:44,560
And the priority queue after taking out the element over here will be empty.

189
00:08:44,560 --> 00:08:50,080
But if that is not the case, then we take out the last element, put it at the beginning, and then

190
00:08:50,080 --> 00:08:52,600
we bubble down to its correct position.

191
00:08:52,600 --> 00:08:54,550
So that's what we are trying to do.

192
00:08:54,550 --> 00:08:58,900
So let's say if uh this dot data dot length.

193
00:08:59,500 --> 00:09:03,640
Greater than zero right after popping out, right after popping the last element.

194
00:09:03,640 --> 00:09:08,050
If there is still something over there, then we say this dot data at zero.

195
00:09:09,640 --> 00:09:12,820
Is equal to the last element.

196
00:09:13,150 --> 00:09:14,170
See this node over here.

197
00:09:14,170 --> 00:09:14,920
Right last.

198
00:09:14,920 --> 00:09:16,540
So this is the last node.

199
00:09:16,540 --> 00:09:20,200
So we put that first and then we just call bubble down.

200
00:09:20,200 --> 00:09:21,130
So this dot.

201
00:09:22,880 --> 00:09:24,710
Bubble down, right?

202
00:09:25,300 --> 00:09:27,550
So that it gets to its correct position.

203
00:09:27,550 --> 00:09:30,250
And finally we will just return this node.

204
00:09:30,250 --> 00:09:31,780
So return min.

205
00:09:32,630 --> 00:09:34,730
And we are done with the DQ function.

206
00:09:34,730 --> 00:09:36,800
We just need to write the bubble down function.

207
00:09:36,800 --> 00:09:38,840
So let's go ahead and do that as well now.

208
00:09:38,840 --> 00:09:40,070
So bubble down.

209
00:09:42,740 --> 00:09:43,220
All right.

210
00:09:43,220 --> 00:09:45,620
Now, what is it that we have to do over here?

211
00:09:45,620 --> 00:09:52,160
We have to find its two children, and then we have to compare the elements priority and the children's

212
00:09:52,160 --> 00:09:52,700
priority.

213
00:09:52,700 --> 00:10:00,260
Right now, if the child's priority is less than the elements priority, then we have to swap it, right?

214
00:10:00,260 --> 00:10:04,340
Because we need the the items with lower priority.

215
00:10:04,340 --> 00:10:05,510
We want them up.

216
00:10:07,110 --> 00:10:07,500
All right.

217
00:10:07,500 --> 00:10:10,860
So let's go ahead and implement our bubble down function.

218
00:10:10,860 --> 00:10:17,250
Let's say let ID is equal to zero because over here we are always going to start at the root node because

219
00:10:17,250 --> 00:10:20,790
we are setting the node which we took out which is the last node.

220
00:10:20,790 --> 00:10:22,380
We are setting it at the zeroth index.

221
00:10:22,380 --> 00:10:22,650
Right.

222
00:10:22,650 --> 00:10:24,960
So we have to bubble down from here only.

223
00:10:24,960 --> 00:10:26,760
So let id is equal to zero.

224
00:10:26,760 --> 00:10:30,210
And to make our code a bit shorter let's just write.

225
00:10:30,210 --> 00:10:33,960
Let length is equal to this dot data dot length.

226
00:10:35,480 --> 00:10:36,020
All right.

227
00:10:36,020 --> 00:10:38,510
Now let's also find the element right.

228
00:10:38,510 --> 00:10:39,650
So let element.

229
00:10:41,280 --> 00:10:45,960
Is equal to this dot data at index zero.

230
00:10:46,140 --> 00:10:49,320
That's the element which just got inserted.

231
00:10:49,320 --> 00:10:50,310
This one over here.

232
00:10:50,340 --> 00:10:51,120
All right.

233
00:10:51,120 --> 00:10:53,070
Now let's go ahead and loop.

234
00:10:53,070 --> 00:10:54,600
We need to have a while loop.

235
00:10:54,600 --> 00:10:54,840
All right.

236
00:10:54,840 --> 00:10:56,160
So let's write while true.

237
00:10:56,160 --> 00:11:02,610
And we will break out of this when the node the element is at its right priority level.

238
00:11:02,610 --> 00:11:02,910
All right.

239
00:11:02,910 --> 00:11:04,440
So we'll see that.

240
00:11:04,440 --> 00:11:08,670
And again remember it's pretty similar to the binary heap that we have already discussed.

241
00:11:08,670 --> 00:11:12,600
Now let's go ahead and find its left and right child.

242
00:11:12,600 --> 00:11:16,650
So for this let's find the index let's say left child.

243
00:11:17,670 --> 00:11:22,950
ID is equal to two into id plus one.

244
00:11:23,560 --> 00:11:31,960
And let right child ID is equal to two into id plus two.

245
00:11:31,990 --> 00:11:35,590
So we have found the two indices of the children.

246
00:11:35,590 --> 00:11:39,640
Now let's just make variables for the left child and the right child.

247
00:11:39,640 --> 00:11:43,030
So let left child comma right child.

248
00:11:44,530 --> 00:11:45,220
All right.

249
00:11:45,220 --> 00:11:47,890
Now we also need a variable.

250
00:11:47,890 --> 00:11:54,610
Let's call it smallest over here to understand to know whether we need to make a swap or not, or whether

251
00:11:54,610 --> 00:11:56,080
the element is in the right place.

252
00:11:56,080 --> 00:11:57,280
And we can just break out.

253
00:11:57,280 --> 00:12:00,490
So we will track that with this variable smallest over here.

254
00:12:00,490 --> 00:12:02,560
So initially we we make it just null.

255
00:12:02,590 --> 00:12:08,080
Now we are going to check whether the left child index is less than the length.

256
00:12:08,110 --> 00:12:11,290
If that is so then this is a valid index.

257
00:12:11,290 --> 00:12:12,400
That means there is an element.

258
00:12:12,400 --> 00:12:14,110
There is a child over there right.

259
00:12:14,110 --> 00:12:18,370
So we will just find the left child which will be this dot data.

260
00:12:19,350 --> 00:12:20,490
At the index.

261
00:12:20,490 --> 00:12:21,990
Left child index.

262
00:12:22,890 --> 00:12:23,340
All right.

263
00:12:23,340 --> 00:12:30,450
Now we are going to compare the priority of this node and the priority of this element node over here.

264
00:12:30,480 --> 00:12:30,810
All right.

265
00:12:30,810 --> 00:12:32,910
So let's go ahead and check do that over here.

266
00:12:33,540 --> 00:12:37,410
If left child dot priority.

267
00:12:38,010 --> 00:12:39,480
If this priority.

268
00:12:40,620 --> 00:12:41,730
Is less or greater.

269
00:12:41,730 --> 00:12:42,000
What?

270
00:12:42,000 --> 00:12:43,080
What do you think it should be?

271
00:12:43,470 --> 00:12:43,680
We are.

272
00:12:43,680 --> 00:12:48,210
We are going to check whether it is less right because we are we we are trying to understand whether

273
00:12:48,210 --> 00:12:49,920
we need to make a swap or not.

274
00:12:49,920 --> 00:12:52,890
So if it is less, then we need to make a swap, right?

275
00:12:52,890 --> 00:12:57,450
So if it is less than element dot priority then we need to make a swap.

276
00:12:57,450 --> 00:12:59,190
So we will change this.

277
00:12:59,220 --> 00:13:01,020
Initially smallest was null.

278
00:13:01,020 --> 00:13:06,450
So if this is the case then we will say smallest is equal to left child index.

279
00:13:06,450 --> 00:13:09,480
So that indicates that yes a swap is required.

280
00:13:09,480 --> 00:13:11,520
Now we do the same thing for right child.

281
00:13:11,520 --> 00:13:14,280
So let's check whether the there is a right child.

282
00:13:14,280 --> 00:13:18,180
So we check whether right child index is less than the length.

283
00:13:18,660 --> 00:13:21,570
If that is the case yes there is a valid child over there.

284
00:13:21,570 --> 00:13:23,190
So let's find the right child.

285
00:13:23,190 --> 00:13:27,630
So right child will be this dot data at right child index.

286
00:13:28,730 --> 00:13:29,180
All right.

287
00:13:29,180 --> 00:13:35,540
Now we need to know whether we need to swap with this child or with this child.

288
00:13:35,540 --> 00:13:42,110
So there are two possibilities, as by this time, one possibility is that smallest is still null,

289
00:13:42,140 --> 00:13:42,680
right.

290
00:13:42,680 --> 00:13:46,400
So that is a possibility or smallest could be left child index.

291
00:13:46,400 --> 00:13:48,050
So let's write that over here.

292
00:13:48,050 --> 00:13:50,060
Parallelly we will write that and discuss it.

293
00:13:50,750 --> 00:13:51,230
All right.

294
00:13:51,230 --> 00:13:53,960
So if smallest is null right.

295
00:13:53,960 --> 00:13:55,160
Let me just write that over here.

296
00:13:55,160 --> 00:14:01,010
If smallest is equal to null that means that it did not come over here.

297
00:14:01,010 --> 00:14:01,250
Right.

298
00:14:01,250 --> 00:14:04,340
So it was null initially and it did not come over here.

299
00:14:04,340 --> 00:14:08,180
That means the left child with respect to the element is in the right position.

300
00:14:08,180 --> 00:14:13,370
And we don't need to make any swaps, but we need to check whether the right child is in the right position.

301
00:14:13,370 --> 00:14:17,930
So over here we will check whether right child dot priority.

302
00:14:19,770 --> 00:14:22,830
Is less than element priority.

303
00:14:24,470 --> 00:14:30,380
Now, if this is the case, even though the left child is correct with respect to the element, the

304
00:14:30,380 --> 00:14:31,490
right child is not correct.

305
00:14:31,490 --> 00:14:33,290
So we need to make a swap right now.

306
00:14:33,290 --> 00:14:37,550
This could be a possibility or another possibility is that.

307
00:14:41,670 --> 00:14:43,110
Let's just make some space.

308
00:14:43,110 --> 00:14:43,470
Yep.

309
00:14:43,470 --> 00:14:47,400
So another possibility is that smallest is not null.

310
00:14:47,400 --> 00:14:52,290
That means smallest has been changed over here and smallest now is equal to left child index.

311
00:14:52,290 --> 00:14:53,940
So let's write that parallelly.

312
00:14:53,940 --> 00:14:56,550
So smallest is not equal to null.

313
00:14:57,540 --> 00:15:00,690
Now it means that we have to make a swap.

314
00:15:00,690 --> 00:15:01,380
Definitely.

315
00:15:01,380 --> 00:15:04,740
But now we need to identify which is the correct element to swap.

316
00:15:04,740 --> 00:15:07,950
Should I swap the element with the left child or with the right child?

317
00:15:07,950 --> 00:15:12,420
So if in this case if the right child priority.

318
00:15:14,960 --> 00:15:18,110
Is less than the left child priority right?

319
00:15:18,110 --> 00:15:20,360
So the left child priority.

320
00:15:21,200 --> 00:15:24,410
In this case, we swap with the right child right.

321
00:15:24,410 --> 00:15:29,780
So we are trying to identify the element with the lowest priority because we want that to be the parent.

322
00:15:29,780 --> 00:15:30,140
Right.

323
00:15:30,140 --> 00:15:32,270
So we are going to check it like this over here.

324
00:15:32,810 --> 00:15:37,610
Now if any one of these conditions is true let me just add a bracket over here.

325
00:15:37,610 --> 00:15:42,290
Then we set smallest is equal to right child index.

326
00:15:43,940 --> 00:15:44,510
All right.

327
00:15:44,510 --> 00:15:51,110
So by this time when we reach over here, when we are done with these two areas, right when we have

328
00:15:51,110 --> 00:15:54,470
checked this and this, we know whether we need to make a swap or not.

329
00:15:54,470 --> 00:15:55,730
So that is one thing we know.

330
00:15:55,730 --> 00:16:01,280
And if we need to make a swap, we know whether we need to swap the element with the left child or with

331
00:16:01,280 --> 00:16:02,120
the right child.

332
00:16:02,300 --> 00:16:02,750
All right.

333
00:16:02,750 --> 00:16:06,230
So now let's go ahead and check whether smallest is still null.

334
00:16:06,230 --> 00:16:11,990
If smallest is equal to null, that means that element is in the right position.

335
00:16:11,990 --> 00:16:13,370
And we can just break out.

336
00:16:13,370 --> 00:16:13,550
Right.

337
00:16:13,550 --> 00:16:15,020
We don't need to make any swaps.

338
00:16:15,020 --> 00:16:15,770
So we are done.

339
00:16:15,770 --> 00:16:17,390
The element is in the right position.

340
00:16:17,390 --> 00:16:19,820
So it has bubbled down to the correct position.

341
00:16:19,820 --> 00:16:20,030
Right.

342
00:16:20,030 --> 00:16:21,110
And we can break out.

343
00:16:21,110 --> 00:16:24,170
But if this is not the case then we need to swap.

344
00:16:24,170 --> 00:16:24,560
All right.

345
00:16:24,560 --> 00:16:27,080
So if this is not the case let's go ahead and swap.

346
00:16:27,880 --> 00:16:31,420
So we can say this dot data at ID.

347
00:16:35,920 --> 00:16:39,400
Is equal to this dot data at smallest, right?

348
00:16:41,640 --> 00:16:49,140
Now this would either be the right child index or the left child index, depending on which is the best,

349
00:16:49,140 --> 00:16:51,330
which has the smaller prior priority.

350
00:16:51,360 --> 00:16:51,960
All right.

351
00:16:51,960 --> 00:16:54,240
So we we put that value over here.

352
00:16:54,240 --> 00:16:56,250
Then we say this dot data.

353
00:16:57,380 --> 00:16:58,580
At smallest.

354
00:16:59,370 --> 00:17:00,900
Is equal to element, right.

355
00:17:00,900 --> 00:17:02,490
We have already stored that over here.

356
00:17:02,490 --> 00:17:03,930
So element is.

357
00:17:04,710 --> 00:17:05,910
This one over here.

358
00:17:06,000 --> 00:17:07,470
That was the initial node.

359
00:17:07,470 --> 00:17:07,770
Right.

360
00:17:07,770 --> 00:17:10,740
So we put that to this dot data at smallest.

361
00:17:10,740 --> 00:17:12,510
Now we have swapped these two values.

362
00:17:12,510 --> 00:17:15,810
Now we just need to set ID is equal to smallest.

363
00:17:19,960 --> 00:17:26,560
This is required because once we have done a swap, we have to check that node with its parent, right.

364
00:17:26,560 --> 00:17:28,390
So it has to keep happening.

365
00:17:28,390 --> 00:17:35,800
The loop has to go on till the node is at its right place, such that the parent's priority is not less

366
00:17:35,800 --> 00:17:37,120
than the child's priority.

367
00:17:37,120 --> 00:17:38,530
So that would happen over here.

368
00:17:38,530 --> 00:17:42,040
And when we find smallest is equal to null, we will break out.

369
00:17:42,550 --> 00:17:43,330
So that is it.

370
00:17:43,330 --> 00:17:46,630
So we have successfully coded the bubble down as well.

371
00:17:46,630 --> 00:17:48,970
Now let's go ahead and test our function.

372
00:17:48,970 --> 00:17:50,680
So we have written the n q function.

373
00:17:50,680 --> 00:17:54,280
And we needed the bubble up function along with the n q function.

374
00:17:54,280 --> 00:17:56,350
And we have written the dequeue function.

375
00:17:56,350 --> 00:17:58,330
And we needed bubble down over here as well.

376
00:17:58,330 --> 00:17:58,720
All right.

377
00:17:58,720 --> 00:18:00,490
Now let's go ahead and test it.

378
00:18:00,610 --> 00:18:02,110
Now let's say let.

379
00:18:03,440 --> 00:18:05,630
Priority queue.

380
00:18:06,860 --> 00:18:09,650
Is equal to new priority queue.

381
00:18:10,880 --> 00:18:15,050
Now let's go ahead and NQ five jobs with different priorities.

382
00:18:15,050 --> 00:18:16,370
So let's say.

383
00:18:18,170 --> 00:18:21,080
Prior q dot nq.

384
00:18:22,550 --> 00:18:25,310
And let the value be job one.

385
00:18:27,210 --> 00:18:28,620
And the priority is three.

386
00:18:28,620 --> 00:18:30,990
So it's like a to do list, right?

387
00:18:30,990 --> 00:18:34,440
A to do list with different jobs and different priorities.

388
00:18:34,440 --> 00:18:39,990
And we define that priority one is the most important thing for us which is most urgent to be done.

389
00:18:39,990 --> 00:18:40,560
All right.

390
00:18:40,560 --> 00:18:44,250
So let's have the second job and let it have a priority of four.

391
00:18:45,250 --> 00:18:47,140
And then we have the third job.

392
00:18:47,230 --> 00:18:49,390
Let it have a priority of one.

393
00:18:51,410 --> 00:18:53,210
Then we have the fourth job.

394
00:18:53,210 --> 00:18:55,340
Let it have a priority of two.

395
00:18:57,290 --> 00:18:58,820
And then we have one more job.

396
00:18:58,820 --> 00:19:00,290
This is job five.

397
00:19:00,290 --> 00:19:01,730
Let it have a priority of one.

398
00:19:01,730 --> 00:19:02,240
All right.

399
00:19:02,240 --> 00:19:04,370
So let's go ahead and run our code now.

400
00:19:05,870 --> 00:19:06,290
All right.

401
00:19:06,290 --> 00:19:10,580
So we have n cubed these five nodes to our priority queue.

402
00:19:10,700 --> 00:19:15,440
Now let's keep this over here so that we can test whether it's working.

403
00:19:19,400 --> 00:19:20,120
All right.

404
00:19:20,600 --> 00:19:25,880
Now, how should it be initially when let's just parallelly create it probably over here.

405
00:19:25,880 --> 00:19:26,270
Right.

406
00:19:26,270 --> 00:19:29,000
So let me just use these numbers only.

407
00:19:29,000 --> 00:19:29,240
Right.

408
00:19:29,240 --> 00:19:31,220
So initially we have three.

409
00:19:31,220 --> 00:19:32,630
So I have three.

410
00:19:34,080 --> 00:19:35,250
Let's just write it over here.

411
00:19:35,250 --> 00:19:37,230
Then when we end Q four.

412
00:19:37,260 --> 00:19:37,560
Right.

413
00:19:37,560 --> 00:19:39,870
So four will be added over here.

414
00:19:40,840 --> 00:19:45,100
And then you can see that three has a lower priority than four.

415
00:19:45,100 --> 00:19:45,730
So it's fine.

416
00:19:45,730 --> 00:19:47,380
So it's in its correct position right.

417
00:19:47,410 --> 00:19:50,170
Next we insert job three which has priority one.

418
00:19:50,170 --> 00:19:52,060
So that's inserted over here.

419
00:19:52,060 --> 00:19:57,520
Right now we can see that the priority of three is greater than one.

420
00:19:57,520 --> 00:19:58,930
So we would have to swap it right.

421
00:19:58,930 --> 00:20:02,320
So we get one over here and we will get three over here.

422
00:20:03,040 --> 00:20:03,730
All right.

423
00:20:03,730 --> 00:20:07,030
And then after that we insert job with priority two.

424
00:20:07,060 --> 00:20:08,620
So that's over here.

425
00:20:10,750 --> 00:20:11,350
All right.

426
00:20:11,350 --> 00:20:15,280
Now, when we check these two, the priority of four is higher, right.

427
00:20:15,280 --> 00:20:16,330
So we need to swap them.

428
00:20:16,330 --> 00:20:19,900
So we get two over here and we get four over here.

429
00:20:20,710 --> 00:20:23,800
And when we compare one and two, it's in the correct position.

430
00:20:23,800 --> 00:20:25,090
Then what?

431
00:20:25,090 --> 00:20:26,170
We have inserted this one.

432
00:20:26,170 --> 00:20:28,510
Then we insert another job with priority five.

433
00:20:28,510 --> 00:20:29,320
Priority one.

434
00:20:29,320 --> 00:20:29,500
Right.

435
00:20:29,500 --> 00:20:30,940
So it will it will come over here.

436
00:20:31,570 --> 00:20:32,770
It comes over here.

437
00:20:33,980 --> 00:20:37,610
Now when we compare this and its parent, we have to swap, right?

438
00:20:37,610 --> 00:20:38,840
Because this is a higher priority.

439
00:20:38,840 --> 00:20:43,100
So we get one over here and we get two over here.

440
00:20:43,100 --> 00:20:43,850
And that's it.

441
00:20:43,850 --> 00:20:44,090
Right.

442
00:20:44,090 --> 00:20:47,300
So again with with respect to this this is equal priority.

443
00:20:47,300 --> 00:20:48,410
So we don't need to swap.

444
00:20:48,410 --> 00:20:49,940
So this is how it should look.

445
00:20:49,940 --> 00:20:53,600
That means we should have one then one three and four and two.

446
00:20:53,630 --> 00:20:56,720
So let's look at the data over here our output.

447
00:20:57,110 --> 00:20:58,730
So this is the expectation.

448
00:20:58,730 --> 00:21:01,430
So we have job three which is priority one.

449
00:21:01,430 --> 00:21:02,900
So that's correct.

450
00:21:02,900 --> 00:21:03,740
Job three right.

451
00:21:03,740 --> 00:21:04,880
It has priority one.

452
00:21:04,880 --> 00:21:06,380
So that's this one over here.

453
00:21:06,380 --> 00:21:12,680
After that we have job five which also has priority one which is this one over here which is correct.

454
00:21:12,680 --> 00:21:14,930
After this we should get this one with priority three.

455
00:21:14,930 --> 00:21:15,230
Right.

456
00:21:15,230 --> 00:21:16,160
Which is job one.

457
00:21:16,160 --> 00:21:16,430
Yes.

458
00:21:16,430 --> 00:21:17,600
Job one with priority three.

459
00:21:17,600 --> 00:21:18,260
That's correct.

460
00:21:18,260 --> 00:21:22,010
Then we should get job with priority four which is job two.

461
00:21:22,040 --> 00:21:23,180
So we have job two over here.

462
00:21:23,180 --> 00:21:24,170
Priority four.

463
00:21:24,170 --> 00:21:29,090
And then we have job four over here which is which has a priority of two.

464
00:21:29,120 --> 00:21:30,950
So yes our output is correct.

465
00:21:30,950 --> 00:21:31,340
Right.

466
00:21:31,340 --> 00:21:33,950
So again let me just comment this out.

467
00:21:38,900 --> 00:21:39,260
All right.

468
00:21:39,290 --> 00:21:43,130
Now let's go ahead and call the DQ function over here.

469
00:21:43,130 --> 00:21:47,570
Now we should be getting always the job with highest priority.

470
00:21:47,960 --> 00:21:49,340
And with highest priority.

471
00:21:49,340 --> 00:21:55,190
We mean numerically the lowest value because we have defined priority one to be the highest priority.

472
00:21:55,190 --> 00:21:55,730
All right.

473
00:21:55,730 --> 00:21:57,170
So let's go ahead and do that.

474
00:21:57,170 --> 00:21:57,950
So we have.

475
00:22:00,160 --> 00:22:03,520
Prior q and then dot d q.

476
00:22:06,400 --> 00:22:10,210
Now it's giving me job three with priority one, which is correct.

477
00:22:10,240 --> 00:22:11,680
Now let me do it again.

478
00:22:11,680 --> 00:22:14,860
So I get job five with priority one, which is correct.

479
00:22:15,160 --> 00:22:19,090
If I do it again I get job four with priority two, which is correct, right?

480
00:22:19,090 --> 00:22:24,160
This is the next, uh, after removing these two are gone among three, four, two, two is the minimum.

481
00:22:24,160 --> 00:22:26,710
So yes, our function, our dequeue function is working.

482
00:22:26,710 --> 00:22:27,250
Correct.

483
00:22:27,280 --> 00:22:29,560
If I call it again I get priority three.

484
00:22:29,560 --> 00:22:31,840
And if I do it again I get priority four.

485
00:22:31,840 --> 00:22:35,560
Now if I do it, there's nothing because the priority queue is empty.

486
00:22:35,560 --> 00:22:39,520
So yes, our function our enqueue and dequeue functions are working.

487
00:22:39,520 --> 00:22:44,140
Now we have returned the enqueue function and we have used bubble up over here.

488
00:22:44,140 --> 00:22:48,430
We have written the dequeue function and we have used bubble down in the dequeue function.

489
00:22:48,430 --> 00:22:54,580
Let's take a sample input and again walk through the code and also relook at the complexity analysis

490
00:22:54,580 --> 00:22:55,750
of this solution.