1
00:00:01,320 --> 00:00:02,050
Hi, everyone.

2
00:00:02,070 --> 00:00:07,370
So in the last video, reimplemented, our only minimum priority queue, and we're this close to what

3
00:00:07,380 --> 00:00:07,680
is he?

4
00:00:08,760 --> 00:00:15,720
So if you remember the time complexity of Heap's art was and Logan and the space complexity was big

5
00:00:15,780 --> 00:00:16,379
of an.

6
00:00:18,060 --> 00:00:24,090
Now, in this video, we wanted to discuss such an algorithm such that the space complexity should become

7
00:00:24,090 --> 00:00:24,450
bigger.

8
00:00:24,480 --> 00:00:26,800
Even so, that means constrained space.

9
00:00:27,420 --> 00:00:29,700
So why the space complexity was big often.

10
00:00:29,710 --> 00:00:36,210
So the space complexity was big, often because we were creating a vector and this vector became so

11
00:00:36,210 --> 00:00:39,020
distracted, was actually containing our minimum hype.

12
00:00:39,660 --> 00:00:43,120
So this vector was containing the elements of our minimum heap.

13
00:00:43,530 --> 00:00:45,810
So that's why you do this with the space.

14
00:00:45,810 --> 00:00:47,400
Complexity was big often.

15
00:00:48,520 --> 00:00:56,920
Now, this input that is given, so this input that is actually given to us now, what will do so in

16
00:00:56,920 --> 00:00:57,720
this algorithm?

17
00:00:57,730 --> 00:01:03,370
So in this video, in this lesson, what we will do so I am going to convert this area into a minimum

18
00:01:03,380 --> 00:01:03,660
heap.

19
00:01:04,180 --> 00:01:09,610
So I'm going to build a minimum heap inside this area only.

20
00:01:10,820 --> 00:01:17,620
So if we're able to build a minimum heap in this area only, basically you are going to change this

21
00:01:17,620 --> 00:01:19,420
area into a minimum heap.

22
00:01:19,930 --> 00:01:24,940
So if you are able to do that, then your time, complexity aside, your space complexity will become

23
00:01:24,940 --> 00:01:28,430
big often because you are not you will not take any extra space.

24
00:01:29,440 --> 00:01:35,150
So this is called in place or so in place means you will not take any extra space.

25
00:01:35,150 --> 00:01:36,790
So the space complexity will be big.

26
00:01:36,790 --> 00:01:39,490
Goffman and approach is very simple.

27
00:01:39,760 --> 00:01:44,890
So instead of taking a new area, a new vector for building the minimum, what material?

28
00:01:45,040 --> 00:01:48,670
We will convert the input into a minimum.

29
00:01:48,940 --> 00:01:52,570
So we will build minimum Hipp inside this given area only.

30
00:01:52,570 --> 00:01:58,540
So I'm going to change the input very simple, so that we can achieve constant space.

31
00:01:59,200 --> 00:02:01,000
So now let's discuss the algorithm.

32
00:02:01,360 --> 00:02:06,140
So if you remember the heap short, so he has two parts.

33
00:02:07,640 --> 00:02:10,449
So first part was basically building the minimum up.

34
00:02:12,050 --> 00:02:17,960
And the second part was actually to call the remove minimum function and times and is basically the

35
00:02:17,990 --> 00:02:18,720
size of the area.

36
00:02:19,040 --> 00:02:23,470
So he thought was to part first part is to build them up.

37
00:02:23,720 --> 00:02:29,240
And second part was to remove minimum function and times so that we can get the minimum element.

38
00:02:30,200 --> 00:02:31,350
And simple.

39
00:02:32,300 --> 00:02:38,460
So now let us first discuss how can we build minimum help inside this input area?

40
00:02:39,470 --> 00:02:41,220
So now let us try to understand.

41
00:02:41,930 --> 00:02:43,220
So let's take this example.

42
00:02:43,220 --> 00:02:44,780
Only 10, five eight one four.

43
00:02:46,960 --> 00:02:47,950
So, Avineri.

44
00:02:52,810 --> 00:02:59,270
So the first element is 10, then I have five, then hit, then one, and then we have four.

45
00:02:59,440 --> 00:03:00,440
So this is the input.

46
00:03:00,440 --> 00:03:02,080
That argument was simple.

47
00:03:03,100 --> 00:03:07,870
Now what we are going to do, so we will assume that this part is actually.

48
00:03:09,890 --> 00:03:13,580
So this part, we will assume that this part has been converted into a minimum.

49
00:03:14,550 --> 00:03:20,490
We will assume this and the rest of the and minus one element is actually our answer today.

50
00:03:21,020 --> 00:03:22,600
So we are going to assume this.

51
00:03:23,240 --> 00:03:30,350
So if this is a part of heap, so that means this is Maitri simple now one by one.

52
00:03:30,950 --> 00:03:37,390
But we will do we will take the element one by one inside the heap, just like we used to do in Oceanside.

53
00:03:37,940 --> 00:03:42,650
So what we will do now put five to now take five into consideration.

54
00:03:43,250 --> 00:03:51,260
So now what I'm saying so this part I'm saying this part is part of my hip and this is normal, just

55
00:03:51,260 --> 00:03:52,220
our unsorted area.

56
00:03:53,210 --> 00:03:56,720
So basically you are starting five, so let's insert five.

57
00:03:57,770 --> 00:04:03,110
Now, after inserting five CBD property has been satisfied, but again, you have to satisfy the many

58
00:04:03,110 --> 00:04:05,140
properties or what you have to do, you will swap.

59
00:04:05,690 --> 00:04:07,130
So I will step down in five.

60
00:04:09,560 --> 00:04:14,220
And here, the slapping will take place over here and will come, and here it will come.

61
00:04:14,750 --> 00:04:20,970
So we have done this thing many, many times morning to explain again and now what we will do.

62
00:04:21,140 --> 00:04:23,240
We will take one more element into consideration.

63
00:04:23,270 --> 00:04:26,180
So now take it into consideration.

64
00:04:27,270 --> 00:04:34,260
So now what I'm saying so I'm saying these three elements are now part of my hip and these two elements

65
00:04:34,260 --> 00:04:39,200
are actually unsorted elements, so I have one more element to it.

66
00:04:39,210 --> 00:04:43,290
So let us insert it so it will be inserted here.

67
00:04:43,920 --> 00:04:47,310
Now, this is Sebti and this is also I mean, I'm hip, simple.

68
00:04:48,870 --> 00:04:50,530
So this is it.

69
00:04:51,300 --> 00:04:52,920
Now, let's insert one more element.

70
00:04:52,950 --> 00:04:58,210
So this time I'm taking one into consideration, so let's take one into consideration.

71
00:04:58,590 --> 00:05:02,100
So what will happen when will be present at this partition?

72
00:05:02,550 --> 00:05:05,960
So our CBT is correct, but this is not a minimum.

73
00:05:06,180 --> 00:05:09,320
So, again, we will do the comparison and we will do the typing part.

74
00:05:09,810 --> 00:05:11,160
So I will have one in 10.

75
00:05:11,280 --> 00:05:13,840
So then we'll come here and one will come here.

76
00:05:14,310 --> 00:05:19,650
So here, what will happen so is going to come here and one is going to come here.

77
00:05:19,710 --> 00:05:20,280
Simple.

78
00:05:21,690 --> 00:05:26,490
Again, what we will do I will not stop here, I will I will have to compare one in five, so compare

79
00:05:26,490 --> 00:05:30,740
one in five and then you will slap so five will come here and one will come here.

80
00:05:30,750 --> 00:05:33,440
So similarly, I'm swapping one in five.

81
00:05:34,170 --> 00:05:37,430
So one is going to come here and five is going to come here.

82
00:05:37,560 --> 00:05:38,130
Simple.

83
00:05:39,740 --> 00:05:42,810
Now we have to take the last element into consideration also.

84
00:05:43,220 --> 00:05:49,250
OK, so we have already took one element, one into consideration now that us look forward into consideration.

85
00:05:50,000 --> 00:05:53,000
So Element four will be inserted at this position.

86
00:05:53,540 --> 00:05:55,040
Again, we will do this.

87
00:05:55,430 --> 00:05:57,250
We will do the comparison and disappointing.

88
00:05:57,620 --> 00:05:59,420
So far, it is actually less than five.

89
00:05:59,450 --> 00:06:00,710
So again, you have to do shopping.

90
00:06:00,990 --> 00:06:03,340
So I will come here and Ford will come here.

91
00:06:03,740 --> 00:06:04,800
So it is five.

92
00:06:04,850 --> 00:06:06,360
So here we have four.

93
00:06:06,830 --> 00:06:08,640
And here we have five.

94
00:06:09,620 --> 00:06:11,150
Now compare Ford with one.

95
00:06:11,390 --> 00:06:12,400
So it is correct.

96
00:06:13,070 --> 00:06:14,450
Now we will stop at this point.

97
00:06:14,480 --> 00:06:16,040
So finally, what is my ETA?

98
00:06:16,370 --> 00:06:22,650
So the shape of is one, then I have element four, then I have element eight, then I have element

99
00:06:22,670 --> 00:06:25,300
then and then I have element five.

100
00:06:26,120 --> 00:06:27,170
So this is my.

101
00:06:28,270 --> 00:06:35,410
Minimum heap, and similarly, you can see this, so this is one, then I have four, then I have eight

102
00:06:35,410 --> 00:06:41,820
and then I have 10 and then I have five simple one four, eight, 10, five.

103
00:06:42,310 --> 00:06:43,440
Now you can notice.

104
00:06:43,450 --> 00:06:46,060
So basically this area is not a certain area.

105
00:06:47,020 --> 00:06:48,430
So why this has not sorted?

106
00:06:48,730 --> 00:06:51,820
Because you remember that he has two parts.

107
00:06:52,970 --> 00:06:58,640
He was having two parts, first is building the minimum hip and second is actually to call the Raymore

108
00:06:58,640 --> 00:07:00,050
minimum function and times.

109
00:07:00,470 --> 00:07:02,030
So we have done the first part.

110
00:07:02,840 --> 00:07:04,440
We have done the first part.

111
00:07:04,460 --> 00:07:07,320
So our minimum hip is ready and we converted.

112
00:07:07,820 --> 00:07:08,600
So what do we do?

113
00:07:09,050 --> 00:07:12,290
So we converted this in, put it into a minimum hip.

114
00:07:13,130 --> 00:07:14,350
We can order this input.

115
00:07:15,290 --> 00:07:16,220
And what was the element?

116
00:07:16,250 --> 00:07:22,350
So it was one four eight, then five one four eight and then 10 and then five.

117
00:07:23,000 --> 00:07:25,160
So we are using constant extra space.

118
00:07:25,850 --> 00:07:28,430
We just build the minimum hip in this area.

119
00:07:28,430 --> 00:07:30,590
Only no need for any extra space.

120
00:07:31,460 --> 00:07:34,430
Now we have to do the second part, remove minimum.

121
00:07:34,640 --> 00:07:39,560
So we will apply the removal minimum function in this area and times.

122
00:07:40,870 --> 00:07:46,450
Now, after doing this, after performing a minimum function and times everyday, we'll get get to.

123
00:07:47,980 --> 00:07:54,100
So let's see, so this is my area one four eight nine five, so let's do it.

124
00:07:58,200 --> 00:08:01,440
So I have one, then four, then eight.

125
00:08:02,280 --> 00:08:04,620
Then 10 and then five.

126
00:08:05,560 --> 00:08:10,870
And by this time, you should be very well aware of how removed minimum function work.

127
00:08:11,710 --> 00:08:13,240
So, again, you can.

128
00:08:14,230 --> 00:08:21,950
Let us build a trials also one four, then eight, then 10 and then five, simple.

129
00:08:22,360 --> 00:08:27,610
So what we have to do, we have to remove the minimum function five times because the size of the arrays,

130
00:08:27,610 --> 00:08:27,970
five.

131
00:08:28,300 --> 00:08:28,900
Simple.

132
00:08:29,890 --> 00:08:30,850
So let's start.

133
00:08:31,690 --> 00:08:35,340
So what removing minimum function will do so it will remove the minimum element.

134
00:08:35,350 --> 00:08:37,200
So remove the minimum element.

135
00:08:37,510 --> 00:08:40,330
So for removing the minimum element, first work is to swap.

136
00:08:40,330 --> 00:08:41,780
So I will swap one in five.

137
00:08:42,520 --> 00:08:45,950
So what will happen when will come here and five will come here.

138
00:08:46,270 --> 00:08:50,180
Now the second step of removing minimum function is to delete the last element.

139
00:08:50,650 --> 00:08:53,110
So this is basically deleting.

140
00:08:53,120 --> 00:08:56,470
So this works in normal, normal, remove minimum function.

141
00:08:57,670 --> 00:09:00,430
But in our case we do not have to remove elements.

142
00:09:00,970 --> 00:09:02,610
So this step is actually wrong.

143
00:09:03,220 --> 00:09:04,600
We will not remove element.

144
00:09:04,610 --> 00:09:06,940
We will just assume that element has been removed.

145
00:09:07,810 --> 00:09:11,120
I'm repeating myself what happens in actual algorithm.

146
00:09:11,140 --> 00:09:13,150
So actually no function what it will do.

147
00:09:13,150 --> 00:09:15,840
So it will up the first element with the last element.

148
00:09:16,390 --> 00:09:18,810
So five will come here and one will come here.

149
00:09:19,060 --> 00:09:22,320
Then we used to write be good back if you remember.

150
00:09:23,170 --> 00:09:24,310
But here what we will do.

151
00:09:24,700 --> 00:09:31,120
We will not write be back, we will not write it, but we will assume that the last element has been

152
00:09:31,120 --> 00:09:31,590
removed.

153
00:09:31,930 --> 00:09:34,030
So we just have to assume this one.

154
00:09:34,040 --> 00:09:35,140
We will not perform this.

155
00:09:35,140 --> 00:09:37,690
We will just assume so.

156
00:09:37,690 --> 00:09:38,800
Let's do so.

157
00:09:38,800 --> 00:09:41,140
What will happen to one in five has been said.

158
00:09:41,590 --> 00:09:44,450
So this is one and this is five now.

159
00:09:45,440 --> 00:09:48,220
Now just assume that the element one has been removed.

160
00:09:48,550 --> 00:09:52,830
Just assume now again what we will do, we will do the standard approach.

161
00:09:53,110 --> 00:09:55,000
So compare five with four and eight.

162
00:09:55,120 --> 00:09:56,200
Forward is the smallest.

163
00:09:56,440 --> 00:10:00,440
What we will do, we will do the trappings of what will come here and five will come here.

164
00:10:00,700 --> 00:10:07,290
Now compare five with the ten, but do not compare five with one because one has been removed.

165
00:10:07,300 --> 00:10:10,570
It is not actually removed, but we have assumed that it is removed.

166
00:10:10,790 --> 00:10:14,670
So five will get compared only with ten and then we have to do nothing.

167
00:10:15,040 --> 00:10:17,110
So basically we did one more step in.

168
00:10:17,740 --> 00:10:23,320
The five is actually slept with four, so four will come here and five will come here.

169
00:10:23,950 --> 00:10:26,170
Simple now again.

170
00:10:26,180 --> 00:10:27,440
So what is my three.

171
00:10:27,460 --> 00:10:35,200
So this is four then I have five here and then we have eight and then we have ten.

172
00:10:35,590 --> 00:10:37,350
So I am writing a different color.

173
00:10:37,930 --> 00:10:44,470
So actually this one is removed but I am writing a different color so that you can assume that the one

174
00:10:44,620 --> 00:10:45,870
element one has been removed.

175
00:10:45,880 --> 00:10:46,360
Simple.

176
00:10:47,230 --> 00:10:48,970
Now let's do it again.

177
00:10:49,420 --> 00:10:51,430
So I want to remove the minimum element.

178
00:10:51,430 --> 00:10:56,770
You can see the remove minimum function and times we have to perform and times now let's perform one

179
00:10:56,770 --> 00:10:59,590
more time so four will get slapped with the last element.

180
00:10:59,590 --> 00:11:00,670
Last element is ten.

181
00:11:01,120 --> 00:11:03,670
Now four is here and then is here.

182
00:11:04,690 --> 00:11:05,680
So let me do this.

183
00:11:06,050 --> 00:11:11,410
Four so four and then so this is four and this is ten.

184
00:11:11,800 --> 00:11:12,340
Simple.

185
00:11:13,480 --> 00:11:16,970
And now this forward, you have to assume that this vote has been removed.

186
00:11:17,680 --> 00:11:21,640
Now, again, do the same thing, compare 10 with five and it five is the smallest.

187
00:11:21,700 --> 00:11:23,050
So you will separate five.

188
00:11:23,530 --> 00:11:25,960
So five will come here and then will come here.

189
00:11:26,960 --> 00:11:33,500
Now, compare then with its left and right children, but left and right children does not exist, so

190
00:11:33,500 --> 00:11:34,550
you will not do anything.

191
00:11:35,580 --> 00:11:37,110
So you will simply stop here.

192
00:11:37,140 --> 00:11:38,230
So what did I do here?

193
00:11:38,520 --> 00:11:44,220
So I said and in five surveyed, so so is here, I just saw 10 in five.

194
00:11:44,220 --> 00:11:45,330
So 10 will come here.

195
00:11:45,870 --> 00:11:47,220
And this is my element.

196
00:11:47,230 --> 00:11:47,610
Five.

197
00:11:48,600 --> 00:11:49,120
Simple.

198
00:11:49,410 --> 00:11:51,330
So what is my Greenall?

199
00:11:51,660 --> 00:11:52,440
So this is.

200
00:11:54,400 --> 00:12:02,380
This is five, then I have ten here, then I have it here and the elements four and element one.

201
00:12:02,380 --> 00:12:03,730
So this has been removed.

202
00:12:04,960 --> 00:12:09,140
Now I want to remove element five, so element five will get swept with it.

203
00:12:09,640 --> 00:12:13,600
So five will come here and it will come here, so do the stepping.

204
00:12:14,080 --> 00:12:17,080
So element, it is going to come here.

205
00:12:17,830 --> 00:12:21,020
And similarly, element five is going to come here.

206
00:12:21,910 --> 00:12:22,970
Now, what are you going to do?

207
00:12:23,200 --> 00:12:25,870
You will assume that Element five has now been removed.

208
00:12:26,200 --> 00:12:29,670
So basically you will compare it with 10 and it is correct.

209
00:12:29,680 --> 00:12:30,890
So do not do anything.

210
00:12:31,660 --> 00:12:32,710
Now what is Maitri?

211
00:12:33,220 --> 00:12:34,680
So my tree is very simple.

212
00:12:35,050 --> 00:12:40,890
I have eight and 10, so I have only two elements left and all the elements has been removed.

213
00:12:40,900 --> 00:12:45,040
So five is removed for it is removed, one is removed.

214
00:12:45,040 --> 00:12:45,620
Simple.

215
00:12:46,450 --> 00:12:49,990
Now I want to delete the minimum element so I will remove minimum function.

216
00:12:49,990 --> 00:12:55,210
So I will separate and then so it is going to come here and it's going to come here.

217
00:12:55,600 --> 00:12:56,430
So where is it.

218
00:12:56,590 --> 00:12:59,260
So it got swept with 10 Beristain.

219
00:12:59,260 --> 00:13:02,940
So it will come here and then will come here.

220
00:13:03,670 --> 00:13:04,240
Simple.

221
00:13:04,810 --> 00:13:05,730
Then what we will do.

222
00:13:06,160 --> 00:13:10,660
So then now you know you will compare ten with its left and right children.

223
00:13:10,660 --> 00:13:13,300
So left children does not exist, right.

224
00:13:13,330 --> 00:13:14,590
Children does not exist.

225
00:13:15,550 --> 00:13:19,180
So you will do nothing because left and right does not exist.

226
00:13:20,020 --> 00:13:21,770
Now finally, what is your eddy.

227
00:13:21,820 --> 00:13:22,200
So do you.

228
00:13:22,210 --> 00:13:23,320
Finally, what is your tree.

229
00:13:23,660 --> 00:13:29,280
Now I have only one element left, so I have been and basically all the elements has been removed.

230
00:13:29,290 --> 00:13:30,160
So this is it.

231
00:13:30,700 --> 00:13:31,660
This is five.

232
00:13:31,820 --> 00:13:32,890
This is four.

233
00:13:33,190 --> 00:13:34,320
And this is one.

234
00:13:34,990 --> 00:13:35,920
Now what you have to do.

235
00:13:36,280 --> 00:13:41,650
So basically you will step 10 with 10 because 10 is the last element also.

236
00:13:41,980 --> 00:13:45,130
And then you will assume that element 10 has been removed.

237
00:13:46,030 --> 00:13:49,600
So swept 10 with 10, so 10 will get seven with ten.

238
00:13:49,840 --> 00:13:52,460
And then you will assume that element 10 has been removed.

239
00:13:52,480 --> 00:13:54,340
So basically your tree is empty.

240
00:13:54,700 --> 00:14:00,670
So by empty, I mean the tree is still there, but all the elements has been diluted, you have to assume.

241
00:14:02,480 --> 00:14:08,390
OK, so we have called removed function and so here and this way, so we can remove the minimum function

242
00:14:08,390 --> 00:14:11,720
five times and you can see so what is the condition of your area?

243
00:14:12,440 --> 00:14:14,270
So your area now looks like this?

244
00:14:14,480 --> 00:14:15,470
First I have then.

245
00:14:15,950 --> 00:14:16,940
Then I have it.

246
00:14:16,940 --> 00:14:18,380
Then five, then four, then one.

247
00:14:18,620 --> 00:14:19,310
So 10.

248
00:14:19,340 --> 00:14:20,710
Then I have it.

249
00:14:20,720 --> 00:14:21,800
Then I have five.

250
00:14:21,800 --> 00:14:22,640
Then I have four.

251
00:14:22,640 --> 00:14:23,600
And then I have one.

252
00:14:24,350 --> 00:14:25,430
Now you can notice.

253
00:14:25,820 --> 00:14:29,960
So this area is actually sorted, but this area sorted in decreasing order.

254
00:14:31,010 --> 00:14:34,830
That it gets sorted in decreasing order, but that's just fine.

255
00:14:35,100 --> 00:14:36,870
So one thing is very clear here.

256
00:14:37,100 --> 00:14:43,790
So in the in place he sought in the in place he sought, if you will, apply the minimum priority queue,

257
00:14:44,360 --> 00:14:49,070
if you lose the court of meaning prior to you, then you really will get sorted in descending order

258
00:14:49,910 --> 00:14:51,140
and in the in place.

259
00:14:51,140 --> 00:14:56,120
He thought if you will use the card of if you will write the code for the maximum priority queue, then

260
00:14:56,120 --> 00:14:59,870
your area basically then you will get sorted in the increasing order.

261
00:15:01,720 --> 00:15:08,650
Simple now again, what is the time, complexities or time complexities still and Logan, we are just

262
00:15:08,650 --> 00:15:10,570
using the report, but since.

263
00:15:12,170 --> 00:15:17,800
We are building we are creating the we are building the heap in the given area only, and then we are

264
00:15:17,810 --> 00:15:20,480
planning to remove minimum function in this area for the time.

265
00:15:20,720 --> 00:15:22,610
So the space complex complexities big often.

266
00:15:23,240 --> 00:15:24,950
So we are improving on space.

267
00:15:27,040 --> 00:15:34,150
Simple, so if you have confusion, what you can do, you can just take one more example and you can

268
00:15:34,150 --> 00:15:35,180
apply the algorithms.

269
00:15:35,740 --> 00:15:37,330
So let me take one more example.

270
00:15:38,990 --> 00:15:41,960
So this is my area, so I have element 15.

271
00:15:47,390 --> 00:15:54,740
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

272
00:15:54,740 --> 00:15:55,250
20.

273
00:15:55,550 --> 00:15:56,090
Simple.

274
00:15:57,140 --> 00:15:58,970
So Heap's Ortez, two parts.

275
00:16:00,410 --> 00:16:01,730
He has two parts.

276
00:16:01,760 --> 00:16:06,900
So, again, the first part is basically the building heap, so first parties, you what you will do,

277
00:16:06,950 --> 00:16:13,130
you will build the heap in the given that only and second part, basically, you have to call the remove

278
00:16:13,130 --> 00:16:16,660
minimum function and times and it's the size of the area.

279
00:16:16,670 --> 00:16:17,660
So in times.

280
00:16:18,970 --> 00:16:19,510
Simple.

281
00:16:21,140 --> 00:16:27,860
So, again, we will do the same thing, so we will assume that this area, Element 15, has been inserted

282
00:16:27,860 --> 00:16:28,610
into the hip.

283
00:16:30,260 --> 00:16:31,870
So let me take me some variables.

284
00:16:31,880 --> 00:16:32,240
So.

285
00:16:33,230 --> 00:16:34,120
Let us take.

286
00:16:36,070 --> 00:16:42,790
Let's take child index and let us take one multivariable parent index and let's take one more variable

287
00:16:42,790 --> 00:16:43,330
index.

288
00:16:45,170 --> 00:16:48,350
So what this index represents, so it will represent.

289
00:16:49,750 --> 00:16:52,340
It will represent the starting point of the uncertainty.

290
00:16:52,690 --> 00:16:56,450
So, for example, this is zero one, two, three and four.

291
00:16:57,370 --> 00:17:00,220
So what is the starting point of the uncertainty that is?

292
00:17:00,250 --> 00:17:02,550
So this part is actually the uncertainty.

293
00:17:02,770 --> 00:17:04,550
So the starting point is the next one.

294
00:17:05,020 --> 00:17:13,450
So this is containing one simple now element 15 has been pushed into the other heap, into our heap.

295
00:17:13,780 --> 00:17:15,960
So we should write 15.

296
00:17:15,970 --> 00:17:17,220
So I'm writing 15 here.

297
00:17:17,859 --> 00:17:19,540
So 11, 15 has been inserted.

298
00:17:20,440 --> 00:17:21,010
Simple.

299
00:17:21,910 --> 00:17:24,030
So now let's insert elements six.

300
00:17:25,890 --> 00:17:31,980
So I'm inserting elements, so it's a Nexus one, so that's why when it's presented, I'm inserting

301
00:17:31,980 --> 00:17:32,340
sex.

302
00:17:32,340 --> 00:17:35,190
So let's insert sex here.

303
00:17:37,520 --> 00:17:43,100
Now, your child index is same as the index, so this is one on less than what you are going to do.

304
00:17:43,130 --> 00:17:48,140
You will find out the parent index, which is zero, and then you are going to compare again the same

305
00:17:48,140 --> 00:17:48,380
thing.

306
00:17:48,380 --> 00:17:51,310
I'm comparing six and 15 and it will get set.

307
00:17:51,590 --> 00:17:54,300
So 15 is going to come here and six will going to come here.

308
00:17:54,320 --> 00:18:01,400
So again, we will do the September 15 is going to come here and six is going to come here and then

309
00:18:01,400 --> 00:18:02,420
we will not stop here.

310
00:18:02,450 --> 00:18:05,180
So what I'm going to update my child index.

311
00:18:05,480 --> 00:18:09,080
So the child index just the same color child index will become zero.

312
00:18:09,260 --> 00:18:13,760
And if you remember, in the last quarter we have written Gile Index for bigger than zero.

313
00:18:13,790 --> 00:18:15,250
So the index becomes zero.

314
00:18:15,590 --> 00:18:16,550
I'm going to stop.

315
00:18:18,020 --> 00:18:18,960
So I will stop here.

316
00:18:19,220 --> 00:18:22,260
So this is next zero and this is index one simple.

317
00:18:23,030 --> 00:18:25,430
Now, let's take one more element into consideration.

318
00:18:25,770 --> 00:18:28,150
So I am taking element into consideration.

319
00:18:28,160 --> 00:18:31,340
So the value of it is to try to index.

320
00:18:31,370 --> 00:18:34,010
So first, take three into consideration.

321
00:18:34,370 --> 00:18:38,000
Its index is actually two, so that's why the index is doing so.

322
00:18:38,000 --> 00:18:39,650
This is same as this one index.

323
00:18:39,650 --> 00:18:40,190
Simple.

324
00:18:40,910 --> 00:18:44,360
Now again, we are going to calculate the index for the comparison.

325
00:18:44,630 --> 00:18:45,980
So being index is zero.

326
00:18:46,610 --> 00:18:52,280
You remember the formula Gile index minus one, but also this is Giler index minus one by two.

327
00:18:52,940 --> 00:18:57,890
So this formula you should remember now I'm going to compare three and six.

328
00:18:58,130 --> 00:18:59,020
So what will happen?

329
00:18:59,030 --> 00:19:00,580
Obviously, this will take place.

330
00:19:01,010 --> 00:19:03,750
So six is going to come here and it is going to come here.

331
00:19:03,770 --> 00:19:07,640
So let's do that sweeping so six and it will be three.

332
00:19:08,510 --> 00:19:09,110
Simple.

333
00:19:09,650 --> 00:19:10,830
And then what are going to do?

334
00:19:10,850 --> 00:19:13,090
So now the trial index is actually zero.

335
00:19:13,520 --> 00:19:15,260
So there does appear the child index.

336
00:19:15,260 --> 00:19:16,670
So child index becomes zero.

337
00:19:17,210 --> 00:19:19,820
As soon as the child index becomes zero, you are going to stop.

338
00:19:20,240 --> 00:19:20,840
Simple.

339
00:19:21,410 --> 00:19:23,810
Now, let's take one more element into consideration.

340
00:19:24,320 --> 00:19:26,960
So I am taking element two into consideration.

341
00:19:27,800 --> 00:19:29,740
So element two has index three.

342
00:19:31,100 --> 00:19:32,690
So this is my element too.

343
00:19:33,350 --> 00:19:36,100
And this has index to be simple.

344
00:19:36,860 --> 00:19:40,010
Now, again, we are we are going to do the same thing, so.

345
00:19:41,590 --> 00:19:46,870
Joel Index is actually three, and then you are going to find the painter next to paint the next one

346
00:19:47,140 --> 00:19:49,480
and then you are going to compare two and 15.

347
00:19:49,690 --> 00:19:51,340
So obviously something will take place.

348
00:19:51,370 --> 00:19:55,290
So 15 is going to come here and two is going to come here.

349
00:19:55,300 --> 00:19:56,360
So let's do it here.

350
00:19:56,380 --> 00:20:02,260
So it do so instead of two, 15 will come here and instead of 15 it will be there.

351
00:20:03,380 --> 00:20:06,290
And then your child next becomes one, so you will copy.

352
00:20:07,400 --> 00:20:12,740
The challenge, next one now calculating, abandoned six, abandoned Nixon zero, and then let's do

353
00:20:12,740 --> 00:20:16,360
the comparison to 20 again, you have to do the slapping part.

354
00:20:16,700 --> 00:20:19,310
So two is going to come here and three is going to come here.

355
00:20:19,310 --> 00:20:20,360
So barriers to entry.

356
00:20:20,690 --> 00:20:23,680
So three is going to come here and two is going to come here.

357
00:20:23,690 --> 00:20:24,260
Simple.

358
00:20:25,160 --> 00:20:26,040
Then what will happen?

359
00:20:26,360 --> 00:20:28,310
So now the child next becomes a zero.

360
00:20:28,580 --> 00:20:29,810
So let's copy this one.

361
00:20:30,030 --> 00:20:32,510
So as soon as a child next becomes zero, you will stop.

362
00:20:33,440 --> 00:20:34,830
So I'm gonna stop.

363
00:20:36,020 --> 00:20:38,110
Now, let's take one more element into consideration.

364
00:20:38,120 --> 00:20:39,470
So this is the last element.

365
00:20:40,040 --> 00:20:42,290
So take element into consideration.

366
00:20:43,010 --> 00:20:49,560
So the value of AI becomes for the value of the value of AI becomes for Sottile.

367
00:20:49,750 --> 00:20:52,820
So the element distantly so right on here.

368
00:20:53,900 --> 00:20:58,640
So it's indexers for again, the child index is actually four.

369
00:20:59,030 --> 00:21:01,850
Then you will calculate the into next to be Nix's one.

370
00:21:02,550 --> 00:21:03,700
The index is one.

371
00:21:03,740 --> 00:21:08,650
Then what you're going to do you will compare twenty with three to compare to the entry.

372
00:21:08,660 --> 00:21:10,000
So this is correct.

373
00:21:10,730 --> 00:21:11,710
So this is correct.

374
00:21:11,720 --> 00:21:14,750
Since this thing is correct then what do you, what do you want to do.

375
00:21:14,750 --> 00:21:15,410
You will stop.

376
00:21:16,280 --> 00:21:19,910
The Konstanty is at its right position so you will stop.

377
00:21:20,060 --> 00:21:21,740
So finally, what is your eddy.

378
00:21:23,000 --> 00:21:30,020
So your already do then you have three and then you have six and then you have fifteen and then you

379
00:21:30,020 --> 00:21:33,130
have twenty and you can.

380
00:21:33,800 --> 00:21:34,880
So what is your minimum.

381
00:21:35,120 --> 00:21:36,740
So first I have element to.

382
00:21:37,830 --> 00:21:44,490
Then I have elementary here, then 11, six, so two, then elementary, then Elliman six and then 15

383
00:21:44,490 --> 00:21:45,060
and 20.

384
00:21:45,450 --> 00:21:48,480
So then you have 11, 15 and then you have 11, 20.

385
00:21:49,410 --> 00:21:52,740
So the first part of hip start to the first part.

386
00:21:52,800 --> 00:21:55,260
So this is this is in place.

387
00:21:55,560 --> 00:21:56,700
He sort.

388
00:21:57,670 --> 00:22:04,060
So this is in place Cheapside, so the first part of in place, he is actually first building up, so

389
00:22:04,060 --> 00:22:05,230
we have built the heap.

390
00:22:06,130 --> 00:22:11,860
Inside the area, inside the Internet, now, we have to call the removed minimum function and times,

391
00:22:12,190 --> 00:22:16,450
so I hope you can call remove minimum function on the city five times.

392
00:22:16,870 --> 00:22:18,340
But just remember one thing.

393
00:22:18,760 --> 00:22:20,590
You will not actually delete the element.

394
00:22:20,590 --> 00:22:23,690
You will just assume that you have deleted the element.

395
00:22:23,710 --> 00:22:27,400
For example, first 20-20 will get swabbed.

396
00:22:27,820 --> 00:22:30,220
Then you do not have to call pop back function.

397
00:22:30,220 --> 00:22:31,810
You will not call malfunction.

398
00:22:31,810 --> 00:22:35,260
You will just assume that Element two has been removed.

399
00:22:35,470 --> 00:22:38,350
You just have to assume so.

400
00:22:38,360 --> 00:22:41,150
I really hope that you guys can implement this in place.

401
00:22:41,560 --> 00:22:48,430
So what you have to do, you can just copy paste our zip code and you can also copy paste our remove

402
00:22:48,430 --> 00:22:51,670
minimum function code, but you have to do some modification.

403
00:22:51,680 --> 00:22:55,930
So just you have to just slightly, slightly modify our existing code.

404
00:22:57,070 --> 00:23:00,850
I really hope that you guys can implement in place he brought.

405
00:23:01,820 --> 00:23:03,590
I will write the code in the next video.

406
00:23:03,980 --> 00:23:04,680
See you there.

407
00:23:04,970 --> 00:23:05,420
Bye bye.