1
00:00:01,400 --> 00:00:02,300
Hi, everyone.

2
00:00:02,330 --> 00:00:08,240
We discussed that priority to Kukan, we have two types in one priority queue and I would argue and

3
00:00:08,240 --> 00:00:13,330
we discussed that we will use help to implement our protocol and help us to properties first.

4
00:00:13,340 --> 00:00:14,720
It is a complete minority.

5
00:00:15,010 --> 00:00:19,580
We discussed what is a complete binary in our last video so we know what is a complete planetary.

6
00:00:19,790 --> 00:00:23,720
And the second property was it has something called keep order property.

7
00:00:24,260 --> 00:00:28,310
So just like Vertigo's heap can be of two types.

8
00:00:28,340 --> 00:00:33,740
So first one is minimum hip hip and the second one is Max hip.

9
00:00:35,200 --> 00:00:42,760
And now let's discuss what is a border property, so let's discuss border property, so first let us

10
00:00:42,760 --> 00:00:44,650
consider what is a minimum hyp.

11
00:00:45,900 --> 00:00:49,180
So in minimum, the definition is very simple.

12
00:00:49,500 --> 00:00:57,930
So basically the root value will be less then left value and the root value will be less than the retail

13
00:00:57,930 --> 00:00:59,970
value of everything myself.

14
00:01:00,360 --> 00:01:05,790
So in minimum heap, the heap other properties is the root value will be less than the lovechild value

15
00:01:06,030 --> 00:01:09,290
and the root value will be less than the retail value.

16
00:01:10,020 --> 00:01:14,980
And you can guess in the in the maxim it will just be opposite.

17
00:01:15,330 --> 00:01:17,410
So in the maximum, what will happen.

18
00:01:17,820 --> 00:01:25,410
So the root value will be then left gile value and similarly the root value will be greater than the

19
00:01:25,500 --> 00:01:26,460
original value.

20
00:01:27,440 --> 00:01:29,400
So this is called Mexi property.

21
00:01:30,350 --> 00:01:32,640
Now let's take an example to understand it better.

22
00:01:33,560 --> 00:01:35,800
So this is a complete by Nutri.

23
00:01:36,860 --> 00:01:38,230
This is a complete ministry.

24
00:01:38,510 --> 00:01:39,880
This is a complete ministry.

25
00:01:40,370 --> 00:01:41,990
So one thing is very clear.

26
00:01:42,020 --> 00:01:45,380
This is a complete bindery, but it also satisfy he bought the property.

27
00:01:45,390 --> 00:01:47,450
So I am taking example of minimum EHP.

28
00:01:49,370 --> 00:01:50,870
So is this truly a minimum?

29
00:01:51,320 --> 00:01:57,080
So first of all, it is a complete binary take and then it sets the minimum order property.

30
00:01:57,410 --> 00:02:01,450
Many properties or root value one is less than two and three.

31
00:02:01,730 --> 00:02:02,940
So this is a minimum.

32
00:02:03,170 --> 00:02:04,690
This is a valid example of minimum.

33
00:02:06,080 --> 00:02:07,340
Now, is this a minimum?

34
00:02:07,580 --> 00:02:12,170
Yes, it is a by Niddrie and two is basically less than four.

35
00:02:12,170 --> 00:02:13,250
So it is a minimum VEB.

36
00:02:16,100 --> 00:02:17,720
So is it now a minimum?

37
00:02:18,020 --> 00:02:24,200
Yes, it is a complete military and also two is basically less than four and five when it's basically

38
00:02:24,200 --> 00:02:25,430
less than two and three.

39
00:02:25,670 --> 00:02:28,430
So this is the minimum he property.

40
00:02:28,670 --> 00:02:31,460
So that's why this is a valid example of minimum cheap.

41
00:02:35,280 --> 00:02:39,390
So to check for the minimum, we have to check for the two properties first, we have to check whether

42
00:02:39,390 --> 00:02:43,580
the inventory is accompanied by any and then we have to check the heap other the property.

43
00:02:44,280 --> 00:02:45,930
So two properties we have to check.

44
00:02:47,160 --> 00:02:48,690
Now, let's take one more example.

45
00:02:51,000 --> 00:02:54,210
So you have to tell me whether the given tree is a minimum heap or not.

46
00:02:56,160 --> 00:03:04,610
So let's take this example, 10, 20, 40, then 30, 35, and let's say a hundred.

47
00:03:06,480 --> 00:03:09,870
So first tell me whether it is a minimum or not.

48
00:03:10,380 --> 00:03:13,050
So for checking minimum, we have to check two properties.

49
00:03:13,050 --> 00:03:14,940
So first, is it a complete by.

50
00:03:15,900 --> 00:03:19,950
Yes, it is accompanied by an entry and now you have to check minimum property.

51
00:03:20,220 --> 00:03:22,950
That is route value should be left and left and right.

52
00:03:22,950 --> 00:03:23,500
Jalula.

53
00:03:23,790 --> 00:03:27,750
So let's check what Avenal 10 is less than 20 and 40.

54
00:03:27,750 --> 00:03:28,210
Correct.

55
00:03:28,530 --> 00:03:31,880
So 20 is less than 30 and 25 correct.

56
00:03:32,280 --> 00:03:33,810
40 is less than 100.

57
00:03:33,810 --> 00:03:34,200
Correct.

58
00:03:34,230 --> 00:03:35,750
So yes, it is a minimum.

59
00:03:36,690 --> 00:03:37,920
It is a minimum EHP.

60
00:03:39,760 --> 00:03:42,970
Now, if I had an order, for example, I am adding an old.

61
00:03:44,650 --> 00:03:51,160
Tattie, so tell me whether it is a minimum or not, so first let us discuss whether it is accompanied

62
00:03:51,160 --> 00:03:52,050
by military or not.

63
00:03:52,060 --> 00:03:53,950
So, yes, it is accompanied by military.

64
00:03:55,280 --> 00:03:57,180
So this story is a complete binary.

65
00:03:57,380 --> 00:04:03,970
Now let's check for the medium property, so 40 is less than a hundred, but 40 is a good identity.

66
00:04:04,400 --> 00:04:10,430
So this tree is a complete binary, but this tree is not a minimum heap.

67
00:04:11,460 --> 00:04:18,810
Because it doesn't satisfy the minimum property, so this is a valid, complete binary tree, but it

68
00:04:18,810 --> 00:04:19,730
is not a minimum.

69
00:04:21,130 --> 00:04:22,500
Let's take one more example.

70
00:04:29,650 --> 00:04:37,830
That said, thirty sixty, two hundred and one zero one, and let's say I have 41 here.

71
00:04:38,590 --> 00:04:40,270
So again, we have to check for the minimum.

72
00:04:40,450 --> 00:04:41,500
So is this street.

73
00:04:42,040 --> 00:04:44,410
So for minimum, we have to check two properties.

74
00:04:44,410 --> 00:04:45,850
First, the complete banditry.

75
00:04:46,030 --> 00:04:48,040
And secondly, he bought the property.

76
00:04:48,880 --> 00:04:51,700
So first check, is it a complete by nutri?

77
00:04:52,180 --> 00:04:54,120
Yes, it is a by Nutri.

78
00:04:54,910 --> 00:04:57,220
Now, let us check for the minimum he property.

79
00:04:57,610 --> 00:04:59,470
So 10 is less than twenty.

80
00:04:59,470 --> 00:05:02,830
One hundred twenty is less than 30 and 60.

81
00:05:03,190 --> 00:05:05,000
So today is less than 41.

82
00:05:05,380 --> 00:05:07,060
60 doesn't have left or right.

83
00:05:07,660 --> 00:05:11,730
So now let's check for another 200 is less than two hundred and one zero one.

84
00:05:11,730 --> 00:05:13,170
So yes, it is a minimum.

85
00:05:14,290 --> 00:05:14,600
Correct.

86
00:05:15,490 --> 00:05:17,200
Now what is a maximum?

87
00:05:17,220 --> 00:05:17,470
Hipp.

88
00:05:18,250 --> 00:05:22,050
So as discussed, Makhzoumi will be just the opposite of the minimum.

89
00:05:22,450 --> 00:05:26,770
So the root value will be bigger than the left Gyula value.

90
00:05:26,770 --> 00:05:29,690
And obviously it's also bigger than the right child.

91
00:05:29,720 --> 00:05:33,280
Will you let us take an example to understand it better?

92
00:05:35,750 --> 00:05:38,390
So this is a complete binary tree.

93
00:05:38,660 --> 00:05:43,960
This is a complete monitary this is a complete binary tree and this is a computer monitor.

94
00:05:44,050 --> 00:05:45,380
This is a computer binary.

95
00:05:45,890 --> 00:05:47,240
This is a complete binary.

96
00:05:47,780 --> 00:05:52,040
Now, given this tree, you have to check whether it is a maximum heap or not.

97
00:05:52,100 --> 00:05:53,700
So, again, we have to check for two things.

98
00:05:54,080 --> 00:05:56,580
So first, we have to check whether it is a complete binary tree.

99
00:05:56,600 --> 00:05:58,430
Yes, it is a complete binary tree.

100
00:05:58,790 --> 00:06:01,430
Then for them then we have to keep order property.

101
00:06:01,710 --> 00:06:05,370
So basically a root value should be good value and real value.

102
00:06:05,750 --> 00:06:07,850
So 10 is good than five and nine.

103
00:06:08,780 --> 00:06:10,940
Similarly, five is greater than three and one.

104
00:06:11,150 --> 00:06:13,310
And similarly, nine is greater than eight.

105
00:06:13,610 --> 00:06:15,660
So yes, it is a mixed heap.

106
00:06:15,680 --> 00:06:17,150
It is a valid mexi.

107
00:06:18,480 --> 00:06:24,030
Simple, now, if you will add one more node, for example, if you will add 12.

108
00:06:24,540 --> 00:06:31,970
So this is still a complete binary tree, but this is not a max heap because nine is less than 12.

109
00:06:32,010 --> 00:06:34,130
So it violates our Mexi property.

110
00:06:34,530 --> 00:06:40,480
So it is still accompanied by Niddrie, but it is not a maximum heap anymore.

111
00:06:41,640 --> 00:06:44,760
So I hope you understood the definition of minimum and maximum.

112
00:06:45,660 --> 00:06:48,860
Now let's see how we can insert in our heap.

113
00:06:49,140 --> 00:06:53,810
So I want to discuss how we will insert and let us take a minimum heap.

114
00:06:55,190 --> 00:06:57,180
For the maximum help, you can do the opposite.

115
00:06:58,160 --> 00:07:00,470
So let us take the example of minimum hyp.

116
00:07:02,750 --> 00:07:15,440
So let's say I have this story, so 10, then 20 to 40, 60, and it's a 45, 50 and 80.

117
00:07:16,310 --> 00:07:17,660
So first let us check.

118
00:07:17,690 --> 00:07:19,320
So is it a complete buy Niddrie?

119
00:07:19,760 --> 00:07:21,370
Yes, it is a complete Pinetree.

120
00:07:21,530 --> 00:07:22,570
So is it a Minyip?

121
00:07:22,580 --> 00:07:24,950
You can check 10 is less than 20 and 40.

122
00:07:25,160 --> 00:07:27,320
So 20 is less than six hundred.

123
00:07:27,320 --> 00:07:28,640
Sixty is less than 80.

124
00:07:28,910 --> 00:07:31,080
Similarly for these, less than 45 and 50.

125
00:07:31,100 --> 00:07:32,980
So, yes, it is a minimum hyp.

126
00:07:33,930 --> 00:07:34,740
It is a minimum.

127
00:07:35,670 --> 00:07:38,460
Now, let's say I want to insert a number 15.

128
00:07:40,000 --> 00:07:47,290
I want to insert this number 15, so minimum hip is actually acerbity can be bindery, and we know in

129
00:07:47,290 --> 00:07:52,690
a competitive binit there is only one position at which we can insert 15, and that position is basically

130
00:07:52,690 --> 00:07:53,110
this one.

131
00:07:54,580 --> 00:08:00,370
So 15 will be inserted towards the right of 60, so this is the only position available so that this

132
00:08:01,090 --> 00:08:02,740
remains a complete by Nutri.

133
00:08:03,860 --> 00:08:09,920
But if you will insert 50 at this position, then what will happen, this is not a minimum heap anymore

134
00:08:10,400 --> 00:08:13,870
because 60 is not less than 15.

135
00:08:14,930 --> 00:08:20,130
So this is still a CBT, but this is not a minimum help anymore.

136
00:08:20,870 --> 00:08:26,390
So what we have to do, what we will do, so we will compare 15 will be around 60.

137
00:08:27,320 --> 00:08:28,250
Now, what should happen?

138
00:08:28,460 --> 00:08:29,150
We will swap.

139
00:08:29,450 --> 00:08:32,240
So 60 will come here, then 15 will come here.

140
00:08:33,370 --> 00:08:41,620
Now, is it a minimum EP, so 15 is actually less than 20, so this is not this is still not a minimum.

141
00:08:41,799 --> 00:08:48,350
So what we will do, we will step down, 15 or 20 will come here and a 15 will come here now.

142
00:08:48,940 --> 00:08:50,790
So 15 is at its right position.

143
00:08:50,980 --> 00:08:52,450
So compared 10 and 50.

144
00:08:52,630 --> 00:08:53,800
So, yes, 15 is good.

145
00:08:53,800 --> 00:08:55,720
And then so this is now a minimum.

146
00:08:56,410 --> 00:08:57,370
So what is our tree?

147
00:08:57,700 --> 00:08:59,080
So this is our final tree.

148
00:08:59,830 --> 00:09:01,870
Then then 15, then 40.

149
00:09:02,590 --> 00:09:04,810
Then 45, then 50.

150
00:09:06,110 --> 00:09:08,280
Then 20 and then under.

151
00:09:08,930 --> 00:09:14,250
So here I have 60 and here I have 80, so that's how we will in a certain element.

152
00:09:14,600 --> 00:09:18,970
So this is a complete binary tree and this is also a minimum EHP.

153
00:09:20,400 --> 00:09:25,480
So what I did, I want to insert 15, I want to insert 15.

154
00:09:25,500 --> 00:09:29,300
So the only option available is this one, because this is a complete binary.

155
00:09:29,580 --> 00:09:34,260
Now, when you will insert 15 here, our minimum property will get violated.

156
00:09:34,440 --> 00:09:38,280
So what we will do so we will put 15 to it, correct position.

157
00:09:38,280 --> 00:09:40,740
So that's why we will compare 15 to its parent.

158
00:09:40,740 --> 00:09:41,840
Its parent was 60.

159
00:09:42,330 --> 00:09:42,900
That's right.

160
00:09:42,900 --> 00:09:43,580
We will swap.

161
00:09:44,160 --> 00:09:46,630
So 60 will come here and then 15 will come here.

162
00:09:47,160 --> 00:09:50,750
Then when 15 will come here, we will again compare 15 to its parent.

163
00:09:50,880 --> 00:09:52,260
So interesting that it's right.

164
00:09:52,260 --> 00:09:55,050
But, you know, so we will slap again.

165
00:09:55,060 --> 00:09:58,320
So 15 will come here and 20 will come here now.

166
00:09:58,710 --> 00:10:00,950
So now 15 is at correct position.

167
00:10:00,960 --> 00:10:01,350
Yes.

168
00:10:01,950 --> 00:10:03,620
Now 15 is at its conclusion.

169
00:10:03,660 --> 00:10:04,560
So we will stop.

170
00:10:05,220 --> 00:10:05,770
Simple.

171
00:10:06,000 --> 00:10:08,370
Let's take one more example for better understanding.

172
00:10:17,930 --> 00:10:23,660
OK, so let's take this one example only, so what I want to do, I want to insert an element literately

173
00:10:24,470 --> 00:10:28,660
I want to tell you, ELEGANTE So what is the only equation available for me?

174
00:10:29,270 --> 00:10:35,450
So this is the only position in the left hand side of 100, but if it will insert three in the left

175
00:10:35,450 --> 00:10:39,920
hand side, so this is still a complete binary tree, but this is not a minimum heap.

176
00:10:40,910 --> 00:10:44,420
So what we have to do, we will put three to it, the right position.

177
00:10:44,420 --> 00:10:47,380
So compare and so to use less than a hundred.

178
00:10:47,390 --> 00:10:48,080
So we will swap.

179
00:10:48,470 --> 00:10:51,090
So 100 will come here and three will come here.

180
00:10:51,500 --> 00:10:54,740
Now check whether three is added side position No.

181
00:10:54,950 --> 00:10:56,320
15 is greater than three.

182
00:10:56,330 --> 00:10:57,200
So I will swap.

183
00:10:57,830 --> 00:11:01,200
So 15 will come here and three will come here.

184
00:11:01,400 --> 00:11:03,230
Now check is three added.

185
00:11:03,280 --> 00:11:03,520
Right.

186
00:11:03,710 --> 00:11:06,530
You know basically ten is a good entry.

187
00:11:06,680 --> 00:11:08,240
So what we do, we will swap with it.

188
00:11:08,720 --> 00:11:11,280
So three will come here and then will come here.

189
00:11:11,510 --> 00:11:12,350
Now what happened?

190
00:11:12,350 --> 00:11:16,820
Basically, three reaches the top position, topmost position, basically the root position.

191
00:11:17,150 --> 00:11:18,640
So there is nowhere to go.

192
00:11:18,650 --> 00:11:19,460
So I will stop.

193
00:11:20,210 --> 00:11:21,380
And what is Mitry?

194
00:11:21,680 --> 00:11:26,500
So my final Griese, I have three here then I have ten here, then 40.

195
00:11:26,840 --> 00:11:29,300
So this is 45 and 50.

196
00:11:30,860 --> 00:11:33,680
Then I have 20 here, so I have 15 here.

197
00:11:34,930 --> 00:11:43,570
This is it, this is 60 and this is hundred, so this is accompanied by binary and this is also a minimum

198
00:11:43,590 --> 00:11:45,190
help you can check through.

199
00:11:45,340 --> 00:11:52,020
Less than 10 and 40 then is less than Grondin, 15 during these less than 1860, 15 is less than hundred

200
00:11:52,270 --> 00:11:54,030
for these, less than four to even 50.

201
00:11:54,040 --> 00:11:55,810
So it is a complete binary.

202
00:11:55,810 --> 00:11:57,210
It is a minimum also.

203
00:11:57,820 --> 00:11:59,290
So that's how we will insert.

204
00:12:01,860 --> 00:12:05,220
So if you will see in the worst case.

205
00:12:07,460 --> 00:12:11,600
But the complexity of the insert function, the worst case, so you can see.

206
00:12:13,710 --> 00:12:21,060
So he was present here now to use present at the topmost position, so how much of what we do, how

207
00:12:21,060 --> 00:12:21,980
much swearing we do?

208
00:12:22,320 --> 00:12:23,750
So this is high tech.

209
00:12:24,000 --> 00:12:31,950
So we have to do something each times, maximum at times, and what is inside.

210
00:12:31,950 --> 00:12:34,800
So instead will take off each time big of each time.

211
00:12:34,800 --> 00:12:37,230
And we know in a complete binary at just nothing.

212
00:12:37,230 --> 00:12:38,880
I did and I think it is just logon.

213
00:12:39,870 --> 00:12:41,460
So it is login.

214
00:12:41,850 --> 00:12:44,430
So insert function will always take a longer time.

215
00:12:47,960 --> 00:12:54,140
In the worst case, also hide in a complete binary tree, it is fixed, it is always log often and we

216
00:12:54,140 --> 00:12:56,630
have to do something maximum number of times.

217
00:12:56,870 --> 00:13:01,110
So that's why the time complexity for insertion is log often now what we did here.

218
00:13:01,490 --> 00:13:04,260
So basically three go from down to up.

219
00:13:04,700 --> 00:13:07,700
So this process is also called up ifI.

220
00:13:10,740 --> 00:13:18,300
So three go from the bottom to the top masterbation, so we call this process up here Biffy and this

221
00:13:18,300 --> 00:13:20,070
is the time complexity for In Session.

222
00:13:21,420 --> 00:13:24,780
Now let us see how we can delete a node from a minimum.

223
00:13:25,410 --> 00:13:26,490
We know how to insert.

224
00:13:26,520 --> 00:13:28,110
Now let's see how we can delete.

225
00:13:29,100 --> 00:13:35,130
So deleting a node in a minimum heap for maximum help, you can do it yourself.

226
00:13:36,450 --> 00:13:39,540
We just have to ensure that it satisfies the maximum property.

227
00:13:40,910 --> 00:13:42,330
So let us take an example.

228
00:13:42,920 --> 00:13:44,720
So let's say I have this example.

229
00:13:46,060 --> 00:13:51,770
Then then let's say 20, 30, 40, and let's say 100.

230
00:13:52,620 --> 00:13:57,510
OK, so suppose I want to delete 10, I want to delete 10.

231
00:13:58,060 --> 00:14:03,070
So the system so I want to delete the top most position, the topmost element.

232
00:14:03,400 --> 00:14:05,020
But I told you so.

233
00:14:05,040 --> 00:14:08,440
Minimum is actually a CBT and it can be divided.

234
00:14:08,590 --> 00:14:11,260
We can also we can only delete the last element.

235
00:14:11,620 --> 00:14:15,640
So I want to delete then but we can only delete hundred.

236
00:14:16,540 --> 00:14:19,090
I'm repeating myself, I want to delete then.

237
00:14:19,450 --> 00:14:24,340
But since it is a complete binary, so the only element that I can delete is actually handed.

238
00:14:24,880 --> 00:14:28,180
So how we will delete and you can guess what we will do.

239
00:14:28,180 --> 00:14:28,870
We will swap.

240
00:14:29,200 --> 00:14:31,930
So it will come here and then will come here.

241
00:14:33,280 --> 00:14:38,430
We will basically swap the element that we have to delete with the element that can be deleted.

242
00:14:39,040 --> 00:14:40,390
So then we come here.

243
00:14:40,390 --> 00:14:42,240
Then what we will do, we will delete this element.

244
00:14:42,640 --> 00:14:44,110
So let us delete this element.

245
00:14:44,980 --> 00:14:51,440
Now, after reading this element, this tree is still a complete by nutri, but this tree is not a minimum.

246
00:14:52,600 --> 00:14:58,630
So what we have to do, we will put a hundred bolts right position, will put a little side position.

247
00:14:58,870 --> 00:15:02,940
So what we'll do, we will compare words with its left and right child.

248
00:15:03,130 --> 00:15:04,940
So 100 is good then 20 and 30.

249
00:15:04,960 --> 00:15:07,560
But among turned down today is the smallest element.

250
00:15:07,570 --> 00:15:09,460
So I will slap a hundred with 20.

251
00:15:09,790 --> 00:15:12,630
So 20 will come here and 100 will come here.

252
00:15:13,300 --> 00:15:18,870
Now it is handed is added sideways you know, so I will come back handed with its left child.

253
00:15:18,970 --> 00:15:20,620
So right child doesn't exist anymore.

254
00:15:20,890 --> 00:15:22,230
So 40 is less than a net.

255
00:15:22,240 --> 00:15:23,800
So I will, I will swap again.

256
00:15:23,800 --> 00:15:26,040
So hundred will come here and forty will come here.

257
00:15:26,470 --> 00:15:27,840
So what will be my final three.

258
00:15:28,180 --> 00:15:34,900
So I have 20 then I have 40 here, I have 30 here and I have 100 here.

259
00:15:36,220 --> 00:15:37,720
So this is my completely.

260
00:15:38,740 --> 00:15:40,480
So let us take one more example.

261
00:15:42,810 --> 00:15:44,250
Of the a minimum.

262
00:15:44,880 --> 00:15:46,630
So let's take this example.

263
00:15:46,710 --> 00:15:54,780
I have one then let's say I have 10 and 15 and let's say I have 18, then 20, and then let's say I

264
00:15:54,780 --> 00:15:56,250
have 30 here.

265
00:15:56,460 --> 00:15:57,840
So let's make it 80.

266
00:15:58,730 --> 00:16:01,870
So this is an example of a minimum hyp.

267
00:16:03,860 --> 00:16:07,580
Minimum, he or we can say minimum prior, dequeue they both him.

268
00:16:08,770 --> 00:16:14,770
Now, if you remember, in the immediate priority queue, I will get the element, I will get the element

269
00:16:14,770 --> 00:16:16,590
first, which has the minimum priority.

270
00:16:16,900 --> 00:16:21,390
So if you can see, for example, I want to get the minimum element.

271
00:16:22,120 --> 00:16:24,640
So what is the minimum element in the minimum?

272
00:16:24,790 --> 00:16:26,920
So topmost element is the minimum element.

273
00:16:27,190 --> 00:16:30,880
So I can get minimum element in constant time.

274
00:16:30,910 --> 00:16:32,820
I just have to return the root element.

275
00:16:33,490 --> 00:16:40,810
So if you remember what is a proper minimum, so raw data will be less then left Giulietta and raw data

276
00:16:40,810 --> 00:16:42,640
will be less than the Retaliator.

277
00:16:42,880 --> 00:16:48,520
So that means in the minimum keep, the minimum element will be present at the topmost position.

278
00:16:48,550 --> 00:16:54,880
That is, the root element is going to be the minimum element and in the maximum keep, the maximum

279
00:16:54,880 --> 00:16:57,250
element will be present at the topmost position.

280
00:16:57,250 --> 00:16:58,490
That is the root position.

281
00:16:59,830 --> 00:17:05,530
Now, if you remember in the minimum protocol, I have one more function and the name of the function

282
00:17:05,530 --> 00:17:06,810
is actually remove minimum.

283
00:17:07,900 --> 00:17:08,790
So remove minimum.

284
00:17:08,800 --> 00:17:10,839
What it will do, it will remove the minimum element.

285
00:17:11,050 --> 00:17:13,900
So what I want to do, I want to remove element one.

286
00:17:14,319 --> 00:17:17,790
So this is the minimum element and I want to remove the minimum element.

287
00:17:18,099 --> 00:17:25,329
But what we can do, we can only remove the last element because it's a complete binary.

288
00:17:25,690 --> 00:17:32,830
So Minyip or you can say prior to Q So since it is a complete binary, so I can only remove the last

289
00:17:32,830 --> 00:17:34,720
element and the last element is 80.

290
00:17:35,440 --> 00:17:40,210
So I have this function, this function wants to remove one, but I can only remove it.

291
00:17:40,300 --> 00:17:42,890
So we will follow the approach that we discussed above.

292
00:17:43,240 --> 00:17:44,800
So we will step one entity.

293
00:17:45,040 --> 00:17:47,730
So it will come here and one will come here.

294
00:17:47,770 --> 00:17:49,720
Then what we will do, we will delete the last element.

295
00:17:49,720 --> 00:17:50,950
So we will delete this element.

296
00:17:52,020 --> 00:17:52,830
Now we will check.

297
00:17:53,010 --> 00:17:57,860
So this is still accompanied by Nutri, but this is not a minimum heap anymore.

298
00:17:58,230 --> 00:18:00,690
So for minimum, he property will be satisfied.

299
00:18:00,720 --> 00:18:03,410
We will compare it with its left and right children.

300
00:18:03,780 --> 00:18:06,630
So it is a good 10 and 15 vote.

301
00:18:06,930 --> 00:18:09,350
And among 10, 15, 10 is the smaller one.

302
00:18:09,360 --> 00:18:11,970
So I will slap penalties entity.

303
00:18:11,970 --> 00:18:13,520
So it will come here now again.

304
00:18:14,070 --> 00:18:18,440
So it is a stronger then 18 and 20, but it is the smaller one.

305
00:18:18,450 --> 00:18:21,490
So I will strap it in and 80.

306
00:18:22,170 --> 00:18:23,570
So what will be my final three.

307
00:18:23,580 --> 00:18:25,200
So the suspense then.

308
00:18:25,200 --> 00:18:26,250
I have 18.

309
00:18:26,730 --> 00:18:27,930
I have 15 here.

310
00:18:29,010 --> 00:18:35,000
I have a here and I have 20 here now again, so this is a complete by Nutri.

311
00:18:35,140 --> 00:18:35,430
Yes.

312
00:18:35,790 --> 00:18:37,140
So is it a minimum?

313
00:18:37,410 --> 00:18:43,120
Yes, Ben is less than 18 and 15 and 18 is less than 18, 20 at the end 20.

314
00:18:44,160 --> 00:18:48,430
So now check again, if you will, get if you call the function, get a minimum.

315
00:18:49,200 --> 00:18:53,700
So, again, the minimum element is Element and Dennis Besant at the topmost position.

316
00:18:54,180 --> 00:18:54,720
Simple.

317
00:18:55,140 --> 00:18:58,260
Now, if you want to remove the minimum element again, you will do the same thing.

318
00:18:58,260 --> 00:18:59,980
You will strap 10 and 20.

319
00:19:00,540 --> 00:19:02,060
So again, 20 will come here.

320
00:19:02,070 --> 00:19:03,170
Then 10 will come here.

321
00:19:03,420 --> 00:19:06,630
Then you will check 20 and they will do the last element.

322
00:19:06,640 --> 00:19:09,020
Then you will check 20 with left and right.

323
00:19:09,600 --> 00:19:11,880
So 15 is the smaller one.

324
00:19:11,880 --> 00:19:13,860
So you'll step during David 15.

325
00:19:14,490 --> 00:19:16,830
So 20 will come here and it will stop.

326
00:19:17,190 --> 00:19:20,360
So finally I have 15, then I have 18.

327
00:19:20,700 --> 00:19:23,470
So here I have 20 and here I have 80.

328
00:19:23,760 --> 00:19:27,500
So again, check the minimum element is always present at the top position.

329
00:19:28,890 --> 00:19:29,360
Simple.

330
00:19:29,790 --> 00:19:30,650
Now what we did.

331
00:19:31,230 --> 00:19:34,260
So what would be the time complexity for the deletion.

332
00:19:35,830 --> 00:19:42,430
How much time it will take so you can see, for example, it was here with the last element, with the

333
00:19:42,430 --> 00:19:45,820
first element, so it will be it is going to be present here.

334
00:19:45,820 --> 00:19:51,120
And then what we are doing, we are going to lock down and it will present at the last position.

335
00:19:51,340 --> 00:19:54,000
So in the worst case, last level, basically.

336
00:19:54,010 --> 00:19:55,420
So in the worst case, what will happen?

337
00:19:55,600 --> 00:19:58,720
I will do the stabbing at a number of times higher times.

338
00:19:59,170 --> 00:20:05,470
So deletion function takes big off height and we know in a complete binary height is always logoff often.

339
00:20:06,160 --> 00:20:10,120
So that's why the deletion function time complexity is long often.

340
00:20:10,750 --> 00:20:15,650
And one more thing, this process, what we are doing, we are going from top to down.

341
00:20:15,940 --> 00:20:18,370
So this process is called down heap biffy.

342
00:20:19,850 --> 00:20:21,590
This is called Down Deep ifI.

343
00:20:23,590 --> 00:20:28,940
So now let's discuss what are the time complexities for insertion deletion and get the minimum element.

344
00:20:29,470 --> 00:20:36,640
So again, in session we are doing up so maximum number of times it will be the setting will take off

345
00:20:36,640 --> 00:20:37,090
each time.

346
00:20:37,090 --> 00:20:43,000
And that is always a log often because in a complete binary tree, height is always log, often similarly

347
00:20:43,000 --> 00:20:43,680
interpolation.

348
00:20:44,120 --> 00:20:47,820
Again, the maximum that we have to perform will be the Gulf edge.

349
00:20:48,280 --> 00:20:50,710
So it will again be big off log in time.

350
00:20:51,280 --> 00:20:53,530
And let's say you are discussing about minimum.

351
00:20:53,770 --> 00:20:59,950
So in the minimum there's are function, get the minimum function and we just have to return the root

352
00:20:59,950 --> 00:21:00,370
element.

353
00:21:00,400 --> 00:21:04,360
So this is constant and here deletion is actually remove minimum.

354
00:21:06,880 --> 00:21:07,730
Remove the minimum.

355
00:21:08,410 --> 00:21:09,380
So what we will do?

356
00:21:09,400 --> 00:21:14,130
Let's take one more example, and this time we will construct our Minyip.

357
00:21:15,070 --> 00:21:21,910
So I want to construct them in hip and elements will come one Vivan elements will come one by one.

358
00:21:22,390 --> 00:21:23,870
Let's say I have an element then.

359
00:21:23,890 --> 00:21:26,060
So this is my minimum hip then.

360
00:21:26,860 --> 00:21:33,700
Now let's say I have an element five so five can be inserted only at the leftmost position due to the

361
00:21:33,700 --> 00:21:35,010
complete binary tree now.

362
00:21:35,380 --> 00:21:36,070
Is it a minimum?

363
00:21:36,400 --> 00:21:37,090
No, it is not.

364
00:21:37,660 --> 00:21:40,600
So then in five they will be swabbed.

365
00:21:40,840 --> 00:21:41,350
Simple.

366
00:21:41,860 --> 00:21:43,450
Now let's insert one more element.

367
00:21:43,480 --> 00:21:48,680
Let's say my element is 18, so 18 can be only inserted at the right position.

368
00:21:49,000 --> 00:21:50,310
Now, is it a minimum?

369
00:21:50,680 --> 00:21:51,760
Yes, it is a minimum.

370
00:21:51,970 --> 00:21:52,990
So do not do anything.

371
00:21:54,300 --> 00:22:01,080
Now, let's insert one more element, let's say I want to insert 20 so 20 can be inserted on the left

372
00:22:01,080 --> 00:22:01,510
hand side.

373
00:22:01,530 --> 00:22:02,590
So is it a minimum?

374
00:22:02,880 --> 00:22:03,330
Yes.

375
00:22:03,840 --> 00:22:06,590
Let's insert one more element to it.

376
00:22:06,900 --> 00:22:09,080
Or two can be inserted only at this position.

377
00:22:09,390 --> 00:22:10,650
Now, is it a minimum?

378
00:22:10,800 --> 00:22:12,030
No, this is not a minimum.

379
00:22:12,210 --> 00:22:12,960
So what will happen?

380
00:22:13,200 --> 00:22:14,610
I will say up to 110.

381
00:22:15,120 --> 00:22:16,560
So two will come here then.

382
00:22:16,560 --> 00:22:17,070
Will come in.

383
00:22:17,070 --> 00:22:19,550
Now, Jack is to decide which handle.

384
00:22:19,740 --> 00:22:22,770
So I will separate again or two will come here and five will come here.

385
00:22:23,900 --> 00:22:26,900
Now, I want to insert one more element, let's say I want to insert three.

386
00:22:27,200 --> 00:22:32,000
So the only option available to me is basically the left hand side of 18 again.

387
00:22:32,330 --> 00:22:33,500
So it's three at the side.

388
00:22:34,100 --> 00:22:34,400
So what?

389
00:22:34,730 --> 00:22:35,500
We will do something.

390
00:22:35,780 --> 00:22:38,000
So it will come here and three will come here.

391
00:22:38,300 --> 00:22:39,700
So finally, what does Mitry.

392
00:22:39,710 --> 00:22:42,050
So I have to here then I have five.

393
00:22:42,950 --> 00:22:51,890
Three, and then this is 20, this is 10 and this is 18, so this is my final three for these elements.

394
00:22:53,850 --> 00:22:57,470
Now you can check, so the stories are complete by Niddrie industries also minimum.

395
00:22:57,660 --> 00:23:02,870
So, too, is less than five three five is less than 20 and 10 and three is less than 18.

396
00:23:03,150 --> 00:23:04,680
So this is a minimum.

397
00:23:05,640 --> 00:23:07,220
Now, let's perform the also.

398
00:23:07,530 --> 00:23:10,280
So, for example, if you want to get the minimum element.

399
00:23:10,800 --> 00:23:13,770
So what is the minimum elements or top motivation is the minimum element.

400
00:23:13,770 --> 00:23:14,880
So I can return to.

401
00:23:15,830 --> 00:23:20,690
You can see in these elements who is the smallest, so I'm getting the minimum element, I'm able to

402
00:23:20,690 --> 00:23:22,670
find out the minimum element in Question Time.

403
00:23:24,200 --> 00:23:29,450
Now, let's say I want to call the function remove minimum delete minimum element, so which element

404
00:23:29,450 --> 00:23:32,960
we have to delete, I have to delete the topmost element.

405
00:23:33,230 --> 00:23:38,270
And for the deletion of the topmost element, what we can do, we can only delete the last element that

406
00:23:38,270 --> 00:23:38,750
is 18.

407
00:23:38,780 --> 00:23:40,210
So again, we will do the same thing.

408
00:23:40,220 --> 00:23:41,510
I will Sep 2010.

409
00:23:42,550 --> 00:23:46,450
So, too, will come here and then what do we do with this element?

410
00:23:47,720 --> 00:23:50,170
Now, is there an inside position?

411
00:23:50,210 --> 00:23:50,440
No.

412
00:23:50,780 --> 00:23:55,940
So it is greater than five and three, but among five entry three is the smaller one, so I will separate

413
00:23:55,940 --> 00:23:56,230
three.

414
00:23:56,600 --> 00:24:00,960
So it will come here and three will come here and now I will stop.

415
00:24:01,070 --> 00:24:02,410
So what is my three?

416
00:24:02,620 --> 00:24:05,740
Three, then I have five, then I have 18.

417
00:24:06,200 --> 00:24:07,330
So this is 20.

418
00:24:07,340 --> 00:24:13,070
And the system now again, this is a complete binary and this is also a minimum heap.

419
00:24:14,960 --> 00:24:20,120
So you can also check again what is the minimum element to use the minimum element after the two element

420
00:24:20,120 --> 00:24:21,560
of the element is removed.

421
00:24:22,190 --> 00:24:23,620
So that is how it is working.

422
00:24:24,290 --> 00:24:30,350
Now, let's say I again want to call this function reward minimum so this function will remove the topmost

423
00:24:30,350 --> 00:24:30,770
element.

424
00:24:31,190 --> 00:24:33,950
So three will be separated then.

425
00:24:34,250 --> 00:24:37,070
So three will come here and then will come here.

426
00:24:37,100 --> 00:24:42,740
So again, then I will delete elementary now which then is added eight points or ten is greater than

427
00:24:42,740 --> 00:24:43,060
five.

428
00:24:43,310 --> 00:24:44,140
So I will trap.

429
00:24:44,330 --> 00:24:46,420
So 10 will come here and five will come here.

430
00:24:46,640 --> 00:24:48,160
Now ten is less than 20.

431
00:24:48,170 --> 00:24:48,990
So this is correct.

432
00:24:49,040 --> 00:24:51,770
So what is my finally five.

433
00:24:51,770 --> 00:24:52,430
Then 10.

434
00:24:52,880 --> 00:24:53,960
Then 18.

435
00:24:55,500 --> 00:24:56,640
And grunty.

436
00:24:58,150 --> 00:25:02,010
So this is a complete binary tree and this is also a minimum.

437
00:25:02,170 --> 00:25:05,800
You can check five years, less than 10 and 18 and then is less than 20.

438
00:25:06,370 --> 00:25:11,770
And if you want to call, get the minimum function so you can return the topmost element in question

439
00:25:11,770 --> 00:25:12,040
time.

440
00:25:12,610 --> 00:25:15,660
So that is how minimum heap is looking for maximum.

441
00:25:15,910 --> 00:25:17,330
We will do just the opposite.

442
00:25:17,860 --> 00:25:21,830
So I'm giving you a break discussion and we will discuss the solution, the next video.

443
00:25:22,720 --> 00:25:26,330
So this is you will do this question yourself.

444
00:25:26,350 --> 00:25:30,940
So what you have to do, you have to construct a minimum heap, just like we did above, and the elements

445
00:25:30,940 --> 00:25:31,930
will come one by one.

446
00:25:32,350 --> 00:25:37,930
So let's say my first element is, well, then element the element five, then let's say hundred, then

447
00:25:37,930 --> 00:25:41,630
one, then let's say nine, then let's say zero and then let's say 14.

448
00:25:41,980 --> 00:25:42,920
So what do you have to do?

449
00:25:43,210 --> 00:25:49,440
You have to create a minimum heap and after creating minimum heap, you have to remove minimum function

450
00:25:49,450 --> 00:25:50,050
two times.

451
00:25:51,330 --> 00:25:55,960
So after getting the minimum, you will call remove minimum function two times, twice.

452
00:25:56,850 --> 00:25:58,920
So basically you have to do down here, Biffy.

453
00:26:01,330 --> 00:26:05,890
So this discussion and we will discuss the solution in the next video, so I will see you in the next

454
00:26:05,890 --> 00:26:06,140
one.

455
00:26:06,160 --> 00:26:06,580
Bye bye.