1
00:00:00,680 --> 00:00:01,550
Hi everyone.

2
00:00:01,550 --> 00:00:05,720
In this video let's discuss a new data structure called binary heaps.

3
00:00:05,720 --> 00:00:08,840
Now these are the five things that we will discuss in this video.

4
00:00:08,840 --> 00:00:11,540
First we will discuss what binary heaps are.

5
00:00:11,540 --> 00:00:15,050
Then we will go ahead and take a look at max and min binary heaps.

6
00:00:15,050 --> 00:00:19,940
And then we go on and see how we can store a binary heap as an array.

7
00:00:19,940 --> 00:00:25,250
And finally we take a look at the range of leaves and internal nodes and the Big-O of common operations

8
00:00:25,250 --> 00:00:26,420
for a binary heap.

9
00:00:26,420 --> 00:00:26,900
All right.

10
00:00:26,900 --> 00:00:28,310
So these are the five sections.

11
00:00:28,310 --> 00:00:32,630
Now let's get started with section one and take a look at what binary heaps are.

12
00:00:32,630 --> 00:00:35,690
Now over here we have two words binary and heaps.

13
00:00:35,690 --> 00:00:39,140
Now heaps over here is a tree based data structure.

14
00:00:39,530 --> 00:00:40,010
All right.

15
00:00:40,010 --> 00:00:45,860
And then we have the word binary over here indicating that every node can have at the most two children,

16
00:00:45,860 --> 00:00:48,440
which was similar to the case of a binary tree.

17
00:00:48,470 --> 00:00:53,210
Now when it comes to a binary heap, this is actually a complete binary tree.

18
00:00:53,210 --> 00:00:53,570
All right.

19
00:00:53,570 --> 00:00:55,820
So a binary heap is a complete binary tree.

20
00:00:55,820 --> 00:00:58,340
And this is a concept that we have discussed previously.

21
00:00:58,340 --> 00:01:02,180
Now we have two types of trees in a complete binary tree.

22
00:01:02,180 --> 00:01:06,470
It can either be a perfect binary tree or an almost complete binary tree.

23
00:01:06,470 --> 00:01:09,110
Now again this is not complex right.

24
00:01:09,110 --> 00:01:10,220
It's pretty straightforward.

25
00:01:10,220 --> 00:01:13,460
So if you have nodes you have to keep filling from left to right.

26
00:01:13,460 --> 00:01:15,470
And you cannot skip any position.

27
00:01:15,470 --> 00:01:15,650
Right.

28
00:01:15,650 --> 00:01:17,660
So that's how you make a complete binary tree.

29
00:01:17,660 --> 00:01:19,820
So the next node would be filled over here.

30
00:01:19,820 --> 00:01:23,570
And again if you have more nodes you have to fill from left to right.

31
00:01:23,570 --> 00:01:25,550
So the next node would come over here.

32
00:01:25,550 --> 00:01:28,430
And after this you have to fill over here right.

33
00:01:28,430 --> 00:01:30,200
So again it's pretty straightforward.

34
00:01:30,200 --> 00:01:33,950
You have to keep filling nodes from left to right to get a complete binary tree.

35
00:01:33,950 --> 00:01:37,340
And binary heaps are actually a complete binary tree.

36
00:01:37,340 --> 00:01:37,790
All right.

37
00:01:37,790 --> 00:01:41,420
So the advantage of a binary heap is that it cannot be one sided.

38
00:01:41,420 --> 00:01:44,330
Again remember when we discussed a binary search tree?

39
00:01:44,330 --> 00:01:50,000
One of the downsides is that you could actually have a valid binary search tree or a BST, which is

40
00:01:50,000 --> 00:01:50,720
one sided.

41
00:01:50,720 --> 00:01:53,210
And in that case it would look more like a linked list.

42
00:01:53,210 --> 00:01:54,110
Right now.

43
00:01:54,110 --> 00:01:55,700
Again, there is one more thing.

44
00:01:55,700 --> 00:01:58,100
So a binary heap is a complete binary tree.

45
00:01:58,100 --> 00:01:59,240
This is point number one.

46
00:01:59,240 --> 00:02:03,110
And the second point is that it satisfies the heap property.

47
00:02:03,110 --> 00:02:03,470
All right.

48
00:02:03,470 --> 00:02:06,800
So again in the case of binary search tree we had a property over there.

49
00:02:06,800 --> 00:02:10,070
Similarly in the case of a binary heap there is a heap property.

50
00:02:10,070 --> 00:02:12,950
And a binary heap satisfies the heap property.

51
00:02:12,950 --> 00:02:16,460
So let's go ahead and take a look at and try to understand what this is.

52
00:02:16,460 --> 00:02:21,410
So that brings us to the second point which is max binary heap and min binary heap.

53
00:02:21,410 --> 00:02:21,860
All right.

54
00:02:21,860 --> 00:02:25,220
So again the heap heap property can be of two types.

55
00:02:25,220 --> 00:02:32,720
So if we are discussing a max binary heap this is a tree type of data structure where every parent node

56
00:02:32,720 --> 00:02:34,910
is larger than the child node.

57
00:02:34,910 --> 00:02:35,240
All right.

58
00:02:35,240 --> 00:02:37,880
So that's why you have max over here because it's larger.

59
00:02:37,880 --> 00:02:42,830
And in the case of a min binary heap every parent will be smaller than the child.

60
00:02:42,830 --> 00:02:44,870
So this is the heap property.

61
00:02:45,560 --> 00:02:51,200
And also remember that in the case of a binary heap, there is no ordering between siblings.

62
00:02:51,200 --> 00:02:54,140
So let's take a few examples and try to understand this.

63
00:02:54,170 --> 00:02:57,140
So over here I've drawn out a few binary trees.

64
00:02:57,140 --> 00:03:01,130
You can see that every parent or every node has at the most two children.

65
00:03:01,130 --> 00:03:06,020
Now this binary tree over here is actually a max binary heap.

66
00:03:06,020 --> 00:03:08,060
Now let's take a look at the nodes.

67
00:03:08,060 --> 00:03:09,680
So over here you have 95.

68
00:03:09,680 --> 00:03:13,130
And you can see that this parent is greater than its children right.

69
00:03:13,130 --> 00:03:15,380
So 95 is greater than 50 and 45.

70
00:03:15,380 --> 00:03:19,640
Similarly 50 is greater than one and two and 45 is greater than 30.

71
00:03:19,640 --> 00:03:21,410
And then it's a complete binary tree.

72
00:03:21,410 --> 00:03:25,730
You can see that the nodes are filled from left to right, and we are not skipping any level.

73
00:03:25,730 --> 00:03:28,160
So this is actually a max binary heap.

74
00:03:28,160 --> 00:03:31,400
Now this tree over here is a min binary heap.

75
00:03:31,400 --> 00:03:31,700
All right.

76
00:03:31,700 --> 00:03:34,670
So you can see every parent is less than its child.

77
00:03:34,670 --> 00:03:36,710
So nine is less than 11 and 15.

78
00:03:36,710 --> 00:03:42,830
Similarly 11 is less than 20 and 1920 is less than 24, 15 is less than 23 and 18.

79
00:03:42,830 --> 00:03:44,810
And we are filling from left to right.

80
00:03:44,810 --> 00:03:47,030
So this is actually a min binary heap.

81
00:03:47,030 --> 00:03:52,640
Now when it comes to this binary tree over here, this cannot be a max binary heap because in that case

82
00:03:52,640 --> 00:03:55,280
you can see the greatest value is coming over here.

83
00:03:55,280 --> 00:03:55,850
All right.

84
00:03:56,270 --> 00:03:57,770
And that's not the case over here.

85
00:03:57,770 --> 00:03:57,950
Right.

86
00:03:57,950 --> 00:04:00,560
Seven is not greater than 22 and 19.

87
00:04:00,560 --> 00:04:02,870
So definitely not a max binary heap.

88
00:04:02,870 --> 00:04:05,000
But can this be a min binary heap.

89
00:04:05,000 --> 00:04:07,100
No this is not a min binary heap.

90
00:04:07,100 --> 00:04:07,700
Why is that so.

91
00:04:07,700 --> 00:04:11,180
Because over here you can see that you have 19 and 14 right.

92
00:04:11,180 --> 00:04:14,870
So over here the parent is 19 and this is 14.

93
00:04:14,870 --> 00:04:19,400
So if it was a min binary heap you would have 14 over here because the parent has to be less than the

94
00:04:19,400 --> 00:04:19,790
child.

95
00:04:19,790 --> 00:04:22,280
So this is not a min binary heap.

96
00:04:22,280 --> 00:04:23,690
So this is not a heap.

97
00:04:23,690 --> 00:04:25,760
Uh, this is not a heap at all.

98
00:04:25,760 --> 00:04:26,180
All right.

99
00:04:26,210 --> 00:04:27,860
Now what about this one over here?

100
00:04:27,860 --> 00:04:29,750
This is also not a heap.

101
00:04:29,750 --> 00:04:30,470
Why is that so?

102
00:04:30,470 --> 00:04:32,180
Because it's not complete, right?

103
00:04:32,180 --> 00:04:33,860
This is not a complete binary tree.

104
00:04:33,860 --> 00:04:36,290
Because the nodes have to be filled from left to right.

105
00:04:36,290 --> 00:04:38,210
So that's why this is also not a heap.

106
00:04:38,210 --> 00:04:40,220
And what about this binary tree over here?

107
00:04:40,220 --> 00:04:42,980
This again is not a max binary heap.

108
00:04:42,980 --> 00:04:47,000
Again, it cannot be a min binary heap because over here you can see you have 76, 50 and 40.

109
00:04:47,030 --> 00:04:47,270
Right.

110
00:04:47,270 --> 00:04:50,720
So in the case of a min binary heap the parent has to be less than the children.

111
00:04:50,720 --> 00:04:52,670
So definitely not a min binary heap.

112
00:04:52,670 --> 00:04:57,800
But this is also not a max binary heap because over here you can see you have 50 and 52.

113
00:04:57,800 --> 00:05:02,060
Now the parent should have to be greater than the children if it was a max binary heap.

114
00:05:02,060 --> 00:05:03,500
So this also is not a heap.

115
00:05:03,500 --> 00:05:07,250
So again to summarize over here we have an example of a max binary heap.

116
00:05:07,250 --> 00:05:10,100
And over here we have an example of a min binary heap.

117
00:05:10,100 --> 00:05:10,670
All right.

118
00:05:10,670 --> 00:05:12,890
So we have covered the first two points.

119
00:05:12,890 --> 00:05:16,520
Now let's see how we can represent a binary heap as an array.

120
00:05:16,520 --> 00:05:18,020
Again this is an important point.

121
00:05:18,020 --> 00:05:23,900
Now we could store a binary heap as we did for a binary search tree where we had the node class.

122
00:05:23,900 --> 00:05:25,910
And then we make a node for each value.

123
00:05:25,910 --> 00:05:27,590
So we could do it in this manner.

124
00:05:27,590 --> 00:05:31,220
But then representing a binary heap as an array is easier.

125
00:05:31,220 --> 00:05:34,610
And this is very important to know for many coding interview questions.

126
00:05:34,610 --> 00:05:36,500
So let's go ahead and learn this now.

127
00:05:36,500 --> 00:05:38,630
Now for this I have an example over here.

128
00:05:38,630 --> 00:05:41,120
So you can see that this is a max binary heap.

129
00:05:41,120 --> 00:05:42,980
Every parent is greater than the children.

130
00:05:42,980 --> 00:05:47,270
Now let's say that this binary tree over here is zero indexed.

131
00:05:47,270 --> 00:05:47,660
All right.

132
00:05:47,660 --> 00:05:50,810
So when we say that this is zero indexed what do we mean.

133
00:05:50,810 --> 00:05:53,000
So we start from here with the index zero.

134
00:05:53,000 --> 00:05:53,810
So this is zero.

135
00:05:53,810 --> 00:05:58,700
Then 123456789 1011 1213 and 14.

136
00:05:58,700 --> 00:06:02,660
So this is what we mean with a binary tree being zero indexed.

137
00:06:02,660 --> 00:06:06,140
Now if this is zero indexed and let me make some space over here.

138
00:06:06,140 --> 00:06:10,310
Let's see some relation between the parents and children's index.

139
00:06:10,310 --> 00:06:10,670
All right.

140
00:06:10,670 --> 00:06:17,090
So if you have a node over here and let's say the index of this node is n, then from over here you

141
00:06:17,090 --> 00:06:23,180
can see by taking a look at the pattern its children will have the indices two n plus one and two n

142
00:06:23,180 --> 00:06:23,870
plus two.

143
00:06:23,900 --> 00:06:24,260
All right.

144
00:06:24,260 --> 00:06:25,340
So let's take an example.

145
00:06:25,340 --> 00:06:26,480
Over here you have zero.

146
00:06:26,480 --> 00:06:31,790
Now if you substitute n is equal to zero over here you will get two into zero plus one which is one

147
00:06:31,790 --> 00:06:33,680
and two into zero plus two which is two.

148
00:06:33,680 --> 00:06:35,090
So that's one and two over here.

149
00:06:35,090 --> 00:06:36,410
Let's take another example.

150
00:06:36,410 --> 00:06:37,580
Let's say we take five.

151
00:06:37,580 --> 00:06:37,940
All right.

152
00:06:37,940 --> 00:06:42,530
So if n is equal to five this becomes two into five plus one which is 11.

153
00:06:42,530 --> 00:06:43,880
And that's what you have over here.

154
00:06:43,880 --> 00:06:46,340
And two into five which is ten plus two.

155
00:06:46,370 --> 00:06:47,630
So this becomes 12.

156
00:06:47,630 --> 00:06:49,160
And that's what you have over here.

157
00:06:49,160 --> 00:06:55,610
So you can see that if the parent index is n its children will have the indices two n plus one and two

158
00:06:55,610 --> 00:06:56,420
n plus two.

159
00:06:56,450 --> 00:06:56,900
All right.

160
00:06:56,930 --> 00:07:00,860
Now if you want to go from the child to the parent again there is a relationship.

161
00:07:00,860 --> 00:07:03,290
Let's say the child index is n.

162
00:07:03,290 --> 00:07:07,040
Now you could be either the left child or the right child.

163
00:07:07,040 --> 00:07:09,650
Right now we are just saying that the child index is n.

164
00:07:09,650 --> 00:07:15,410
In this case, the parent index can be found out by doing floor of n minus one by two.

165
00:07:15,440 --> 00:07:16,880
Again let's take an example.

166
00:07:16,880 --> 00:07:18,380
Let's say we have 11 over here.

167
00:07:18,380 --> 00:07:20,420
And we want to find the index of its parent.

168
00:07:20,420 --> 00:07:21,410
So what do we do.

169
00:07:21,410 --> 00:07:23,240
We do 11 minus one by two.

170
00:07:23,240 --> 00:07:25,250
That's ten by two which is five.

171
00:07:25,250 --> 00:07:27,200
And you can see that the parent index is five.

172
00:07:27,200 --> 00:07:33,920
Similarly if you were starting at 12 now 12 minus one gives you 11, 11 by two gives you 5.5.

173
00:07:33,920 --> 00:07:36,380
And when you floor it you will again get five.

174
00:07:36,380 --> 00:07:42,620
So you can go from the child to the parent by doing floor of n minus one by two, where n is the index

175
00:07:42,620 --> 00:07:43,280
of the child.

176
00:07:43,280 --> 00:07:45,140
Or you can go from the parent to the.

177
00:07:45,680 --> 00:07:50,000
If n is the index of the parent, you just have to do two n plus one and two n plus two.

178
00:07:50,030 --> 00:07:52,250
Now this is something very important that you should know.

179
00:07:52,250 --> 00:07:52,640
All right.

180
00:07:52,670 --> 00:07:58,790
Now using this relationship we will see how we can store this binary heap over here as an array.

181
00:07:58,820 --> 00:08:01,820
So again let's just write the array over here.

182
00:08:01,820 --> 00:08:06,830
So you have 9550, 45, 2122 etc. up to 33.

183
00:08:06,830 --> 00:08:09,890
Again we have just written it down as per these indices.

184
00:08:09,890 --> 00:08:10,190
Right.

185
00:08:10,190 --> 00:08:13,250
So that's what we said, that this binary tree over here is zero index.

186
00:08:13,250 --> 00:08:17,450
So let's write the indices of this array over here 0 to 14.

187
00:08:17,450 --> 00:08:19,490
You can see over here 95 as index zero.

188
00:08:19,490 --> 00:08:21,920
And that's where this 95 is placed at.

189
00:08:21,920 --> 00:08:24,290
For example this 30 is at index five.

190
00:08:24,290 --> 00:08:29,390
And at index five you can see you have the value 30 etc. or at index 13 you have 34.

191
00:08:29,390 --> 00:08:32,030
And you can see that's where 34 is placed.

192
00:08:32,030 --> 00:08:32,360
All right.

193
00:08:32,360 --> 00:08:35,990
So we can store this binary heap over here as this array.

194
00:08:35,990 --> 00:08:38,480
And you can see the indices are marked over here.

195
00:08:38,480 --> 00:08:38,810
All right.

196
00:08:38,810 --> 00:08:43,370
And then it's important to be able to derive the parent and child relationship.

197
00:08:43,370 --> 00:08:47,180
And for that we will make use of this relationship which we have discussed.

198
00:08:47,180 --> 00:08:47,720
All right.

199
00:08:48,110 --> 00:08:52,130
Now again let's take an example and uh, just get familiarized with this.

200
00:08:52,130 --> 00:08:57,890
Now in this array, if I want to find the children of 21, for example, what do I have to do?

201
00:08:57,890 --> 00:09:02,450
I have to take the index of 21, which is three, and then I have to do two and plus one and two and

202
00:09:02,450 --> 00:09:02,960
plus two.

203
00:09:02,990 --> 00:09:06,200
So that would be two into three plus one which gives me seven.

204
00:09:06,380 --> 00:09:10,310
And I also get two into three plus two which gives me eight.

205
00:09:10,310 --> 00:09:14,870
So you can see that the children of index three are at index seven and eight.

206
00:09:14,870 --> 00:09:17,270
And over here you can see that's actually true right.

207
00:09:17,270 --> 00:09:18,320
You have three over here.

208
00:09:18,320 --> 00:09:20,360
And the children are seven and eight.

209
00:09:20,360 --> 00:09:21,470
Indices seven and eight.

210
00:09:21,470 --> 00:09:23,210
And the values are 19 and 20.

211
00:09:23,240 --> 00:09:27,560
Now what if you wanted to find the let's say parent of 16.

212
00:09:27,560 --> 00:09:29,480
So you have this 16 over here.

213
00:09:29,480 --> 00:09:32,810
You want to find its parent again from this array over here.

214
00:09:32,810 --> 00:09:35,180
You can do that without drawing the binary tree over here.

215
00:09:35,180 --> 00:09:37,640
You just need to take its index which is ten.

216
00:09:37,640 --> 00:09:40,220
And then you have to do ten minus one which is nine.

217
00:09:40,220 --> 00:09:42,170
Nine by two gives you 4.5.

218
00:09:42,170 --> 00:09:44,150
And if you floor it you will get four.

219
00:09:44,150 --> 00:09:46,070
So four should be the parent of ten.

220
00:09:46,070 --> 00:09:47,780
So let's take a look whether that's correct.

221
00:09:47,780 --> 00:09:48,830
So you have ten over here.

222
00:09:48,830 --> 00:09:50,600
And you can see the parent is four.

223
00:09:50,600 --> 00:09:53,990
So that's how we represent a binary heap as an array.

224
00:09:53,990 --> 00:09:58,610
And this relationship helps us to identify the parent child relationship.

225
00:09:58,610 --> 00:09:59,120
All right.

226
00:09:59,150 --> 00:10:00,920
Now finally let's go.

227
00:10:01,040 --> 00:10:05,090
Go ahead and take a look at the range of leafs and internal nodes in a binary heap.

228
00:10:05,090 --> 00:10:08,600
Now for this we will make use of something that we've already discussed.

229
00:10:08,600 --> 00:10:10,640
But let's quickly mention it over here as well.

230
00:10:10,640 --> 00:10:13,880
Remember, a binary heap is a complete binary tree.

231
00:10:13,880 --> 00:10:18,830
And we have discussed that in the case of a complete binary tree previously, you can refer to that

232
00:10:18,830 --> 00:10:22,220
video where uh, it's in, it's under the section for Binary Tree.

233
00:10:22,220 --> 00:10:28,160
The range of the leaves will be floor of n by two to n minus one, and the range for the internal nodes

234
00:10:28,160 --> 00:10:35,240
will be zero to floor of n by two minus one, where n is the total number of uh values or nodes right

235
00:10:35,240 --> 00:10:36,320
in the binary tree.

236
00:10:36,320 --> 00:10:40,760
Now let's try to take a look at this formula with the array which we have.

237
00:10:40,760 --> 00:10:44,060
So this is how we represented the binary heap previously.

238
00:10:44,060 --> 00:10:45,470
Now let's write the indices.

239
00:10:45,470 --> 00:10:47,810
So we have the indices from 0 to 14.

240
00:10:47,810 --> 00:10:52,850
So that means there are a total of 15 nodes or values right in this binary tree.

241
00:10:52,850 --> 00:10:54,290
So n is equal to 15.

242
00:10:54,290 --> 00:11:00,920
Now if we find out floor of n by two that would be floor of 15 by two which is floor of 7.5 which is

243
00:11:00,920 --> 00:11:01,250
seven.

244
00:11:01,250 --> 00:11:01,580
Right.

245
00:11:01,580 --> 00:11:08,720
So again over here we know that the leaves are from seven to n minus one, which is 14, and the internal

246
00:11:08,720 --> 00:11:11,030
nodes are from 0 to 7.

247
00:11:11,030 --> 00:11:13,520
This will be seven seven minus one is six right.

248
00:11:13,520 --> 00:11:14,540
So 0 to 6.

249
00:11:14,540 --> 00:11:17,930
These are the internal nodes and 7 to 14.

250
00:11:17,930 --> 00:11:19,010
These are the leaves.

251
00:11:19,010 --> 00:11:19,460
Right.

252
00:11:19,460 --> 00:11:23,990
And again if you take a look at the structure which we have drawn previously, you can see that this

253
00:11:23,990 --> 00:11:24,770
is actually true.

254
00:11:24,770 --> 00:11:25,100
Right.

255
00:11:25,100 --> 00:11:27,920
You have leafs starting at nine at index seven.

256
00:11:27,920 --> 00:11:28,160
Right.

257
00:11:28,160 --> 00:11:29,810
So that's index seven over here.

258
00:11:29,810 --> 00:11:32,630
And 7 to 14 are leafs which is correct.

259
00:11:32,630 --> 00:11:36,980
And then 0 to 6 which are these indices are the internal nodes.

260
00:11:36,980 --> 00:11:38,030
So that's actually correct.

261
00:11:38,030 --> 00:11:38,330
Right.

262
00:11:38,330 --> 00:11:44,630
So you can see that using this relationship we can actually play around with this tree without drawing

263
00:11:44,630 --> 00:11:44,750
it.

264
00:11:44,750 --> 00:11:44,930
Right.

265
00:11:44,930 --> 00:11:46,820
So we can store this as an array.

266
00:11:46,820 --> 00:11:51,740
And again the relationship between the parent and the child is stored in this array itself.

267
00:11:51,740 --> 00:11:56,450
Because we know this relationship that if you have the parent, you can find the child by doing two

268
00:11:56,450 --> 00:11:58,670
n plus one and two n plus two.

269
00:11:58,670 --> 00:12:03,440
And from the child, if you want to go to the parent, all you have to do is just find floor of n minus

270
00:12:03,440 --> 00:12:04,250
one by two.

271
00:12:04,250 --> 00:12:10,550
And if you want to find the leafs then you can do floor of n by two to n minus one again n over here

272
00:12:10,550 --> 00:12:17,090
is the total number of values and for internal nodes the indices range from zero to floor of n by two

273
00:12:17,090 --> 00:12:17,960
minus one.

274
00:12:17,960 --> 00:12:20,600
Again, let's take an example to get more familiarized.

275
00:12:20,600 --> 00:12:22,310
Over here you have node nine.

276
00:12:22,310 --> 00:12:22,820
All right.

277
00:12:22,820 --> 00:12:26,540
Now if you want to find its parent what do you need to do.

278
00:12:26,570 --> 00:12:31,520
You have to do floor of n minus one by two which is nine minus one by two which gives you four.

279
00:12:31,520 --> 00:12:31,700
Right.

280
00:12:31,700 --> 00:12:34,610
So you can see four is the parent of index nine.

281
00:12:34,610 --> 00:12:35,330
And that's true.

282
00:12:35,360 --> 00:12:37,370
You have four over here and you have nine over here.

283
00:12:37,370 --> 00:12:39,590
Again let's practice a little bit more.

284
00:12:39,590 --> 00:12:44,960
If you want to find the children of the value 21 which is at index three, you have to do just.

285
00:12:45,090 --> 00:12:46,320
One plus one and two.

286
00:12:46,320 --> 00:12:46,860
One plus two.

287
00:12:46,860 --> 00:12:47,040
Right.

288
00:12:47,040 --> 00:12:50,310
So that's two into three plus one and two into three plus two.

289
00:12:50,310 --> 00:12:52,290
And that gives you seven and eight.

290
00:12:52,290 --> 00:12:53,730
And you can see that's actually true.

291
00:12:53,760 --> 00:12:54,780
You have three over here.

292
00:12:54,780 --> 00:12:57,000
And you have seven and eight over here.

293
00:12:57,030 --> 00:12:57,540
All right.

294
00:12:57,540 --> 00:13:01,920
So we have seen how we can actually store a binary heap as an array.

295
00:13:01,920 --> 00:13:07,920
We have seen how you can go from an index and find its children and from an index and find its parent.

296
00:13:07,920 --> 00:13:09,930
So that's actually what we want actually.

297
00:13:09,930 --> 00:13:12,690
That's the relationship when we want to store a binary heap.

298
00:13:12,690 --> 00:13:18,630
And if we can get that relationship just from an array, then there's no nothing wrong in storing the

299
00:13:18,630 --> 00:13:20,250
binary heap just as an array.

300
00:13:20,250 --> 00:13:25,650
And we've also seen how we can find the range of the indices for the internal nodes and for the leafs.

301
00:13:25,650 --> 00:13:31,710
And this will be much useful where we heapify something and we will discuss that in the in a future

302
00:13:31,710 --> 00:13:32,190
video.

303
00:13:32,190 --> 00:13:32,700
All right.

304
00:13:32,730 --> 00:13:37,800
Now let's go to the final part where we quickly discuss the big O of common operations for a binary

305
00:13:37,830 --> 00:13:38,190
heap.

306
00:13:38,190 --> 00:13:42,960
Now over here, we are not going to discuss this in detail, because there is a separate video where

307
00:13:42,960 --> 00:13:44,280
we discuss that in detail.

308
00:13:44,280 --> 00:13:47,760
But over here I'm just listing it down for the sake of completeness.

309
00:13:47,760 --> 00:13:52,620
Now, removing and inserting into a binary heap is a O of log n operation.

310
00:13:52,620 --> 00:13:53,070
All right.

311
00:13:53,070 --> 00:13:55,200
And the space complexity is O of one.

312
00:13:55,620 --> 00:13:58,380
Now this is discussed in detail in a future video.

313
00:13:58,380 --> 00:14:04,410
But then just to develop an intuition, remember, uh, a binary heap is a complete binary tree.

314
00:14:04,410 --> 00:14:09,960
And because it's balanced, because it's balanced, the maximum depth or the height of the tree will

315
00:14:09,960 --> 00:14:11,640
be of the order of log n, right?

316
00:14:11,640 --> 00:14:14,190
That would be log n, where n is the total number of values.

317
00:14:14,190 --> 00:14:16,290
So we have discussed that also in a previous video.

318
00:14:16,290 --> 00:14:22,380
And then for inserting or removing at the worst case we just need to make one comparison per one level.

319
00:14:22,380 --> 00:14:24,390
And the total number of levels will be log n.

320
00:14:24,390 --> 00:14:28,830
So that's why for removal or insertion the time complexity is O of log n.

321
00:14:28,830 --> 00:14:32,040
And then I've written down bubble down and bubble up over here again.

322
00:14:32,040 --> 00:14:32,760
Don't worry about it.

323
00:14:32,760 --> 00:14:35,250
We'll discuss that in detail in the next video.

324
00:14:35,250 --> 00:14:35,760
All right.

325
00:14:35,760 --> 00:14:41,220
Now there you can see that when you insert into a binary heap, you make use of something called bubble

326
00:14:41,220 --> 00:14:41,550
up.

327
00:14:41,550 --> 00:14:45,300
And when you remove from a binary heap, you make use of something called bubble down.

328
00:14:45,300 --> 00:14:51,840
So that's why removal or bubble down is an O of log n time operation and insertion or bubbling up is

329
00:14:51,840 --> 00:14:53,400
a O of log n time operation.

330
00:14:53,400 --> 00:14:58,200
Now, searching in a binary heap is in the worst case O of n time complexity.

331
00:14:58,200 --> 00:15:01,050
That's because there is no ordering between siblings, right?

332
00:15:01,050 --> 00:15:06,480
So in the worst case, we'll have to search every element in the binary heap and building a heap from

333
00:15:06,480 --> 00:15:06,960
an array.

334
00:15:06,960 --> 00:15:10,500
Again, this also is discussed in a future video in detail.

335
00:15:10,500 --> 00:15:13,290
That's a O of n time complexity operation.

336
00:15:13,290 --> 00:15:17,250
Now there is a proof of this which we discuss in detail in a future video.