1
00:00:00,730 --> 00:00:01,600
Hi everyone.

2
00:00:01,600 --> 00:00:03,490
Let's do this question right.

3
00:00:03,490 --> 00:00:06,010
A max heap class that supports the following.

4
00:00:06,010 --> 00:00:08,530
Building a max heap from an input array.

5
00:00:08,530 --> 00:00:10,570
Inserting integers in the heap.

6
00:00:10,570 --> 00:00:11,770
Removing the heaps.

7
00:00:11,770 --> 00:00:13,450
Maximum or root value.

8
00:00:13,450 --> 00:00:14,770
Peeking at the heaps.

9
00:00:14,770 --> 00:00:16,120
Maximum or root value.

10
00:00:16,120 --> 00:00:19,060
The heap is to be represented in the form of an array.

11
00:00:19,060 --> 00:00:19,570
All right.

12
00:00:19,570 --> 00:00:21,070
So this is a basic question.

13
00:00:21,070 --> 00:00:25,900
So these are the four functions that we have to write or methods that we have to write for the class.

14
00:00:25,900 --> 00:00:26,110
Right.

15
00:00:26,110 --> 00:00:27,520
So these are instance methods.

16
00:00:27,520 --> 00:00:30,880
So let's go ahead and understand how we can solve this question.

17
00:00:30,880 --> 00:00:36,640
So we need to write the instance methods to build the heap insert into the heap remove from the heap

18
00:00:36,640 --> 00:00:37,840
and peek at the heap.

19
00:00:37,840 --> 00:00:41,650
All right so let's get started with the first function which is to build the heap.

20
00:00:41,650 --> 00:00:44,410
And remember we are representing the heap as an array.

21
00:00:44,410 --> 00:00:47,560
So in the previous videos we have discussed how we can do that.

22
00:00:47,560 --> 00:00:49,570
So we will be using that over here.

23
00:00:49,570 --> 00:00:50,110
All right.

24
00:00:50,140 --> 00:00:55,630
Now before we go ahead and discuss the method which will be used to build a heap from an input array,

25
00:00:55,630 --> 00:00:58,240
let's discuss the Heapify algorithm.

26
00:00:58,240 --> 00:01:05,080
Because to do this to build the heap from the input array, we will be repeatedly calling the Heapify

27
00:01:05,080 --> 00:01:07,450
algorithm on a set of indices.

28
00:01:07,450 --> 00:01:08,470
So we will discuss that.

29
00:01:08,470 --> 00:01:11,050
So first we will discuss the Heapify algorithm.

30
00:01:11,050 --> 00:01:14,440
So over here I have a binary tree.

31
00:01:14,440 --> 00:01:14,920
All right.

32
00:01:14,920 --> 00:01:17,890
And notice that you have an element seven over here.

33
00:01:17,890 --> 00:01:23,290
Now we know that this element over here does not follow the max heap property.

34
00:01:23,290 --> 00:01:23,500
Right.

35
00:01:23,500 --> 00:01:25,450
So over here you have 21 and 22.

36
00:01:25,450 --> 00:01:29,230
And clearly the children are greater than the parent.

37
00:01:29,230 --> 00:01:34,720
So let's say we want to implement an algorithm to heapify this element over here.

38
00:01:34,720 --> 00:01:39,190
Now if we write the indices we know that seven is at index one.

39
00:01:39,190 --> 00:01:39,430
Right.

40
00:01:39,430 --> 00:01:42,610
So writing the indices means let's convert this into an array.

41
00:01:42,610 --> 00:01:44,530
So I would be writing 95.

42
00:01:44,770 --> 00:01:47,320
Then I have seven then 45.

43
00:01:47,320 --> 00:01:52,000
Then I write 2122, then 30, 35, etc..

44
00:01:52,000 --> 00:01:52,360
Right.

45
00:01:52,360 --> 00:01:54,010
So this is what we have discussed before, right?

46
00:01:54,010 --> 00:01:57,940
So it follows the relationship between the parent and the child with the indices.

47
00:01:57,940 --> 00:02:01,420
So over here you can notice that seven is at index one.

48
00:02:01,420 --> 00:02:07,240
So we are going to write and we are going to discuss an algorithm to heapify the element over here in

49
00:02:07,240 --> 00:02:09,130
this tree at index one.

50
00:02:09,130 --> 00:02:09,610
All right.

51
00:02:09,610 --> 00:02:11,890
So again what is it that we are trying to do.

52
00:02:11,920 --> 00:02:18,490
We are going to change the position of the element seven such that it follows the heap property in this

53
00:02:18,490 --> 00:02:20,380
case the max heap property.

54
00:02:20,380 --> 00:02:21,100
All right.

55
00:02:21,460 --> 00:02:23,680
Now you can do this right.

56
00:02:23,680 --> 00:02:27,520
Again we are trying to heapify the element at index one which is this one over here.

57
00:02:27,520 --> 00:02:32,050
Now there is a prerequisite for us to be able to do this.

58
00:02:32,050 --> 00:02:39,340
The prerequisite is that we can do this only if all the elements in the left and right subtree follow

59
00:02:39,340 --> 00:02:40,240
the heap property.

60
00:02:40,240 --> 00:02:41,740
So let's take a look at this.

61
00:02:41,740 --> 00:02:45,400
So the left and right subtree of seven are these right.

62
00:02:45,400 --> 00:02:49,240
So all the elements over here and here follow the heap property.

63
00:02:49,240 --> 00:02:54,910
For example 21 is greater than 19 and 20 and 22 is greater than 15 and 16.

64
00:02:54,910 --> 00:03:02,140
So because this is satisfied that is why we can heapify the element at index one, which is this one

65
00:03:02,140 --> 00:03:02,560
over here.

66
00:03:02,560 --> 00:03:04,180
So remember this is important.

67
00:03:04,180 --> 00:03:11,320
We can heapify an element at an index only if all the elements in the left and right subtree follow

68
00:03:11,320 --> 00:03:12,280
the heap property.

69
00:03:12,280 --> 00:03:13,660
And it's followed over here.

70
00:03:13,660 --> 00:03:14,110
All right.

71
00:03:14,110 --> 00:03:16,270
So let's proceed and see how we can do this.

72
00:03:16,270 --> 00:03:22,900
So let's clear this now if I want to element if I want to heapify this element over here, what I have

73
00:03:22,900 --> 00:03:24,640
to do is I have to check its children.

74
00:03:24,640 --> 00:03:26,860
So its children are 21 and 22.

75
00:03:26,890 --> 00:03:29,350
Now the bigger among these two is 22.

76
00:03:29,350 --> 00:03:32,830
Right now let me check whether seven is greater than 22.

77
00:03:32,860 --> 00:03:33,700
Is that the case?

78
00:03:33,700 --> 00:03:34,780
No, it's not right.

79
00:03:34,780 --> 00:03:36,940
Seven is actually less than 22.

80
00:03:36,940 --> 00:03:39,730
Or I can say 22 is is greater than seven.

81
00:03:39,730 --> 00:03:43,240
So this does not follow the max heap property.

82
00:03:43,240 --> 00:03:46,000
So in this case we have to swap seven.

83
00:03:46,000 --> 00:03:48,400
And the bigger one among these two which is 22.

84
00:03:48,430 --> 00:03:49,780
So let's swap that.

85
00:03:49,780 --> 00:03:52,660
So 22 comes over here and seven comes over here.

86
00:03:52,660 --> 00:03:53,230
All right.

87
00:03:53,230 --> 00:03:55,210
So we have seven over here at this point.

88
00:03:55,210 --> 00:03:57,010
Now we need to continue this right.

89
00:03:57,010 --> 00:03:58,870
So we we need to continue this.

90
00:03:58,870 --> 00:04:02,410
Let's check its children at this point which is 15 and 16.

91
00:04:02,410 --> 00:04:04,690
So the bigger among these two is 16.

92
00:04:04,690 --> 00:04:08,290
Now over here again you can see 16 is greater than seven.

93
00:04:08,290 --> 00:04:10,870
So it does not follow the max heap property.

94
00:04:10,870 --> 00:04:11,140
Right.

95
00:04:11,140 --> 00:04:13,990
So we have to again swap seven and 16.

96
00:04:13,990 --> 00:04:15,340
So let's do that over here.

97
00:04:15,340 --> 00:04:17,470
We get seven over here and 16 over here.

98
00:04:17,470 --> 00:04:21,250
Now you can see that this is how the tree looks like right.

99
00:04:21,250 --> 00:04:22,240
You have seven over here.

100
00:04:22,240 --> 00:04:24,040
Now it's in the correct position.

101
00:04:24,040 --> 00:04:24,220
Right.

102
00:04:24,220 --> 00:04:27,580
So this is now a max binary heap.

103
00:04:28,000 --> 00:04:32,740
So we have successfully heap defied the element at index one which was this one over here.

104
00:04:32,740 --> 00:04:33,790
So what did we do.

105
00:04:33,790 --> 00:04:35,800
We had the element seven over here.

106
00:04:35,800 --> 00:04:43,090
And we bubbled down or sifted down this element to its correct position so that it follows the heap

107
00:04:43,090 --> 00:04:45,700
property, in this case the max heap property.

108
00:04:45,700 --> 00:04:48,760
So this is what we call the Heapify algorithm.

109
00:04:48,760 --> 00:04:53,860
Now that we have understood this, let's go ahead and come back to the build method which we have to

110
00:04:53,860 --> 00:04:54,190
write.

111
00:04:54,190 --> 00:05:00,340
And remember you can heapify and index only if all the elements in its left and right sub.

112
00:05:00,820 --> 00:05:02,200
Follow the heap property.

113
00:05:02,200 --> 00:05:04,030
So that is something that you have to keep in mind.

114
00:05:04,030 --> 00:05:05,980
We will use this over here as well.

115
00:05:05,980 --> 00:05:06,430
All right.

116
00:05:06,430 --> 00:05:08,440
So let's get back to our build function.

117
00:05:08,440 --> 00:05:11,890
Now for example let's say this is the array which is given to us.

118
00:05:11,890 --> 00:05:15,460
And we have to convert this into a max binary heap.

119
00:05:15,460 --> 00:05:17,860
So let's write the indices of this array.

120
00:05:17,860 --> 00:05:19,930
So zero one up to seven.

121
00:05:19,930 --> 00:05:20,380
All right.

122
00:05:20,410 --> 00:05:25,480
Now if I were to just picturise this as a binary tree it would look like this.

123
00:05:25,480 --> 00:05:25,690
Right.

124
00:05:25,690 --> 00:05:28,030
We have four seven and three are its children.

125
00:05:28,030 --> 00:05:30,610
Then zero nine, three, two and six.

126
00:05:30,610 --> 00:05:30,880
Right.

127
00:05:30,880 --> 00:05:31,630
So four.

128
00:05:31,660 --> 00:05:33,070
Then you have seven and three.

129
00:05:33,070 --> 00:05:35,140
Then you have zero nine and three two.

130
00:05:35,170 --> 00:05:36,310
So that's this level.

131
00:05:36,310 --> 00:05:37,210
And then you have six.

132
00:05:37,210 --> 00:05:39,700
So this is how we would picturise it right now.

133
00:05:39,700 --> 00:05:40,570
Let's proceed.

134
00:05:41,080 --> 00:05:46,510
Now notice that the Leafs over here are 693 and two.

135
00:05:46,540 --> 00:05:47,020
All right.

136
00:05:47,020 --> 00:05:51,130
Now over here there is another interesting thing that you can see.

137
00:05:51,130 --> 00:05:54,580
The leaf nodes always follow the heap property.

138
00:05:54,580 --> 00:05:54,910
Right.

139
00:05:54,910 --> 00:05:56,650
Because it does not have a child.

140
00:05:56,650 --> 00:06:00,490
So you can easily say that the leaf node follows the heap property.

141
00:06:00,490 --> 00:06:04,480
Or it is the greater one among its children and its children are just null, right?

142
00:06:04,660 --> 00:06:05,980
They don't have children.

143
00:06:05,980 --> 00:06:09,310
So the leaf nodes always follow the heap property.

144
00:06:09,310 --> 00:06:11,140
So that's an interesting observation.

145
00:06:11,140 --> 00:06:15,220
Now we just have to heapify the internal nodes.

146
00:06:15,220 --> 00:06:18,610
So again we want to convert this into a max binary heap.

147
00:06:18,610 --> 00:06:21,820
And the leaf nodes are already following the heap property.

148
00:06:21,820 --> 00:06:24,460
So the remaining nodes are the internal nodes.

149
00:06:24,460 --> 00:06:31,000
So we just need to call the Heapify algorithm which we just now discussed on the internal nodes.

150
00:06:31,000 --> 00:06:31,480
All right.

151
00:06:31,480 --> 00:06:36,130
Now there is one more interesting thing that you have to notice over here, which is the order in which

152
00:06:36,130 --> 00:06:40,240
you have to call the Heapify algorithm on the various internal nodes.

153
00:06:40,240 --> 00:06:45,580
Now the order to be followed is this order over here, which is bottom up, which is you have to call

154
00:06:45,580 --> 00:06:50,740
zero first, then you have to call Heapify on three, then on seven and then on four.

155
00:06:50,740 --> 00:06:52,810
Now there is an interesting reason for this.

156
00:06:52,840 --> 00:06:59,410
We have discussed that you can call or you can execute the Heapify algorithm only if all the elements

157
00:06:59,410 --> 00:07:03,310
in the left and right subtree are following the heap property.

158
00:07:03,820 --> 00:07:11,260
Now we have to call the Heapify algorithm in this order, because we can be assured that these, for

159
00:07:11,260 --> 00:07:17,650
example zero over here for for zero, its left and right subtree will follow the heap property, because

160
00:07:17,650 --> 00:07:21,490
we know that leaf nodes are always following the heap property.

161
00:07:21,490 --> 00:07:24,640
So internal nodes near the leaves, right?

162
00:07:24,640 --> 00:07:26,860
So these are the internal nodes near the leaves.

163
00:07:26,860 --> 00:07:32,830
So for them the left and right subtree will follow the heap property because for them the left and right

164
00:07:32,830 --> 00:07:34,570
subtree are just leaves.

165
00:07:34,570 --> 00:07:37,150
So this is the interesting thing you have to notice over here.

166
00:07:37,150 --> 00:07:43,240
And that's the reason that we have to call the Heapify algorithm in this order which is bottom up.

167
00:07:43,240 --> 00:07:48,040
So again remember we have to just call the bubble down function in this order.

168
00:07:48,040 --> 00:07:53,680
So that's the Heapify algorithm which we discussed is nothing but the bubble down or sift down algorithm.

169
00:07:53,680 --> 00:07:54,190
All right.

170
00:07:54,190 --> 00:07:56,470
So let's go ahead and implement that over here.

171
00:07:57,040 --> 00:08:00,700
So this is the current array which we have picturized or visualized.

172
00:08:00,700 --> 00:08:02,140
But it's not stored like this.

173
00:08:02,140 --> 00:08:03,220
It's just stored as an array.

174
00:08:03,220 --> 00:08:06,070
But we know the relationship between the parents and the children.

175
00:08:06,070 --> 00:08:09,220
So now let's call the Heapify algorithm in this order.

176
00:08:09,220 --> 00:08:10,930
First we call it on zero.

177
00:08:10,930 --> 00:08:12,610
So we have zero.

178
00:08:12,610 --> 00:08:14,800
We check its children, which is only six.

179
00:08:14,800 --> 00:08:17,680
Now this does not follow the heap property right.

180
00:08:17,680 --> 00:08:19,270
So we have to swap these two.

181
00:08:19,300 --> 00:08:21,580
So we get six over here and zero over here.

182
00:08:21,580 --> 00:08:22,690
Now we proceed.

183
00:08:22,690 --> 00:08:23,950
Now we come to three.

184
00:08:23,950 --> 00:08:29,470
And we call the Heapify algorithm or the bubble down algorithm on this node over here which is three.

185
00:08:29,470 --> 00:08:32,830
Now we can see that this is already in its correct place, right.

186
00:08:32,830 --> 00:08:35,440
Its children are not greater than this over here.

187
00:08:35,440 --> 00:08:37,210
So it's already in in the correct place.

188
00:08:37,210 --> 00:08:39,370
So we don't do anything and we move forward.

189
00:08:39,370 --> 00:08:42,670
We come to seven right now over here we have seven.

190
00:08:42,670 --> 00:08:44,620
Its two children are six and nine.

191
00:08:44,620 --> 00:08:46,270
The greater among these two is nine.

192
00:08:46,270 --> 00:08:47,920
And that's greater than seven right.

193
00:08:47,920 --> 00:08:49,330
So we have to swap these two.

194
00:08:49,360 --> 00:08:52,030
So let's get nine over here and seven over here.

195
00:08:52,030 --> 00:08:53,320
Now seven is over here.

196
00:08:53,320 --> 00:08:54,790
And it does not have any more children.

197
00:08:54,790 --> 00:08:55,690
So we can stop.

198
00:08:55,690 --> 00:08:58,750
So again now we move forward and we come to four.

199
00:08:58,750 --> 00:09:02,350
Now its children are nine and three.

200
00:09:02,350 --> 00:09:05,980
And you can see that nine is the greater one and nine is greater than four.

201
00:09:05,980 --> 00:09:06,250
Right.

202
00:09:06,250 --> 00:09:07,450
So we swap these two.

203
00:09:07,480 --> 00:09:09,820
So we get nine over here and four over here.

204
00:09:09,820 --> 00:09:11,290
Now four is over here.

205
00:09:11,290 --> 00:09:14,230
At this point again we have to check its children right.

206
00:09:14,230 --> 00:09:15,850
Its children are six and seven.

207
00:09:15,850 --> 00:09:18,460
Now the greater is seven and seven is greater than four.

208
00:09:18,460 --> 00:09:20,950
So again it does not follow the heap property.

209
00:09:20,950 --> 00:09:22,690
So we have to swap four and seven.

210
00:09:22,690 --> 00:09:25,210
So we get seven over here and four over here.

211
00:09:25,210 --> 00:09:26,320
And that's the end.

212
00:09:26,320 --> 00:09:29,050
So by this time four is in the correct place.

213
00:09:29,050 --> 00:09:33,670
So we have called the Heapify algorithm on 037 and four.

214
00:09:33,670 --> 00:09:37,150
Or we have called the bubble down algorithm on 037 and four.

215
00:09:37,150 --> 00:09:40,480
And all the internal nodes are now in their correct position.

216
00:09:40,480 --> 00:09:44,320
Now if we just write this as an array it's 973.

217
00:09:44,320 --> 00:09:47,950
And then you have six, four, three, two and zero.

218
00:09:47,950 --> 00:09:49,480
So this is the output.

219
00:09:49,480 --> 00:09:52,690
So this array over here is now a max binary heap.

220
00:09:52,690 --> 00:09:55,450
So this is how we do the build function.

221
00:09:55,450 --> 00:09:55,660
Right.

222
00:09:55,660 --> 00:09:56,650
So we have discussed this.

223
00:09:56,650 --> 00:09:58,090
So let's just keep this aside.

224
00:09:58,090 --> 00:10:00,280
So this is a valid max.

225
00:10:00,440 --> 00:10:01,610
Binary heap now.

226
00:10:01,760 --> 00:10:04,760
Now let's proceed now with the remove function.

227
00:10:04,760 --> 00:10:11,840
Because over here also we will be using the same bubble down algorithm which we had have used to uh,

228
00:10:11,840 --> 00:10:13,430
execute our build function.

229
00:10:13,430 --> 00:10:13,610
Right.

230
00:10:13,610 --> 00:10:17,180
So we called the bubble down function on many elements.

231
00:10:17,180 --> 00:10:19,010
So the same function will be used over here.

232
00:10:19,010 --> 00:10:22,040
So let's first do the remove and then we come back to insert.

233
00:10:22,040 --> 00:10:28,160
So when you remove an element from a binary heap whether it's a max binary heap or a min binary heap,

234
00:10:28,160 --> 00:10:30,440
we always remove from the root node.

235
00:10:30,440 --> 00:10:30,830
All right.

236
00:10:30,830 --> 00:10:32,810
So in this case we remove nine.

237
00:10:32,810 --> 00:10:34,040
So this is the root node.

238
00:10:34,040 --> 00:10:39,500
And because this is a max binary heap this value will be the greatest value in this whole array.

239
00:10:39,500 --> 00:10:40,100
All right.

240
00:10:40,130 --> 00:10:42,410
Now again that's an interesting thing to notice.

241
00:10:42,410 --> 00:10:46,610
So in the case of a max binary heap the root node will be the maximum value.

242
00:10:46,610 --> 00:10:50,000
And that will be the value that we take out or remove.

243
00:10:50,000 --> 00:10:53,960
And in the case of a min binary heap the root node will be the minimum value.

244
00:10:53,960 --> 00:10:55,550
And that's what we will be taking out.

245
00:10:55,550 --> 00:10:58,730
So we can call this remove function extract max.

246
00:10:58,730 --> 00:10:59,030
Right.

247
00:10:59,030 --> 00:11:01,820
So that's why we can call this extract max.

248
00:11:03,100 --> 00:11:03,730
All right.

249
00:11:03,730 --> 00:11:04,900
Now let's proceed.

250
00:11:04,900 --> 00:11:08,170
So we have discussed that we always remove from the beginning of this array.

251
00:11:08,170 --> 00:11:10,060
Let's go ahead and visualize the array.

252
00:11:10,060 --> 00:11:13,330
So we have 9736432 and zero.

253
00:11:13,330 --> 00:11:16,180
Now we always remove from the beginning right.

254
00:11:16,180 --> 00:11:17,380
So this one over here.

255
00:11:17,380 --> 00:11:19,150
So we will return this value.

256
00:11:19,150 --> 00:11:23,230
If we are we we call the extract max or the remove function.

257
00:11:23,230 --> 00:11:25,240
We return this value over here.

258
00:11:25,240 --> 00:11:30,430
Now after we have returned this value what we will do is we will take the last element which is this

259
00:11:30,430 --> 00:11:31,300
one over here.

260
00:11:31,300 --> 00:11:34,750
And we will put that over here in the root.

261
00:11:34,750 --> 00:11:34,990
Right.

262
00:11:34,990 --> 00:11:37,870
So we take the last element and we put it in the root.

263
00:11:37,870 --> 00:11:39,490
So this is the last element.

264
00:11:39,490 --> 00:11:43,090
So we can just take the last element from the array by popping it out.

265
00:11:43,090 --> 00:11:48,850
And then we set the zeroth element of the array as this element which we just now popped out.

266
00:11:48,850 --> 00:11:49,210
All right.

267
00:11:49,210 --> 00:11:51,190
So this is just returned.

268
00:11:51,190 --> 00:11:52,780
And then we pop this out.

269
00:11:52,780 --> 00:11:53,980
So this is removed right.

270
00:11:53,980 --> 00:11:55,630
And this is placed over here.

271
00:11:56,080 --> 00:11:57,310
So we have zero over here.

272
00:11:57,310 --> 00:12:00,760
Now what we do is let me just write this take this to the side.

273
00:12:00,760 --> 00:12:02,410
And it looks like this now right.

274
00:12:02,410 --> 00:12:04,450
We have removed we have just returned nine.

275
00:12:04,450 --> 00:12:08,920
We have removed this value and we have put it at the zeroth index.

276
00:12:08,920 --> 00:12:10,390
So this is how it looks now.

277
00:12:10,390 --> 00:12:13,690
Now what we will do is we will bubble down.

278
00:12:13,690 --> 00:12:13,900
Right.

279
00:12:13,900 --> 00:12:16,930
So we will bubble down or we will heapify this index.

280
00:12:16,930 --> 00:12:18,550
That is the zeroth index.

281
00:12:18,550 --> 00:12:19,600
We will just bubble down.

282
00:12:19,600 --> 00:12:19,960
All right.

283
00:12:19,960 --> 00:12:22,360
So let's see how that works out.

284
00:12:22,360 --> 00:12:24,760
Now its children are seven and three.

285
00:12:24,760 --> 00:12:26,680
Now what is maximum among these two.

286
00:12:26,710 --> 00:12:27,400
It's seven right.

287
00:12:27,400 --> 00:12:28,750
And seven is greater than zero.

288
00:12:28,750 --> 00:12:31,030
So it does not follow the max heap property.

289
00:12:31,030 --> 00:12:33,340
So we have to swap zero and seven.

290
00:12:33,340 --> 00:12:35,650
So seven comes here and zero is over here.

291
00:12:35,650 --> 00:12:38,050
Now again what are the children of zero.

292
00:12:38,050 --> 00:12:38,860
It's six and four.

293
00:12:38,860 --> 00:12:42,700
And the greater one among these two is six and six is greater than zero.

294
00:12:42,700 --> 00:12:44,950
So it does not follow the max heap property.

295
00:12:44,950 --> 00:12:46,630
So we have to swap zero and six.

296
00:12:46,630 --> 00:12:47,530
So let's do that.

297
00:12:47,530 --> 00:12:49,840
So we get six over here and zero over here.

298
00:12:49,840 --> 00:12:52,810
Now this zero is at its right place.

299
00:12:52,810 --> 00:12:56,860
So now the max binary heap looks like this right.

300
00:12:56,860 --> 00:12:59,530
We have seven six and three are its children.

301
00:12:59,530 --> 00:13:02,140
And then over here we have zero and four and three and two.

302
00:13:02,170 --> 00:13:05,170
So yes this is how it should be.

303
00:13:05,170 --> 00:13:10,750
So we removed the last element, placed it at the root, and then we bubbled it down to its correct

304
00:13:10,750 --> 00:13:11,320
position.

305
00:13:11,320 --> 00:13:17,620
So this is how we extract the maximum value or remove the root node in the case of a max binary heap.

306
00:13:17,620 --> 00:13:20,680
So we are done with the build function and the remove function.

307
00:13:20,680 --> 00:13:23,680
Now let's proceed and look at the insert function.

308
00:13:23,680 --> 00:13:26,740
So we have our max binary heap over here.

309
00:13:26,740 --> 00:13:29,020
And I've just visualized this over here.

310
00:13:29,020 --> 00:13:32,620
Now let's say we want to insert a node with value 20.

311
00:13:32,620 --> 00:13:36,190
Or let's say we want to insert 20 into this max binary heap.

312
00:13:36,670 --> 00:13:37,720
Now what do we do.

313
00:13:37,750 --> 00:13:39,070
We insert at the end.

314
00:13:39,070 --> 00:13:39,310
Right.

315
00:13:39,310 --> 00:13:41,770
We always insert or we push into the array.

316
00:13:41,770 --> 00:13:42,910
We put it over here.

317
00:13:43,390 --> 00:13:43,810
All right.

318
00:13:43,810 --> 00:13:50,620
So after we put it over here we just have to bubble up or sift up to its correct position.

319
00:13:50,620 --> 00:13:55,390
So in the case of build and remove we had a bubble down or sift down function.

320
00:13:55,390 --> 00:13:55,720
Right.

321
00:13:55,720 --> 00:13:59,560
So in the case of insert we need a bubble up or sift up function.

322
00:13:59,560 --> 00:14:01,750
So again adding here let's visualize this.

323
00:14:01,750 --> 00:14:03,280
That means we are adding it over here right.

324
00:14:03,280 --> 00:14:04,480
So let's visualize this.

325
00:14:04,480 --> 00:14:05,860
So 20 is over here now.

326
00:14:05,860 --> 00:14:11,590
Now we need to place this in the correct position such that this follows the max heap property.

327
00:14:11,590 --> 00:14:15,400
So for this we will compare this value and its parent right.

328
00:14:15,400 --> 00:14:16,540
So its parent is six.

329
00:14:16,540 --> 00:14:18,040
So we compare these two.

330
00:14:18,040 --> 00:14:20,530
Now in this case they are not in the right position.

331
00:14:20,530 --> 00:14:20,710
Right.

332
00:14:20,710 --> 00:14:22,120
Because 20 is greater than six.

333
00:14:22,120 --> 00:14:23,770
So we just swap these two.

334
00:14:23,770 --> 00:14:24,520
So let's swap it.

335
00:14:24,550 --> 00:14:27,010
We get 20 over here and six over here.

336
00:14:27,430 --> 00:14:27,760
All right.

337
00:14:27,760 --> 00:14:29,320
So this is how it looks now.

338
00:14:29,650 --> 00:14:30,970
Now again what do we do.

339
00:14:30,970 --> 00:14:32,230
We have 20 over here.

340
00:14:32,230 --> 00:14:34,060
We check this with its parent.

341
00:14:34,060 --> 00:14:36,400
So its parent is seven at this point right.

342
00:14:36,400 --> 00:14:41,110
So we compare them and we see that they are not in the correct position because 20 is greater than seven.

343
00:14:41,110 --> 00:14:41,320
Right.

344
00:14:41,320 --> 00:14:42,370
So again we swap.

345
00:14:42,370 --> 00:14:44,860
So we get seven over here and 20 over here.

346
00:14:44,860 --> 00:14:45,310
All right.

347
00:14:45,310 --> 00:14:46,630
So this is how it looks now.

348
00:14:46,630 --> 00:14:48,940
Now we compare 20 and its parent.

349
00:14:48,940 --> 00:14:51,250
So its parent is nine at this point right.

350
00:14:51,250 --> 00:14:53,230
So again they are not in the right position.

351
00:14:53,230 --> 00:14:53,920
So we swap.

352
00:14:53,920 --> 00:14:56,260
Now we have 20 over here and nine over here.

353
00:14:56,260 --> 00:14:56,980
And we stop.

354
00:14:56,980 --> 00:14:57,250
Right.

355
00:14:57,250 --> 00:14:58,810
So it does not have any more parent.

356
00:14:58,810 --> 00:15:05,320
So we bubble up or sift up until it is in the right position such that the parent is the greater value.

357
00:15:05,320 --> 00:15:07,870
Because over here we are building a max binary heap, right?

358
00:15:07,870 --> 00:15:11,320
So we bubble up until the parent is the maximum value.

359
00:15:11,320 --> 00:15:16,060
Or if it's if we get to the root, then we can stop it because it does not have a parent.

360
00:15:16,060 --> 00:15:20,020
So this is how we insert a value into the max binary heap.

361
00:15:20,020 --> 00:15:22,480
And finally let's look at the peak function.

362
00:15:22,480 --> 00:15:26,410
In the case of the peak function we just have to return the first value.

363
00:15:26,410 --> 00:15:32,200
For example, if this is our binary heap max, binary heap peaking means we are just looking at the

364
00:15:32,200 --> 00:15:32,830
root, right?

365
00:15:32,830 --> 00:15:36,490
So in the case of a max binary heap, we want to know the maximum value.

366
00:15:36,490 --> 00:15:41,500
And in the case of a min binary heap we just want to look at the minimum value without removing it.

367
00:15:41,500 --> 00:15:42,040
So that's it.

368
00:15:42,040 --> 00:15:47,020
So peaking just returns the element at the zeroth index in this array.

369
00:15:47,800 --> 00:15:47,980
Right.

370
00:15:47,980 --> 00:15:49,630
So we are just returning the first value.

371
00:15:49,630 --> 00:15:51,130
So that's the peek function.

372
00:15:51,130 --> 00:15:55,300
So we have successfully discussed how to implement these four functions.

373
00:15:55,300 --> 00:15:59,170
Now let's quickly look at the complexity analysis of our solution.

374
00:15:59,170 --> 00:16:00,280
So quickly.

375
00:16:00,280 --> 00:16:03,460
Let's recap revise what we have just now discussed.

376
00:16:03,460 --> 00:16:08,710
In the case of the build function what we are doing is we are just typifying the internal nodes and

377
00:16:08,710 --> 00:16:09,490
bottom up, right.

378
00:16:09,490 --> 00:16:11,380
So we have discussed that it should be bottom up.

379
00:16:11,380 --> 00:16:16,060
Now in the case of the insert function, what we are doing is we are inserting at the end and then we

380
00:16:16,060 --> 00:16:21,820
are bubbling up that element till it reaches its right position such that the parent is greater than

381
00:16:21,820 --> 00:16:23,080
that particular element.

382
00:16:23,080 --> 00:16:23,710
All right.

383
00:16:24,160 --> 00:16:30,190
Now in the case of the remove function or extract max, in this case, what we are doing is we will

384
00:16:30,190 --> 00:16:35,650
remove from the beginning of the array, and then we will replace it with the last element of the array.

385
00:16:35,650 --> 00:16:38,980
And then we will bubble down that element to its correct position.

386
00:16:38,980 --> 00:16:43,810
And finally in the case of the peak function we discussed, we just returned the first value in the

387
00:16:43,810 --> 00:16:44,140
array.

388
00:16:44,140 --> 00:16:46,990
So that's how we implemented these four functions.

389
00:16:46,990 --> 00:16:49,930
Now let's quickly look at the complexity analysis.

390
00:16:49,930 --> 00:16:56,080
Now in the case of the peak function it's just a it's just returning the value at the zeroth index of

391
00:16:56,080 --> 00:16:56,470
the array.

392
00:16:56,470 --> 00:17:00,280
So that's just an O of one or a constant space and time operation.

393
00:17:00,280 --> 00:17:00,760
All right.

394
00:17:00,790 --> 00:17:09,130
Now in the case of insert and remove the time complexity is O of log n and the space complexity is O

395
00:17:09,130 --> 00:17:09,490
of one.

396
00:17:09,490 --> 00:17:09,730
Right.

397
00:17:09,730 --> 00:17:12,760
So O of log n because it depends on the depth of the tree.

398
00:17:12,760 --> 00:17:12,910
Right.

399
00:17:12,910 --> 00:17:17,980
So that's the maximum number of comparisons we have to make to uh, bubble down or bubble up.

400
00:17:17,980 --> 00:17:18,190
Right.

401
00:17:18,190 --> 00:17:20,800
Because over here we have bubble up and over here we have bubble down.

402
00:17:20,800 --> 00:17:25,780
So that's actually the operation that takes time because initially we are inserting at the end or removing

403
00:17:25,780 --> 00:17:29,500
from the beginning, but then we have to bubble up or bubble down to the correct place.

404
00:17:29,500 --> 00:17:29,890
Right.

405
00:17:29,890 --> 00:17:34,510
So and again log n is the height of the tree or the maximum depth.

406
00:17:34,510 --> 00:17:36,670
We can say the height as the maximum depth right.

407
00:17:36,670 --> 00:17:41,920
So time is equal to O of log n or o of d where d is the maximum depth.

408
00:17:41,920 --> 00:17:48,820
And again remember that's because the number of comparisons is log n and we are doing one comparison

409
00:17:48,820 --> 00:17:49,630
per level.

410
00:17:49,630 --> 00:17:54,040
And again the time is taken up for these two functions, which is bubble up and bubble down.

411
00:17:54,040 --> 00:17:59,470
So the time complexity of the bubble up and bubble down function itself is O of log n.

412
00:17:59,470 --> 00:18:03,550
So we have discussed the space and time complexity of these three functions.

413
00:18:03,550 --> 00:18:07,930
And again the space complexity is one because we are not taking up any extra space.

414
00:18:08,590 --> 00:18:09,010
All right.

415
00:18:09,010 --> 00:18:10,270
Now let's proceed.

416
00:18:10,270 --> 00:18:12,700
Now what about the build function.

417
00:18:12,700 --> 00:18:18,880
Now in the case of the build function we have to do bubble down for these elements over here.

418
00:18:18,880 --> 00:18:19,360
Right.

419
00:18:19,360 --> 00:18:20,890
So we have already discussed that.

420
00:18:20,890 --> 00:18:22,210
So these are the internal nodes.

421
00:18:22,210 --> 00:18:27,220
Now we have seen that for bubbling down one element the time complexity is O of log n.

422
00:18:27,220 --> 00:18:34,030
So it may seem that the time complexity to bubble down almost n elements is o of n log n, but that

423
00:18:34,030 --> 00:18:34,990
is not the case.

424
00:18:34,990 --> 00:18:41,290
The time complexity is actually O of n, and we will see the proof for this in the next video.

425
00:18:41,290 --> 00:18:44,080
And the space complexity is again o of one.