1 00:00:00,720 --> 00:00:01,650 Welcome back. 2 00:00:01,650 --> 00:00:04,710 So we have successfully coded our max binary heap. 3 00:00:04,710 --> 00:00:05,550 We have designed it. 4 00:00:05,580 --> 00:00:09,420 Now let's take a sample input and walk through the code that we have written. 5 00:00:09,420 --> 00:00:11,970 Now first we look at the build heap function. 6 00:00:11,970 --> 00:00:15,420 And let's say that this array over here is passed to this function. 7 00:00:15,420 --> 00:00:18,120 It's eight, six, one, 15, 12 and five. 8 00:00:18,120 --> 00:00:21,480 Now we can visualize this array as a binary tree. 9 00:00:21,480 --> 00:00:23,640 In this manner we are just filling from left to right. 10 00:00:23,640 --> 00:00:27,480 So we have eight, then six and one, then 15, 12 and five. 11 00:00:27,480 --> 00:00:28,050 All right. 12 00:00:28,050 --> 00:00:29,400 So now we are over here. 13 00:00:29,400 --> 00:00:30,660 We are inside this function. 14 00:00:30,660 --> 00:00:33,900 And we find the length of the array which is equal to six over here. 15 00:00:33,900 --> 00:00:34,170 Right. 16 00:00:34,170 --> 00:00:35,850 This length is equal to six. 17 00:00:35,850 --> 00:00:38,190 Now let me just write the indices over here. 18 00:00:38,340 --> 00:00:40,140 So three four and five. 19 00:00:40,140 --> 00:00:42,450 Now we find the last parent. 20 00:00:42,450 --> 00:00:49,620 We know that the range of the internal nodes is zero to math.floor n by two minus one where n is the 21 00:00:49,620 --> 00:00:50,400 size of the array. 22 00:00:50,400 --> 00:00:52,230 So over here it's six by two. 23 00:00:52,230 --> 00:00:54,120 And my math dot floor. 24 00:00:54,120 --> 00:00:56,850 So this gives us three three minus one gives us two. 25 00:00:56,880 --> 00:01:00,150 So the last parent has the index two which is this one over here. 26 00:01:00,150 --> 00:01:01,740 And that's this element right. 27 00:01:01,740 --> 00:01:03,600 So 012. 28 00:01:03,600 --> 00:01:05,760 And then we have 345. 29 00:01:05,760 --> 00:01:08,490 So here visually we can see that these are leaf nodes. 30 00:01:08,490 --> 00:01:10,050 So they are not internal. 31 00:01:10,050 --> 00:01:12,210 So yes this is the last parent node. 32 00:01:12,210 --> 00:01:14,310 So we find that index two over here. 33 00:01:14,310 --> 00:01:16,530 Then we go from I is equal to two. 34 00:01:16,560 --> 00:01:20,700 So from I is equal to two till I is greater than equal to zero. 35 00:01:20,700 --> 00:01:22,500 So two one and zero. 36 00:01:22,500 --> 00:01:27,300 So for these values of I we will go through the for loop right. 37 00:01:27,300 --> 00:01:29,010 So we will loop again and again. 38 00:01:29,010 --> 00:01:30,360 So initially I is two. 39 00:01:30,360 --> 00:01:31,200 Then I will be one. 40 00:01:31,200 --> 00:01:32,700 Then I will be equal to zero. 41 00:01:32,700 --> 00:01:37,350 So for these values of the indices we will call the bubble down function. 42 00:01:37,350 --> 00:01:39,750 And we will pass the array and that particular index. 43 00:01:39,750 --> 00:01:40,770 And then that's it. 44 00:01:40,770 --> 00:01:43,230 So that's how our build heap function works. 45 00:01:43,230 --> 00:01:46,620 So let's try and look at the bubble down function. 46 00:01:46,620 --> 00:01:50,700 And let's see what's happening when we call this for the index two. 47 00:01:50,730 --> 00:01:52,560 So that's this element over here. 48 00:01:52,560 --> 00:01:52,950 All right. 49 00:01:52,950 --> 00:01:55,290 So over here we have our bubble down function. 50 00:01:55,770 --> 00:01:57,810 And we are calling it for index two. 51 00:01:57,810 --> 00:01:58,590 So this is zero. 52 00:01:58,590 --> 00:02:00,840 This is one and this is index two. 53 00:02:00,870 --> 00:02:01,500 All right. 54 00:02:01,500 --> 00:02:03,000 Now again this is three. 55 00:02:03,000 --> 00:02:05,160 This is four and this is five. 56 00:02:05,160 --> 00:02:06,840 Now we are inside this function. 57 00:02:06,840 --> 00:02:09,810 We find the length of the array which is equal to six over here. 58 00:02:09,810 --> 00:02:12,420 And then we say current is equal to array at index. 59 00:02:12,420 --> 00:02:17,190 And the index at this instance is equal to two because we called it for I is equal to two. 60 00:02:17,220 --> 00:02:21,840 Now the current over here is array at index two which is equal to one. 61 00:02:21,840 --> 00:02:23,310 So let me just write it like this. 62 00:02:23,310 --> 00:02:24,270 So that's current. 63 00:02:24,270 --> 00:02:26,820 So current is pointing to this node over here. 64 00:02:26,940 --> 00:02:27,450 All right. 65 00:02:27,450 --> 00:02:30,510 Now we loop again and again. 66 00:02:30,510 --> 00:02:32,130 As long as this is true. 67 00:02:32,130 --> 00:02:35,910 Now let's see when we break out we will see that we will break out over here right when. 68 00:02:35,910 --> 00:02:37,560 And again we will analyze this. 69 00:02:37,560 --> 00:02:38,760 So what happens over here. 70 00:02:38,760 --> 00:02:43,620 First we find the left hand child left and right children right. 71 00:02:43,620 --> 00:02:46,200 So left index is two into I plus one. 72 00:02:46,200 --> 00:02:49,110 So two into two is four four plus one is five. 73 00:02:49,110 --> 00:02:50,880 So this is the left child index. 74 00:02:50,880 --> 00:02:53,970 So we get that the left child index is equal to five. 75 00:02:53,970 --> 00:02:58,230 And then right child index is two into two plus two which is equal to six. 76 00:02:58,230 --> 00:03:03,750 Now again we over here we have a variable largest and it's set to null. 77 00:03:03,750 --> 00:03:07,560 So this is something that we are going to use whether we can stop or not. 78 00:03:07,560 --> 00:03:07,830 Right. 79 00:03:07,830 --> 00:03:13,830 If we find that the node is in such a position that we don't need to make any swaps, then we can stop. 80 00:03:13,830 --> 00:03:17,220 So we want to know when we can stop bubbling down. 81 00:03:17,220 --> 00:03:19,260 So we will use this variable for that. 82 00:03:19,260 --> 00:03:20,490 So initially it is null. 83 00:03:20,490 --> 00:03:25,470 And once we are through with this part, if it is still null we will break out of the while loop. 84 00:03:25,470 --> 00:03:25,830 All right. 85 00:03:25,830 --> 00:03:26,730 So that's the condition. 86 00:03:26,730 --> 00:03:28,800 Now let's look at what is happening over here. 87 00:03:28,800 --> 00:03:34,260 First we are going to check whether the left child index which is five is less than the length which 88 00:03:34,260 --> 00:03:35,100 is equal to six. 89 00:03:35,100 --> 00:03:36,720 So five is less than six. 90 00:03:36,720 --> 00:03:39,270 That means there is a valid node over here. 91 00:03:39,270 --> 00:03:39,750 All right. 92 00:03:39,750 --> 00:03:44,250 So we say left child is equal to array at left child index which is five. 93 00:03:44,250 --> 00:03:47,790 So this over here the left child is identified at this point. 94 00:03:47,790 --> 00:03:52,140 And then we are checking whether the left child is greater than the current value. 95 00:03:52,140 --> 00:03:57,210 So the left child value over here is five and is five greater than the current value which is equal 96 00:03:57,210 --> 00:03:57,780 to one. 97 00:03:57,780 --> 00:03:58,950 Yes, that is true. 98 00:03:58,950 --> 00:03:59,250 Right. 99 00:03:59,250 --> 00:03:59,850 This is true. 100 00:03:59,850 --> 00:04:01,860 So that means we need to make a swap. 101 00:04:01,860 --> 00:04:02,040 Right. 102 00:04:02,040 --> 00:04:03,570 So this order is not correct. 103 00:04:03,570 --> 00:04:05,190 We need to make a swap again. 104 00:04:05,190 --> 00:04:07,650 Remember we are building a max binary heap over here. 105 00:04:07,650 --> 00:04:10,110 So the parent has to be greater than the child. 106 00:04:10,110 --> 00:04:14,130 So over here we say that largest is equal to left child index. 107 00:04:14,130 --> 00:04:17,820 So at this point largest becomes equal to five. 108 00:04:17,820 --> 00:04:19,350 So let me just store that over here. 109 00:04:19,350 --> 00:04:20,220 This is largest. 110 00:04:20,220 --> 00:04:23,400 So largest is equal to left child index which is equal to five. 111 00:04:23,400 --> 00:04:29,070 Now we are going to check whether right child index which is six whether six is less than six which 112 00:04:29,070 --> 00:04:29,580 is false. 113 00:04:29,610 --> 00:04:29,790 Right. 114 00:04:29,790 --> 00:04:30,810 So this is not true. 115 00:04:30,810 --> 00:04:33,150 So that means that there is no child over here. 116 00:04:33,150 --> 00:04:34,980 So we don't go inside over here. 117 00:04:35,460 --> 00:04:39,270 Now over here we are going to check whether largest is null now. 118 00:04:39,270 --> 00:04:41,010 Largest is not null right. 119 00:04:41,010 --> 00:04:41,490 Largest. 120 00:04:41,490 --> 00:04:43,980 We have set it to left child index which is five. 121 00:04:43,980 --> 00:04:47,850 So that means we need to make a swap or we cannot break out of the while loop. 122 00:04:47,850 --> 00:04:51,510 So at this point we don't break and we come over here. 123 00:04:51,510 --> 00:04:55,440 And at this point we swap array at index and array at largest. 124 00:04:55,440 --> 00:04:56,910 So we swap these two right. 125 00:04:56,910 --> 00:04:59,940 So we get five over here and we get one over here. 126 00:05:00,050 --> 00:05:01,460 So these are swapped. 127 00:05:01,460 --> 00:05:06,470 And again we said that the ID is equal to largest which is equal to five. 128 00:05:06,470 --> 00:05:09,200 So now ID is equal to five. 129 00:05:09,230 --> 00:05:09,680 All right. 130 00:05:09,680 --> 00:05:11,930 So let's now just clear this up a bit. 131 00:05:11,930 --> 00:05:13,580 So let me just clear this up. 132 00:05:15,020 --> 00:05:20,690 Now at this point we have five over here and we have one over here. 133 00:05:21,050 --> 00:05:21,320 Right. 134 00:05:21,320 --> 00:05:23,900 So five is over here and one is over here. 135 00:05:23,900 --> 00:05:28,310 And we have I'd let me just write that over here ID is equal to five. 136 00:05:29,550 --> 00:05:30,930 This is the index five. 137 00:05:31,260 --> 00:05:31,740 All right. 138 00:05:31,740 --> 00:05:34,710 Now again we come and it's still true right. 139 00:05:34,710 --> 00:05:36,360 So again we come inside the while loop. 140 00:05:36,360 --> 00:05:41,310 So let me just clear this up so that we can see what's happening. 141 00:05:42,210 --> 00:05:45,090 Now we are again inside the while loop, right? 142 00:05:45,090 --> 00:05:50,880 So we come over here and we find that find the left child index two into five plus one which is ten 143 00:05:50,880 --> 00:05:52,590 plus one which is equal to 11. 144 00:05:52,590 --> 00:05:55,980 And then we find the right child index which is 12. 145 00:05:55,980 --> 00:05:59,820 So if this node had children it would have been 11 and 12. 146 00:05:59,820 --> 00:06:00,030 Right. 147 00:06:00,030 --> 00:06:02,670 So six, seven, eight nine, ten and then 11 and 12. 148 00:06:02,670 --> 00:06:05,160 So we are just finding these indexes over here. 149 00:06:05,160 --> 00:06:08,190 And then at this point largest is set to null. 150 00:06:08,190 --> 00:06:11,070 Now we are going to check whether there is a left child after all. 151 00:06:11,070 --> 00:06:11,250 Right. 152 00:06:11,250 --> 00:06:15,420 So left child index which is 11 is not less than length which is six. 153 00:06:15,420 --> 00:06:15,660 Right. 154 00:06:15,660 --> 00:06:18,720 So we don't go inside over here and we do the same thing. 155 00:06:18,750 --> 00:06:20,610 12 is 12 less than six. 156 00:06:20,610 --> 00:06:20,880 No. 157 00:06:20,880 --> 00:06:22,410 So we don't go over here as well. 158 00:06:22,410 --> 00:06:23,790 Now we come over here. 159 00:06:23,790 --> 00:06:26,190 And at this point largest is still null. 160 00:06:26,190 --> 00:06:28,410 So we understand that there is no more child. 161 00:06:28,410 --> 00:06:31,500 So we break out and we have got this structure like this. 162 00:06:31,500 --> 00:06:33,900 So we have five over here and we have one over here. 163 00:06:33,900 --> 00:06:36,900 And yes this element that is index. 164 00:06:39,230 --> 00:06:45,020 Two is been typified, or the element which was over here, which is five, is placed in its correct 165 00:06:45,020 --> 00:06:45,650 position. 166 00:06:45,650 --> 00:06:46,160 All right. 167 00:06:46,160 --> 00:06:48,950 So we have done that for I is equal to two. 168 00:06:48,950 --> 00:06:51,290 Now we go ahead and do that for I is equal to one. 169 00:06:51,290 --> 00:06:53,150 Now how does this look at this point. 170 00:06:53,150 --> 00:06:54,200 Let me just draw it over here. 171 00:06:54,200 --> 00:06:54,800 We have eight. 172 00:06:54,830 --> 00:06:57,440 We have six and we have five over here. 173 00:06:57,440 --> 00:06:59,720 And we have one over here because we swapped them. 174 00:06:59,720 --> 00:07:00,050 Right. 175 00:07:00,050 --> 00:07:00,890 We have five over here. 176 00:07:00,890 --> 00:07:01,730 We have one over here. 177 00:07:01,730 --> 00:07:04,610 And then we have 15 and we have 12 over here. 178 00:07:04,610 --> 00:07:11,330 Now we are going to again call the bubble down function for the element at index one, zero and one. 179 00:07:11,330 --> 00:07:13,370 So this is the element at index one right. 180 00:07:13,370 --> 00:07:15,410 So we are going to call the bubble down function. 181 00:07:15,410 --> 00:07:16,370 Again what will do. 182 00:07:16,370 --> 00:07:18,770 It will again let's see what's happening. 183 00:07:18,770 --> 00:07:20,720 So we have this over here we have six. 184 00:07:20,720 --> 00:07:23,270 So we come again inside we find its children. 185 00:07:23,270 --> 00:07:28,400 And then we are going to check whether the child is greater than the current. 186 00:07:28,400 --> 00:07:29,720 So that's what we're going to check. 187 00:07:29,720 --> 00:07:31,640 So what about 15 and 12. 188 00:07:31,640 --> 00:07:32,780 Yes these two are greater. 189 00:07:32,780 --> 00:07:33,950 So again we will swap. 190 00:07:33,950 --> 00:07:34,130 Right. 191 00:07:34,130 --> 00:07:37,460 So this will become 15 and this will become six. 192 00:07:37,460 --> 00:07:40,940 Now how do we ensure that we take 15 and not 12. 193 00:07:40,940 --> 00:07:42,650 So let's see that over here. 194 00:07:42,650 --> 00:07:45,440 We will see that in this case let me just bring this. 195 00:07:45,440 --> 00:07:47,270 So we have 615 and 12. 196 00:07:47,270 --> 00:07:47,720 All right. 197 00:07:47,720 --> 00:07:49,520 So let me just write that over here. 198 00:07:52,280 --> 00:07:55,250 So we have six, 15 and 12. 199 00:07:55,280 --> 00:07:57,950 Now when we come to this part of the code. 200 00:07:58,560 --> 00:07:59,970 We have found the children. 201 00:07:59,970 --> 00:08:01,170 Everything is the same thing, right? 202 00:08:01,170 --> 00:08:06,930 So once we reach over here, we will see that the left child, which is 15, is greater than current. 203 00:08:06,930 --> 00:08:10,230 So yes, largest is set to this index over here. 204 00:08:10,260 --> 00:08:10,710 All right. 205 00:08:10,710 --> 00:08:12,810 Now we come over here and we see 12. 206 00:08:12,810 --> 00:08:14,790 And we know that 12 is larger than six. 207 00:08:14,790 --> 00:08:18,660 But over here we are going to check whether largest is equal to null. 208 00:08:18,660 --> 00:08:19,830 No that is not true. 209 00:08:19,830 --> 00:08:20,010 Right. 210 00:08:20,010 --> 00:08:23,430 Because we have set largest to this index over here which is three. 211 00:08:23,430 --> 00:08:23,610 Right. 212 00:08:23,610 --> 00:08:26,760 So this is three now over here we have mentioned that right. 213 00:08:26,760 --> 00:08:27,810 So this is index three. 214 00:08:27,840 --> 00:08:30,000 Now largest is not null. 215 00:08:30,000 --> 00:08:33,270 So then we are going to check whether right child is greater than left child. 216 00:08:33,270 --> 00:08:37,020 So 12 is the right child is 12 greater than 15. 217 00:08:37,020 --> 00:08:37,470 No. 218 00:08:37,470 --> 00:08:38,640 So we don't go inside. 219 00:08:38,640 --> 00:08:40,350 We don't go over here right. 220 00:08:40,350 --> 00:08:41,160 We don't go over here. 221 00:08:41,160 --> 00:08:43,470 And largest is still equal to this. 222 00:08:43,470 --> 00:08:44,820 That is the left child index. 223 00:08:44,820 --> 00:08:47,850 And then we are going to just swap these two over here. 224 00:08:47,850 --> 00:08:48,540 That is right. 225 00:08:48,540 --> 00:08:49,380 Index is right. 226 00:08:49,380 --> 00:08:52,530 Largest and over here largest is left child index. 227 00:08:52,530 --> 00:08:56,100 And then right largest which is the left child index is equal to current. 228 00:08:56,100 --> 00:08:57,750 So these two are getting swapped. 229 00:08:57,750 --> 00:09:00,990 So we get six over here and we get 15 over here. 230 00:09:00,990 --> 00:09:02,310 And then there is no more child. 231 00:09:02,310 --> 00:09:05,580 So we will break out because largest will still be null. 232 00:09:05,580 --> 00:09:07,350 So let me just write that over here. 233 00:09:08,730 --> 00:09:11,040 So we have 15 over here and six over here. 234 00:09:13,890 --> 00:09:20,280 Now we will again call the bubble down function for the zeroth index, which is this element over here. 235 00:09:20,310 --> 00:09:22,680 Now what about eight, 15 and five? 236 00:09:22,680 --> 00:09:23,790 Are they in the right position? 237 00:09:23,790 --> 00:09:25,380 No, right 15 is greater than eight. 238 00:09:25,380 --> 00:09:27,750 So again we will swap these two values. 239 00:09:27,750 --> 00:09:31,950 We will see that this over here is not greater than this value. 240 00:09:31,950 --> 00:09:33,900 So we are only dealing with this value. 241 00:09:33,900 --> 00:09:34,980 So we swap these two. 242 00:09:34,980 --> 00:09:38,700 So we get eight over here and we get 15 over here right. 243 00:09:38,730 --> 00:09:41,070 Now what about eight six and 12. 244 00:09:41,100 --> 00:09:43,230 Is this in the correct position. 245 00:09:43,230 --> 00:09:46,380 So let's see whether this is larger than its children. 246 00:09:46,380 --> 00:09:47,760 So it's not the case right. 247 00:09:47,760 --> 00:09:49,080 12 is larger than eight. 248 00:09:49,080 --> 00:09:50,460 So again we will have to swap. 249 00:09:50,460 --> 00:09:51,750 So we'll get 12 over here. 250 00:09:51,750 --> 00:09:53,490 And we will get eight over here. 251 00:09:53,490 --> 00:09:58,110 And that gives us the uh binary max binary heap. 252 00:09:58,110 --> 00:09:58,350 Right. 253 00:09:58,350 --> 00:09:59,880 So the array now will look like this. 254 00:09:59,910 --> 00:10:06,630 We have 15, then we have 12 over here we have five over here we have six over here and we have eight 255 00:10:06,630 --> 00:10:06,990 over here. 256 00:10:06,990 --> 00:10:08,640 And yes, there is one over here. 257 00:10:09,490 --> 00:10:09,820 Right. 258 00:10:09,820 --> 00:10:11,590 So this is the array. 259 00:10:11,620 --> 00:10:15,040 Now if we are just going to write it out let me just clear this space. 260 00:10:17,590 --> 00:10:19,300 So this array will look like this. 261 00:10:19,330 --> 00:10:26,440 We have 15, 12, five, six, eight and one which is a max binary heap. 262 00:10:26,440 --> 00:10:29,260 So we have discussed the build heap function which we have written. 263 00:10:29,260 --> 00:10:32,080 And we have walked through the bubble down function which we have written. 264 00:10:32,110 --> 00:10:35,620 Now let's quickly take a look at the extract max function. 265 00:10:35,620 --> 00:10:36,520 Now over here. 266 00:10:36,520 --> 00:10:37,990 What how does it works. 267 00:10:37,990 --> 00:10:40,030 Let's say we call the extract max function. 268 00:10:40,030 --> 00:10:45,310 So we say const maximum value is this dot heap at the zeroth index which is 98. 269 00:10:45,310 --> 00:10:45,640 Right. 270 00:10:45,640 --> 00:10:48,790 So at this point maximum value is equal to 98. 271 00:10:48,790 --> 00:10:53,200 So let's do it with this sample max binary heap which I have over here. 272 00:10:53,200 --> 00:10:56,500 Now we say last is equal to this dot heap dot pop. 273 00:10:56,500 --> 00:10:56,710 Right. 274 00:10:56,710 --> 00:10:57,910 This is stored as an array. 275 00:10:57,910 --> 00:11:02,020 So the array will look like this 98 then 5782. 276 00:11:02,110 --> 00:11:06,550 And then we have 44 1175 and 22. 277 00:11:06,580 --> 00:11:10,060 So we are going to pop out the last element which is this one over here. 278 00:11:10,060 --> 00:11:10,420 Right. 279 00:11:10,420 --> 00:11:12,730 So last is 22. 280 00:11:12,760 --> 00:11:13,270 Right. 281 00:11:13,270 --> 00:11:17,530 And then we are checking whether there are still elements in the heap array. 282 00:11:17,530 --> 00:11:20,830 Once we have taken this out, which is yes which is the case. 283 00:11:20,830 --> 00:11:23,980 So we say this dot heap at zero is equal to last. 284 00:11:23,980 --> 00:11:27,430 So over here we make the value as the last which is 22. 285 00:11:27,460 --> 00:11:30,820 Now visually we can see that over here we have just taken this out. 286 00:11:30,820 --> 00:11:32,260 So this is no longer there. 287 00:11:32,260 --> 00:11:34,450 And then over here we put the value 22. 288 00:11:34,480 --> 00:11:35,590 So that is what we have done. 289 00:11:35,590 --> 00:11:41,500 Now afterwards we will call the bubble down function for this uh, which the same function which we 290 00:11:41,500 --> 00:11:43,180 have written already, which we have discussed. 291 00:11:43,180 --> 00:11:46,750 So we are passing the array and we are passing this as the index which is zero. 292 00:11:46,750 --> 00:11:48,190 So again what happens. 293 00:11:48,190 --> 00:11:49,060 Let's quickly see. 294 00:11:49,060 --> 00:11:50,320 We come over here. 295 00:11:50,350 --> 00:11:51,820 Let me just clear this up. 296 00:11:54,340 --> 00:11:58,060 So we have called the bubble down function and the array has been passed. 297 00:11:58,060 --> 00:12:00,340 And the index which is given is zero. 298 00:12:00,340 --> 00:12:00,640 All right. 299 00:12:00,640 --> 00:12:02,470 So this is the old example. 300 00:12:02,470 --> 00:12:04,180 We are dealing with the new one. 301 00:12:04,180 --> 00:12:05,770 So let me just write that over here. 302 00:12:05,770 --> 00:12:15,880 We had 98 then 57 then 82 over here and 44 and 11 and 75 and 22. 303 00:12:15,880 --> 00:12:17,920 So that's how it was looking. 304 00:12:17,920 --> 00:12:21,970 The example which we were just dealing and we popped this out and we put it over here. 305 00:12:21,970 --> 00:12:22,150 Right. 306 00:12:22,150 --> 00:12:23,590 So we have 22 over here. 307 00:12:23,590 --> 00:12:26,080 Now we are calling the bubble down function. 308 00:12:26,080 --> 00:12:29,020 Now what happens again we find the length. 309 00:12:29,020 --> 00:12:32,740 So at this point the length is 12345 and six. 310 00:12:32,740 --> 00:12:34,420 So we have the length over here as well. 311 00:12:34,420 --> 00:12:38,650 Six is also six and the current value is 22. 312 00:12:38,650 --> 00:12:40,000 So this is 22. 313 00:12:40,210 --> 00:12:42,310 Now we are going to find its children right. 314 00:12:42,310 --> 00:12:43,780 So by this part. 315 00:12:43,780 --> 00:12:47,710 So we find that one and two are its children because this is zero right. 316 00:12:47,710 --> 00:12:50,140 So zero plus one is one and zero plus two is two. 317 00:12:50,140 --> 00:12:51,460 So we find its children. 318 00:12:51,460 --> 00:12:55,720 And then over here we are going to check whether the child is greater than current. 319 00:12:55,720 --> 00:12:57,820 So is 57 greater than 22. 320 00:12:57,820 --> 00:12:58,240 Yes. 321 00:12:58,240 --> 00:13:02,620 So largest is equal to at this point left child index which is equal to one. 322 00:13:02,620 --> 00:13:08,560 Again we are going to check whether 82 over here we are seeing that largest is not null because we changed 323 00:13:08,560 --> 00:13:09,730 largest at this point. 324 00:13:09,730 --> 00:13:12,310 Now we are going to compare 82 and 57 right? 325 00:13:12,310 --> 00:13:12,670 Right. 326 00:13:12,670 --> 00:13:16,120 Child 82 is greater than left child which is 57. 327 00:13:16,120 --> 00:13:19,240 So we are changing largest to two right. 328 00:13:19,240 --> 00:13:21,340 So largest now is equal to two. 329 00:13:21,340 --> 00:13:24,610 And now we are going to swap these 282 and 22. 330 00:13:24,640 --> 00:13:26,650 So over here we get 82. 331 00:13:29,390 --> 00:13:31,640 And over here we get 22. 332 00:13:32,880 --> 00:13:33,330 All right. 333 00:13:33,330 --> 00:13:36,120 So again we come back to the while loop. 334 00:13:36,120 --> 00:13:37,140 And again we loop. 335 00:13:37,140 --> 00:13:40,110 So for this node now we find its children right. 336 00:13:40,110 --> 00:13:42,630 So this is uh one two. 337 00:13:42,660 --> 00:13:44,940 Then we have 345 and six. 338 00:13:44,940 --> 00:13:46,830 So over here we'll get five and six. 339 00:13:47,950 --> 00:13:51,040 And from this formula we will also get that right because over here it's two. 340 00:13:51,070 --> 00:13:52,270 So two into two is four. 341 00:13:52,270 --> 00:13:53,470 Four plus one is five. 342 00:13:53,470 --> 00:13:55,690 Again two into two is four four plus two is six. 343 00:13:55,690 --> 00:13:57,490 So that's how we get five and six over here. 344 00:13:57,520 --> 00:14:00,490 Now let me just make some thing clean. 345 00:14:00,490 --> 00:14:03,490 So let's just clean this up a little bit so it's legible. 346 00:14:04,030 --> 00:14:06,070 So at this point we have 82 over here. 347 00:14:06,070 --> 00:14:08,410 So let's delete everything else. 348 00:14:08,410 --> 00:14:09,730 So I have 82 over here. 349 00:14:09,730 --> 00:14:11,050 And I have 22 over here. 350 00:14:11,050 --> 00:14:13,240 So again let's clean this up as well. 351 00:14:13,240 --> 00:14:14,530 And there is nothing over here. 352 00:14:14,530 --> 00:14:16,480 So this is how it looks at this point. 353 00:14:16,480 --> 00:14:19,390 Now we found that its children are five and six. 354 00:14:19,390 --> 00:14:22,390 Now we find that yes there is a left child. 355 00:14:22,390 --> 00:14:26,800 And when we check this part right child less than length which is six is not less than six. 356 00:14:26,800 --> 00:14:27,940 So we don't come over here. 357 00:14:27,940 --> 00:14:28,240 Right. 358 00:14:28,240 --> 00:14:29,500 So there is no right child. 359 00:14:29,500 --> 00:14:34,240 Now when it comes to the left child, we find that the left child is 75 over here. 360 00:14:34,330 --> 00:14:36,580 And then we are comparing 75 and 22. 361 00:14:36,580 --> 00:14:38,530 And we see that yes a swap is required. 362 00:14:38,530 --> 00:14:41,950 So largest is set to this index over here which is zero. 363 00:14:42,190 --> 00:14:43,510 Uh this is uh five right. 364 00:14:43,510 --> 00:14:44,770 So this is index five. 365 00:14:44,770 --> 00:14:46,840 So we set that to index five. 366 00:14:46,840 --> 00:14:48,370 And over here we swap these two. 367 00:14:48,370 --> 00:14:48,610 Right. 368 00:14:48,610 --> 00:14:52,660 Right index is right largest and largest is left child index. 369 00:14:52,900 --> 00:14:55,510 So we swap them so we get 75 over here. 370 00:14:56,880 --> 00:14:59,460 And we get 22 over here at this point. 371 00:14:59,490 --> 00:15:00,960 Now let me just clean this up. 372 00:15:00,960 --> 00:15:02,280 So we have 75 over here. 373 00:15:02,280 --> 00:15:03,570 We have 22 over here. 374 00:15:03,570 --> 00:15:06,540 And again we come to the while loop over here. 375 00:15:06,540 --> 00:15:06,750 Right. 376 00:15:06,750 --> 00:15:08,640 So we are back again over here. 377 00:15:09,570 --> 00:15:12,750 Now we calculate its possible children's indices. 378 00:15:12,750 --> 00:15:13,080 Right. 379 00:15:13,080 --> 00:15:14,310 So this is, uh. 380 00:15:14,310 --> 00:15:15,090 What what was this? 381 00:15:15,090 --> 00:15:15,870 This was five. 382 00:15:15,870 --> 00:15:17,130 So five into two is ten. 383 00:15:17,130 --> 00:15:20,520 Ten plus one is 11 and ten plus two is 12. 384 00:15:20,520 --> 00:15:24,210 So 11 and 12 are the possible indexes of its children. 385 00:15:24,210 --> 00:15:29,130 And again over here we have we will check whether 11 is less than six which is wrong. 386 00:15:29,130 --> 00:15:30,420 So we don't come over here. 387 00:15:30,420 --> 00:15:33,690 Over here we will check whether 12 is less than six which is again a no. 388 00:15:33,690 --> 00:15:35,940 So we come over here and largest is still null. 389 00:15:35,940 --> 00:15:36,840 So we break out. 390 00:15:36,840 --> 00:15:40,710 So at this point we were able to extract the maximum. 391 00:15:40,710 --> 00:15:46,650 And then we ensured that the remaining elements follow the max heap property. 392 00:15:46,650 --> 00:15:49,410 So this is how the extract max function works. 393 00:15:49,410 --> 00:15:54,120 Let's look at the insert and the peek function which are the two remaining functions over here. 394 00:15:54,120 --> 00:15:56,010 First we look at the insert function. 395 00:15:56,010 --> 00:15:59,610 Let's say we want to insert the value 25. 396 00:15:59,610 --> 00:16:02,100 All right so I have a node with value 25. 397 00:16:02,100 --> 00:16:03,540 And let's say we want to insert it. 398 00:16:03,540 --> 00:16:04,530 So how does it work. 399 00:16:04,530 --> 00:16:05,880 Let's take a look at it. 400 00:16:05,880 --> 00:16:08,400 So always we will insert at the end. 401 00:16:08,430 --> 00:16:10,020 Now this is stored as an array right. 402 00:16:10,020 --> 00:16:12,090 So this will look like this 98. 403 00:16:12,090 --> 00:16:14,490 Then we have 5782. 404 00:16:14,820 --> 00:16:19,140 Then we have 44 1175 and 22. 405 00:16:19,140 --> 00:16:21,840 And we push 25 to this array. 406 00:16:21,840 --> 00:16:23,550 So we have 25 over here. 407 00:16:24,240 --> 00:16:24,540 Right. 408 00:16:24,540 --> 00:16:25,740 So we have 25 over here. 409 00:16:25,740 --> 00:16:28,470 Now visually you can see that we are just inserting it over here. 410 00:16:28,470 --> 00:16:30,270 So this is 25 at this point. 411 00:16:30,300 --> 00:16:32,250 Now what we do is we will bubble up. 412 00:16:32,250 --> 00:16:33,870 We will call the bubble up function. 413 00:16:33,870 --> 00:16:35,010 And we are over here. 414 00:16:35,010 --> 00:16:39,120 Now we say ID is equal to this dot heap dot length minus one. 415 00:16:39,120 --> 00:16:44,670 So the length at this point is 3456788 minus one is seven. 416 00:16:44,670 --> 00:16:44,880 Right. 417 00:16:44,880 --> 00:16:48,420 So the length the id at this point is equal to seven. 418 00:16:48,420 --> 00:16:49,830 Now what about value. 419 00:16:49,830 --> 00:16:51,870 Value is equal to this dot heap at id. 420 00:16:52,020 --> 00:16:54,990 So let's look at the value which is the latest one. 421 00:16:54,990 --> 00:16:55,260 Right. 422 00:16:55,260 --> 00:16:58,260 So this is 01234567. 423 00:16:58,260 --> 00:16:59,820 So that's why we calculated this. 424 00:16:59,820 --> 00:17:02,310 So we are just taking the last value and putting it over here. 425 00:17:02,310 --> 00:17:04,380 So value is equal to 25. 426 00:17:05,120 --> 00:17:05,480 All right. 427 00:17:05,480 --> 00:17:10,820 Now we are going to loop as long as ID is greater than or equal to zero, or we are going to bubble 428 00:17:10,820 --> 00:17:11,480 up right. 429 00:17:11,480 --> 00:17:16,400 So we can stop if we reach the ID as zero because there's nothing more to go up. 430 00:17:16,400 --> 00:17:16,610 Right. 431 00:17:16,610 --> 00:17:23,030 So either one condition to break out of this while loop is if ID is equal to zero, or if ID is no longer 432 00:17:23,030 --> 00:17:24,500 greater than zero, we break out. 433 00:17:24,530 --> 00:17:26,900 Now we also have a break condition over here. 434 00:17:26,900 --> 00:17:28,430 Let's discuss that now. 435 00:17:28,430 --> 00:17:31,610 Once we are inside this loop, what we do is we find its parent right? 436 00:17:31,610 --> 00:17:32,780 So its parent. 437 00:17:32,930 --> 00:17:35,360 Now at this point the index is seven. 438 00:17:35,360 --> 00:17:40,670 We know that we can find the parent by doing math dot floor seven minus one by two. 439 00:17:40,670 --> 00:17:41,000 Right. 440 00:17:41,000 --> 00:17:44,540 So seven minus two seven minus one is six six by two is three. 441 00:17:44,540 --> 00:17:46,430 So 0123. 442 00:17:46,430 --> 00:17:47,270 So this is three. 443 00:17:47,270 --> 00:17:52,520 So yes we get that the no the value at index three is its parent which is 44. 444 00:17:52,520 --> 00:17:52,760 Right. 445 00:17:52,760 --> 00:17:55,190 So we find the parent value as 44. 446 00:17:55,190 --> 00:17:57,080 Now we are going to compare these two. 447 00:17:57,110 --> 00:18:02,450 If it was the case that the value is less than the parent value which is the case over here. 448 00:18:02,450 --> 00:18:02,600 Right. 449 00:18:02,600 --> 00:18:05,240 So 25 is actually less than 44. 450 00:18:05,240 --> 00:18:06,770 In this case we can break out. 451 00:18:06,770 --> 00:18:09,560 So we are sure that it's in the correct position. 452 00:18:09,560 --> 00:18:10,970 So in this case we would break out. 453 00:18:11,000 --> 00:18:15,980 Now let's say we were inserting a value like something greater than 44 like for example 50. 454 00:18:15,980 --> 00:18:19,670 In that case we would have swapped these two values over here. 455 00:18:19,820 --> 00:18:20,210 All right. 456 00:18:20,210 --> 00:18:22,130 So that is how the insert function works. 457 00:18:22,130 --> 00:18:26,990 Now once we swap let's say we were inserting um 60 for example. 458 00:18:26,990 --> 00:18:27,260 All right. 459 00:18:27,260 --> 00:18:28,820 So let's say we were inserting 60. 460 00:18:28,820 --> 00:18:31,880 So this is 60 and this is 60. 461 00:18:32,390 --> 00:18:34,100 And this is also 60. 462 00:18:34,580 --> 00:18:36,830 So over here we are comparing 60 and 44. 463 00:18:36,830 --> 00:18:39,530 We see that they are not following the heap property. 464 00:18:39,530 --> 00:18:40,970 So we swap over here right. 465 00:18:40,970 --> 00:18:44,060 So we say this is 60 and this is 44. 466 00:18:44,060 --> 00:18:44,840 So we have swapped. 467 00:18:45,560 --> 00:18:49,850 Now we set ID is equal to parent ID which is this index over here. 468 00:18:49,850 --> 00:18:50,120 Right. 469 00:18:50,120 --> 00:18:51,290 So that is three. 470 00:18:51,290 --> 00:18:53,060 So we say ID is equal to three. 471 00:18:53,060 --> 00:18:55,250 And again id is still greater than zero. 472 00:18:55,250 --> 00:18:57,230 So we again come into the while loop. 473 00:18:57,230 --> 00:18:59,210 Now let me clean this up a little bit. 474 00:19:01,930 --> 00:19:02,200 All right. 475 00:19:02,200 --> 00:19:04,000 So we are again inside the while loop. 476 00:19:04,000 --> 00:19:06,070 And at this point ID is equal to three. 477 00:19:06,070 --> 00:19:10,300 So we do three minus one by two which is two by two which is equal to one. 478 00:19:10,300 --> 00:19:14,920 So we find that the parent is this element at index one which is 57. 479 00:19:14,920 --> 00:19:15,190 Right. 480 00:19:15,190 --> 00:19:17,950 So yes, we can see visually that it is the correct parent. 481 00:19:17,950 --> 00:19:23,830 Now again we are going to check over here whether this value which is 60, whether it is less than equal 482 00:19:23,830 --> 00:19:24,910 to the parent value. 483 00:19:24,910 --> 00:19:26,950 If that is the case we would have broken right. 484 00:19:26,950 --> 00:19:28,330 We would have broke out and come out. 485 00:19:28,330 --> 00:19:29,380 But it's not the case. 486 00:19:29,380 --> 00:19:32,170 So again in this part we are going to swap these two. 487 00:19:32,170 --> 00:19:36,760 So we get 60 over here and we get 57 over here. 488 00:19:37,920 --> 00:19:38,490 All right. 489 00:19:38,490 --> 00:19:41,490 Again it is set to the parent ID which is equal to one. 490 00:19:41,490 --> 00:19:43,020 So parent is now one. 491 00:19:43,020 --> 00:19:44,580 Again ID is greater than zero. 492 00:19:44,580 --> 00:19:46,800 So we again come inside the while loop. 493 00:19:46,800 --> 00:19:48,540 So let's clean this up. 494 00:19:48,540 --> 00:19:49,650 And again we are over here. 495 00:19:49,650 --> 00:19:51,330 So ID is equal to one. 496 00:19:51,330 --> 00:19:52,890 Now what about the parent index. 497 00:19:52,890 --> 00:19:55,470 So that's one minus one by two which is equal to zero. 498 00:19:55,470 --> 00:19:55,650 Right. 499 00:19:55,650 --> 00:19:58,860 So we get that the parent is this one over here 98. 500 00:19:58,860 --> 00:20:02,190 Now we are going to compare these two values right 98 and 60. 501 00:20:02,190 --> 00:20:06,540 And we see that value is actually less than the parent value 60 is less than 98. 502 00:20:06,540 --> 00:20:07,710 So we break out. 503 00:20:07,710 --> 00:20:11,790 And by this we have successfully inserted the element 60. 504 00:20:11,790 --> 00:20:13,230 And it's at the correct position. 505 00:20:13,230 --> 00:20:17,130 So that this is actually a binary heap a max binary heap. 506 00:20:17,130 --> 00:20:19,170 So this is how the insert function works. 507 00:20:19,170 --> 00:20:21,450 And finally let's look at the peak function. 508 00:20:21,450 --> 00:20:23,220 So let me just clear this up. 509 00:20:25,540 --> 00:20:25,960 All right. 510 00:20:25,960 --> 00:20:29,950 So we are just going to return the first value in the array. 511 00:20:29,950 --> 00:20:32,380 So we are going to store this as an array as we discussed. 512 00:20:32,380 --> 00:20:34,750 So this will be 9857. 513 00:20:34,750 --> 00:20:41,350 Again I'm coming to this example only 57 8244 1175 and 22. 514 00:20:41,350 --> 00:20:42,220 So this is the array. 515 00:20:42,250 --> 00:20:45,760 Now in the peak function we just want to know what is there over here. 516 00:20:45,760 --> 00:20:46,060 Right. 517 00:20:46,060 --> 00:20:47,200 We don't want to remove it. 518 00:20:47,200 --> 00:20:48,130 We just want to see it. 519 00:20:48,130 --> 00:20:52,810 So we will just return this dot heap at index zero which is this value over here. 520 00:20:52,810 --> 00:20:55,240 So we will just return 98 over here. 521 00:20:55,240 --> 00:20:57,010 And that is our peak function. 522 00:20:57,010 --> 00:21:00,280 Now let's quickly look at the complexities over here. 523 00:21:00,850 --> 00:21:04,210 You can see that all of these functions run in constant space right. 524 00:21:04,210 --> 00:21:06,820 We have implemented it in an iterative manner. 525 00:21:06,820 --> 00:21:10,930 So again the peak function runs in O of one time and space. 526 00:21:10,930 --> 00:21:13,120 We are just returning this value right. 527 00:21:13,120 --> 00:21:14,770 What about the insert function. 528 00:21:14,770 --> 00:21:16,990 The insert function runs in. 529 00:21:18,420 --> 00:21:20,490 O of log n time complexity. 530 00:21:20,490 --> 00:21:20,700 Right? 531 00:21:20,700 --> 00:21:23,190 So time is equal to O of log n. 532 00:21:23,190 --> 00:21:26,670 And again it's the maximum number of comparisons which are required. 533 00:21:26,670 --> 00:21:29,190 So again the binary heap can never be one sided. 534 00:21:29,190 --> 00:21:31,830 So this is going to be the best worst and average case. 535 00:21:31,830 --> 00:21:34,110 So the time complexity is O of log in. 536 00:21:34,110 --> 00:21:37,440 And log log n is the maximum depth or the height of the tree. 537 00:21:37,440 --> 00:21:43,500 And again the time complexity of the bubble up function is also O of log n space. 538 00:21:43,500 --> 00:21:47,790 Complexity of these is O of one right space is O of one space. 539 00:21:47,790 --> 00:21:49,560 Over here is also O of one. 540 00:21:49,560 --> 00:21:53,160 Now what about the bubble down function? 541 00:21:53,160 --> 00:21:57,000 This one also has a time complexity of O of log n, right? 542 00:21:57,000 --> 00:22:00,420 Again it's it depends on the number of comparisons which are required. 543 00:22:00,420 --> 00:22:05,370 And again then that will depend on the height of the tree or which is the maximum depth right which 544 00:22:05,370 --> 00:22:06,030 is log n. 545 00:22:06,030 --> 00:22:10,950 So over here also the time complexity is O of log n space complexity is O of one. 546 00:22:10,950 --> 00:22:13,530 Now what about the build heap function? 547 00:22:13,530 --> 00:22:15,120 We have discussed the proof right? 548 00:22:15,120 --> 00:22:21,630 Even though you may feel that it should be n log n, the time complexity actually is equal to o of n, 549 00:22:21,630 --> 00:22:24,750 and the space complexity is equal to O of one.