1 00:00:00,500 --> 00:00:01,490 Welcome back. 2 00:00:01,490 --> 00:00:06,740 Let's now go ahead and construct the max binary heap, which we discussed in the previous video. 3 00:00:06,740 --> 00:00:11,600 For this we will need to write a class and let's call it max binary heap itself. 4 00:00:12,350 --> 00:00:16,070 And inside this we have our constructor. 5 00:00:17,030 --> 00:00:19,610 And we are not passing anything to the constructor. 6 00:00:21,750 --> 00:00:22,350 All right. 7 00:00:22,350 --> 00:00:25,830 And over here we just say this dot heap is an empty array. 8 00:00:25,860 --> 00:00:32,550 Now we could implement the max binary heap using a node class, etc. like we did the binary search tree. 9 00:00:32,550 --> 00:00:35,070 But over here we are going to implement it as an array. 10 00:00:35,100 --> 00:00:37,080 Now over here we need to write the functions. 11 00:00:37,080 --> 00:00:38,190 Now as per the question. 12 00:00:38,190 --> 00:00:41,310 We need to have a build heap function which will take in an array. 13 00:00:41,310 --> 00:00:46,980 And this function over here will rearrange the positions of the elements of the array such that the 14 00:00:46,980 --> 00:00:49,110 array follows the max heap property. 15 00:00:49,380 --> 00:00:50,880 That's what we are going to do over here. 16 00:00:50,880 --> 00:00:52,140 Now let's get started. 17 00:00:52,140 --> 00:00:54,030 Let's have a variable called length. 18 00:00:54,030 --> 00:00:57,690 And let that be the length of the array which is passed to the function. 19 00:00:57,690 --> 00:00:58,380 All right. 20 00:00:58,380 --> 00:01:01,830 And let's also have another variable last parent right. 21 00:01:01,830 --> 00:01:05,670 So let last parent is equal to. 22 00:01:05,670 --> 00:01:11,640 And remember the range of the internal nodes is zero to floor of n by two minus one. 23 00:01:11,640 --> 00:01:15,210 So floor of n by two minus one will be the last parent right. 24 00:01:15,210 --> 00:01:16,140 So that's not a leaf. 25 00:01:16,140 --> 00:01:17,190 So it's a parent right. 26 00:01:17,190 --> 00:01:19,890 So let's say let's find the index of that. 27 00:01:19,890 --> 00:01:21,720 So that will be math dot floor. 28 00:01:23,490 --> 00:01:27,570 And then we have already here length which is the length of the array. 29 00:01:27,600 --> 00:01:31,560 So we just need to divide that by two length divided by two. 30 00:01:31,560 --> 00:01:33,210 And then you have to subtract one from it. 31 00:01:33,210 --> 00:01:35,520 So this will be the last parents index. 32 00:01:35,520 --> 00:01:36,120 All right. 33 00:01:36,120 --> 00:01:41,640 Now as we discussed in the previous video we have to call the Heapify function bottom up right. 34 00:01:41,640 --> 00:01:44,910 So it will start from this index till zero. 35 00:01:44,910 --> 00:01:46,800 So for this we will have a for loop. 36 00:01:46,800 --> 00:01:48,210 Now let's code that. 37 00:01:49,120 --> 00:01:52,690 For let I is equal to last parent. 38 00:01:53,650 --> 00:02:00,340 And then this has to keep happening till I greater than or equal to zero and I minus minus. 39 00:02:01,270 --> 00:02:01,840 All right. 40 00:02:01,870 --> 00:02:05,980 Now for each of these indexes what we have to do is we have to just heapify it. 41 00:02:05,980 --> 00:02:06,310 Right. 42 00:02:06,310 --> 00:02:08,590 So for this we will have to write a function. 43 00:02:08,590 --> 00:02:10,180 So we call it bubble down. 44 00:02:10,180 --> 00:02:10,510 All right. 45 00:02:10,510 --> 00:02:12,700 So this dot bubble down. 46 00:02:14,730 --> 00:02:19,860 And then over here we will pass the array and then we will pass this particular index which is I. 47 00:02:20,980 --> 00:02:21,280 All right. 48 00:02:21,280 --> 00:02:22,390 So that's that's the end. 49 00:02:22,390 --> 00:02:22,600 Right. 50 00:02:22,600 --> 00:02:28,270 So by this time the array will be rearranged such that it follows the max heap property. 51 00:02:28,270 --> 00:02:33,400 And then we just have to set this over here which is an empty array to the array at this point. 52 00:02:33,400 --> 00:02:33,580 Right. 53 00:02:33,580 --> 00:02:35,140 So we are doing it in place. 54 00:02:35,140 --> 00:02:37,480 So over here we can just say this dot heap. 55 00:02:39,990 --> 00:02:41,370 Is equal to the array. 56 00:02:42,890 --> 00:02:44,690 And then we will just return this, right? 57 00:02:44,690 --> 00:02:45,860 We can just return. 58 00:02:47,030 --> 00:02:47,810 This. 59 00:02:47,810 --> 00:02:49,460 So that's just optional. 60 00:02:49,460 --> 00:02:53,990 So over here we are just returning this so that when we call this function we can see the output. 61 00:02:53,990 --> 00:02:54,620 All right. 62 00:02:54,620 --> 00:02:56,780 Now we need to write this function. 63 00:02:56,780 --> 00:02:57,650 Let's continue. 64 00:02:57,650 --> 00:03:00,620 So this will be a function again we will write it over here. 65 00:03:00,620 --> 00:03:02,540 Let's have it bubble down. 66 00:03:04,130 --> 00:03:07,670 Now this is just the Heapify algorithm, right? 67 00:03:07,670 --> 00:03:10,640 So this has to just heapify that particular index. 68 00:03:10,640 --> 00:03:12,590 So again it receives an array. 69 00:03:12,590 --> 00:03:14,060 So let's write that over here. 70 00:03:14,800 --> 00:03:15,730 And an index. 71 00:03:15,730 --> 00:03:17,050 Let's call the index ID. 72 00:03:17,470 --> 00:03:19,090 Now what does it do. 73 00:03:19,090 --> 00:03:20,830 Let's again think about it. 74 00:03:20,830 --> 00:03:22,750 We have to bubble down right. 75 00:03:22,750 --> 00:03:25,840 So it has we have to find its child two children. 76 00:03:25,840 --> 00:03:27,520 We have to look at the greater child. 77 00:03:27,520 --> 00:03:33,040 And then if the greater child is greater than that particular element at that index, then we have to 78 00:03:33,040 --> 00:03:33,340 swap. 79 00:03:33,340 --> 00:03:38,650 And we have to keep doing that until, uh, the element is greater than its children, which is the 80 00:03:38,650 --> 00:03:39,730 max heap property. 81 00:03:39,730 --> 00:03:40,750 So let's do that. 82 00:03:40,750 --> 00:03:45,550 So over here again let me have a variable const length is equal to array dot length which is the length 83 00:03:45,550 --> 00:03:46,150 of the array. 84 00:03:47,330 --> 00:03:50,030 And let's say the current element is array at I. 85 00:03:50,060 --> 00:03:54,110 So again I say const current is equal to. 86 00:03:55,060 --> 00:03:56,050 Array at ID. 87 00:03:57,600 --> 00:03:58,710 Which is the index. 88 00:03:58,710 --> 00:04:00,570 And again we are passing this over here. 89 00:04:00,570 --> 00:04:00,720 Right. 90 00:04:00,720 --> 00:04:02,400 So we are passing that index over here. 91 00:04:02,400 --> 00:04:07,080 So at this instance of the bubble down function we are just dealing with this element. 92 00:04:07,080 --> 00:04:08,670 So that's why I've made it a const. 93 00:04:08,670 --> 00:04:09,270 All right. 94 00:04:09,300 --> 00:04:10,800 Now we keep looping. 95 00:04:10,800 --> 00:04:14,790 So let's say while true and we will have some condition to break out of it. 96 00:04:14,790 --> 00:04:15,930 So we'll discuss that. 97 00:04:15,930 --> 00:04:17,340 Now what do we do. 98 00:04:17,340 --> 00:04:19,110 We have to find its children right. 99 00:04:19,110 --> 00:04:21,480 So let's say let left child. 100 00:04:22,870 --> 00:04:32,920 ID is equal to two into id plus one, and the right child index will be two into id plus two. 101 00:04:32,950 --> 00:04:33,190 Right. 102 00:04:33,190 --> 00:04:33,850 So let's do that. 103 00:04:33,850 --> 00:04:35,290 Let write. 104 00:04:36,170 --> 00:04:41,750 Child ID is equal to two into id x plus two. 105 00:04:41,990 --> 00:04:42,380 All right. 106 00:04:42,380 --> 00:04:43,970 So we have found the children. 107 00:04:43,970 --> 00:04:46,790 Now again let's have two variables to hold the value. 108 00:04:46,790 --> 00:04:49,130 Let left child and right child. 109 00:04:49,130 --> 00:04:53,990 Again we're not directly doing it because it may be a case that there is no child. 110 00:04:53,990 --> 00:04:54,170 Right. 111 00:04:54,170 --> 00:04:58,850 So it may be out of bound or it this index may turn out to be greater than the length. 112 00:04:58,850 --> 00:04:59,030 Right. 113 00:04:59,030 --> 00:05:02,330 So then in that case we will not be able to find this left child. 114 00:05:02,330 --> 00:05:06,740 So over here I'm just creating the variables left child and right child. 115 00:05:07,540 --> 00:05:12,760 Now, before we assign the value, we will check whether the index is within the range. 116 00:05:12,760 --> 00:05:13,270 All right. 117 00:05:13,270 --> 00:05:19,420 And finally we will also need another variable to see whether we need to continue or whether we can 118 00:05:19,420 --> 00:05:20,050 come out right. 119 00:05:20,080 --> 00:05:25,240 Now we can come out if the children are lesser than in this case, the current element. 120 00:05:25,240 --> 00:05:25,480 Right. 121 00:05:25,480 --> 00:05:26,200 Are I at ID? 122 00:05:26,470 --> 00:05:30,100 If the children of this are less than this, then we can come out right. 123 00:05:30,100 --> 00:05:32,260 So we will need to keep track of that. 124 00:05:32,260 --> 00:05:33,940 So for this let's have largest. 125 00:05:33,940 --> 00:05:35,380 Initially it will be null. 126 00:05:35,410 --> 00:05:42,160 Now in case the children are less than the current element then we will keep it null and we'll just 127 00:05:42,160 --> 00:05:42,640 check null. 128 00:05:42,640 --> 00:05:44,830 And if it's null we will come out of the while loop. 129 00:05:44,830 --> 00:05:50,380 Now if it's not null, we'll identify with which among these two children we should swap this element. 130 00:05:50,380 --> 00:05:54,040 So we will use this for that for tracking that index. 131 00:05:54,040 --> 00:05:54,700 All right. 132 00:05:54,730 --> 00:05:55,930 Now let's continue. 133 00:05:55,930 --> 00:05:58,810 Now let's say if the left child index. 134 00:05:58,810 --> 00:06:02,380 So we are going to see whether the left child and right child are there or not. 135 00:06:02,380 --> 00:06:05,380 So for this we will just say left child index. 136 00:06:05,380 --> 00:06:07,780 If it is less than the length right. 137 00:06:07,780 --> 00:06:10,780 So if it's less than the length so it's within the bounds. 138 00:06:10,780 --> 00:06:16,330 So in this case we can say left child is equal to we can say left child is equal to array. 139 00:06:17,750 --> 00:06:19,580 At left child index. 140 00:06:19,940 --> 00:06:20,210 Right. 141 00:06:20,210 --> 00:06:24,410 So this is just to ensure that this is actually a valid child. 142 00:06:24,410 --> 00:06:26,600 So we are just checking whether it's within the length. 143 00:06:26,600 --> 00:06:31,700 And if it's so then we are finding left child is equal to array at left child dot index if left child 144 00:06:31,700 --> 00:06:32,180 index. 145 00:06:32,180 --> 00:06:32,660 All right. 146 00:06:32,660 --> 00:06:34,310 So we have found the left child. 147 00:06:34,310 --> 00:06:38,990 Now we have to check whether we have to change this or not like largest. 148 00:06:38,990 --> 00:06:43,250 So we are going to use this to track whether we need to swap anything or not. 149 00:06:43,250 --> 00:06:52,370 Now for this let's check whether the left child is actually bigger than the uh, the current element. 150 00:06:52,370 --> 00:06:54,230 So we'll do it inside over here only. 151 00:06:54,230 --> 00:07:01,310 So if left child, if it is larger than the current element, what do we do in this case? 152 00:07:01,310 --> 00:07:06,380 In this case we say that largest is equal to left child index. 153 00:07:06,710 --> 00:07:10,040 So that means that we have to swap it with the left child index. 154 00:07:10,040 --> 00:07:12,590 But hold on, we have not yet checked the right child. 155 00:07:12,590 --> 00:07:14,660 Now let's do the same thing for the right child. 156 00:07:14,660 --> 00:07:15,500 So if. 157 00:07:16,920 --> 00:07:19,020 Right child index is less than length. 158 00:07:19,020 --> 00:07:21,420 So there is a right child. 159 00:07:21,420 --> 00:07:21,960 All right. 160 00:07:21,960 --> 00:07:26,040 So we say right child is equal to array at. 161 00:07:26,760 --> 00:07:28,110 Right child index. 162 00:07:28,230 --> 00:07:30,390 So we have found the right child. 163 00:07:30,390 --> 00:07:35,670 Now we have to see whether we need to change the value of the largest. 164 00:07:35,670 --> 00:07:37,170 So what are the possibilities. 165 00:07:37,170 --> 00:07:37,380 Right. 166 00:07:37,380 --> 00:07:40,470 So there is a possibility that largest is still null. 167 00:07:40,470 --> 00:07:44,310 Or there is a possibility that largest is equal to the left child index. 168 00:07:44,310 --> 00:07:45,480 So let's check that. 169 00:07:45,480 --> 00:07:46,950 So let me write the condition. 170 00:07:46,950 --> 00:07:47,940 So if. 171 00:07:48,860 --> 00:07:50,330 I'm saying largest. 172 00:07:51,070 --> 00:07:53,770 Is equal to null, right? 173 00:07:53,770 --> 00:07:57,220 So that means that left child is not greater than current. 174 00:07:57,220 --> 00:08:03,340 So if this is the case then if we want to swap, at least the right child should be greater than the 175 00:08:03,340 --> 00:08:03,730 current. 176 00:08:03,730 --> 00:08:03,910 Right. 177 00:08:03,910 --> 00:08:07,390 So we say and right child greater than current. 178 00:08:07,960 --> 00:08:08,260 All right. 179 00:08:08,260 --> 00:08:10,660 So if this is the case then we need to swap. 180 00:08:10,660 --> 00:08:12,670 Our largest should be the right child index. 181 00:08:12,670 --> 00:08:14,530 Now this is one possibility. 182 00:08:14,530 --> 00:08:16,810 Or what is the other possibility. 183 00:08:16,810 --> 00:08:18,640 The other possibility is that. 184 00:08:19,330 --> 00:08:21,190 Largest is not null. 185 00:08:21,190 --> 00:08:21,520 Right? 186 00:08:21,520 --> 00:08:24,790 So again earlier I discussed there are two possibilities. 187 00:08:24,790 --> 00:08:27,610 Largest can be null or largest is not null. 188 00:08:27,610 --> 00:08:30,850 So over here we have dealt with the case where largest is is null. 189 00:08:30,850 --> 00:08:32,740 Now what if largest is not null. 190 00:08:32,740 --> 00:08:34,510 So let let's write that over here. 191 00:08:34,510 --> 00:08:41,380 If largest is not null and if right child is greater than left child right. 192 00:08:41,380 --> 00:08:43,090 So again what is this over here? 193 00:08:43,090 --> 00:08:46,810 Largest is not null means the child. 194 00:08:46,810 --> 00:08:50,740 The previous child over here is actually greater than the current. 195 00:08:50,740 --> 00:08:50,920 Right. 196 00:08:50,920 --> 00:08:55,660 So this if only if left child is greater than current largest is equal to left child index. 197 00:08:55,660 --> 00:08:58,510 So only in this case largest is not equal to null. 198 00:08:58,510 --> 00:09:01,510 So we know that the left child is greater than the current element. 199 00:09:01,540 --> 00:09:06,580 Now already we have stored the left child index as largest. 200 00:09:06,580 --> 00:09:07,060 We are. 201 00:09:07,060 --> 00:09:10,960 We are seeing whether we need to change this to the right child index for this. 202 00:09:10,960 --> 00:09:14,950 If this is the case, then right child has to be greater than left child. 203 00:09:14,950 --> 00:09:17,950 If this is true, then if any of these is true right? 204 00:09:17,950 --> 00:09:19,240 So this is an or operator. 205 00:09:19,240 --> 00:09:20,980 So if any of these is true. 206 00:09:20,980 --> 00:09:25,060 So let me just have brackets over here so that this is one if condition. 207 00:09:25,060 --> 00:09:30,430 So if any of these is true then we have to set largest to right child index. 208 00:09:32,070 --> 00:09:32,460 All right. 209 00:09:32,460 --> 00:09:34,410 So what is it that we have done over here? 210 00:09:35,070 --> 00:09:38,250 In this part, we are checking whether there is a left child. 211 00:09:38,250 --> 00:09:42,390 If there is a left child, we are checking whether the left child is greater than the current which 212 00:09:42,390 --> 00:09:44,640 is the array at ID, right. 213 00:09:44,640 --> 00:09:46,890 So we have set current is equal to array ID. 214 00:09:47,190 --> 00:09:51,720 So if there is a left child we are checking whether that child is greater than the current element. 215 00:09:51,720 --> 00:09:54,960 If so we are setting largest to left child index. 216 00:09:54,960 --> 00:10:00,180 Now we over here we are checking whether we need to change the largest to right child index. 217 00:10:00,180 --> 00:10:05,760 Again remember we have to swap the current element with the larger one among the two children, right? 218 00:10:05,760 --> 00:10:09,030 The two children may be both of them are greater than the current. 219 00:10:09,030 --> 00:10:12,690 In that case, we have to swap it with the larger one and maybe only one of them. 220 00:10:12,690 --> 00:10:16,620 So maybe the left child is smaller than the right child then the current element. 221 00:10:16,620 --> 00:10:20,220 So in this case it will it will be still largest will still be null over here. 222 00:10:20,220 --> 00:10:22,920 And then we come over here and we see largest is still null. 223 00:10:22,920 --> 00:10:26,190 And then if the right child is greater than current we need to swap. 224 00:10:26,190 --> 00:10:26,640 All right. 225 00:10:26,640 --> 00:10:30,030 So we are setting largest is equal to right child ID over here. 226 00:10:30,750 --> 00:10:31,320 All right. 227 00:10:31,320 --> 00:10:36,810 Now now once we are done with this all we need to do is we need to check whether largest is still null 228 00:10:36,810 --> 00:10:37,530 or not. 229 00:10:37,530 --> 00:10:42,210 So let's write that if largest is equal to null right. 230 00:10:42,210 --> 00:10:45,810 So that means both the children are less than the current element. 231 00:10:45,810 --> 00:10:47,760 And in this case we can just break right. 232 00:10:47,760 --> 00:10:49,290 So we can just break and come out. 233 00:10:49,290 --> 00:10:54,270 So let me just write it in a succinct manner so I can just write it over here. 234 00:10:54,270 --> 00:10:56,940 So if largest is null then we can just break. 235 00:10:56,940 --> 00:10:57,150 Right. 236 00:10:57,150 --> 00:10:59,430 So there's no more swaps to be done. 237 00:10:59,430 --> 00:11:00,300 We come out. 238 00:11:00,300 --> 00:11:04,020 Now if that is not the case then we have to swap, right? 239 00:11:04,020 --> 00:11:06,000 So if that's not the case we will swap. 240 00:11:06,000 --> 00:11:13,920 So we have to swap array at ID and the array at the largest right. 241 00:11:13,920 --> 00:11:20,280 Whether it's the smaller left child or the larger uh right side child, any of the it can be either 242 00:11:20,280 --> 00:11:22,050 the left child or the right child. 243 00:11:22,890 --> 00:11:26,970 So we say array at largest and then we say array at largest. 244 00:11:29,370 --> 00:11:30,750 Is equal to. 245 00:11:31,660 --> 00:11:34,510 Current because we have stored that already over here. 246 00:11:34,510 --> 00:11:34,930 Right? 247 00:11:34,930 --> 00:11:37,360 We have stored current over here, which is R-rated. 248 00:11:37,720 --> 00:11:41,170 So that's why we did not use any other variable over here for swapping. 249 00:11:41,170 --> 00:11:45,490 So R-rated is equal to array at largest and array largest is equal to current. 250 00:11:45,490 --> 00:11:46,450 So we are swapping. 251 00:11:46,450 --> 00:11:51,190 Now the last thing is we just need to set ID is equal to largest. 252 00:11:52,060 --> 00:11:52,420 All right. 253 00:11:52,420 --> 00:11:53,800 Because we have to go down. 254 00:11:53,800 --> 00:11:53,980 Right. 255 00:11:53,980 --> 00:11:55,570 So this is the bubble down function. 256 00:11:55,570 --> 00:11:57,640 So let's say we did a swap. 257 00:11:57,640 --> 00:12:03,820 Remember we have discussed that again the in the new position we have to check that element and its 258 00:12:03,820 --> 00:12:06,640 children whether further swaps are required or not. 259 00:12:06,640 --> 00:12:09,580 So that's why we have the while loop over here. 260 00:12:09,580 --> 00:12:15,730 So this will keep continuing until the situation is such that largest is still null, which means that 261 00:12:15,730 --> 00:12:18,880 both the children are less than the current element. 262 00:12:18,880 --> 00:12:22,210 In that case, the element is at its right position, right? 263 00:12:22,210 --> 00:12:23,050 So we are done. 264 00:12:23,050 --> 00:12:26,050 And, uh, let's test our code. 265 00:12:26,050 --> 00:12:26,740 All right. 266 00:12:27,470 --> 00:12:28,250 So. 267 00:12:28,910 --> 00:12:30,650 Let's just do that over here. 268 00:12:30,650 --> 00:12:33,110 So we have the max binary heap. 269 00:12:33,110 --> 00:12:36,560 So let's create an object of this class right. 270 00:12:36,560 --> 00:12:42,590 So let's say um let heap is equal to new. 271 00:12:43,570 --> 00:12:45,160 Max binary heap. 272 00:12:46,790 --> 00:12:47,270 All right. 273 00:12:47,270 --> 00:12:52,580 Now we will just call the build heap function heap dot build heap. 274 00:12:52,580 --> 00:12:54,410 And we have to pass in an array. 275 00:12:54,410 --> 00:12:54,620 Right. 276 00:12:54,620 --> 00:12:56,570 So that's how we do it. 277 00:12:56,570 --> 00:12:58,250 So let's pass in an array. 278 00:12:58,250 --> 00:13:01,700 So let's say we have the same array for. 279 00:13:02,670 --> 00:13:03,630 Seven. 280 00:13:04,390 --> 00:13:12,820 309326, the same one which we used in the concept video. 281 00:13:12,820 --> 00:13:16,090 Now let's call, let's run it and see what's happening. 282 00:13:17,630 --> 00:13:17,990 All right. 283 00:13:17,990 --> 00:13:19,280 So we have. 284 00:13:20,180 --> 00:13:23,810 The heap object over here, and it has eight elements. 285 00:13:24,430 --> 00:13:29,470 And we see it's 97364320 which is correct. 286 00:13:29,470 --> 00:13:29,770 Right. 287 00:13:29,770 --> 00:13:34,060 So we have used the same example which we used in the uh explanation video. 288 00:13:34,060 --> 00:13:35,590 So we use the same array. 289 00:13:35,590 --> 00:13:39,730 And you can see that the elements now follow the max heap property. 290 00:13:39,730 --> 00:13:41,860 So our build heap function is working. 291 00:13:41,860 --> 00:13:46,360 Now let's proceed and go ahead and write the next function which is extract Max. 292 00:13:46,360 --> 00:13:52,120 Let's start with uh extract max because it's very much similar to the build heap because over there 293 00:13:52,120 --> 00:13:54,340 also we'll have this Heapify algorithm used. 294 00:13:54,340 --> 00:13:54,640 Right. 295 00:13:54,640 --> 00:13:57,130 So we will use bubble down there also when we remove. 296 00:13:57,130 --> 00:13:58,570 So let's go ahead and write that. 297 00:13:58,570 --> 00:14:01,090 So this is the bubble down function. 298 00:14:01,090 --> 00:14:03,760 So below that let's write extract max. 299 00:14:05,660 --> 00:14:05,930 All right? 300 00:14:05,930 --> 00:14:07,460 And we don't need to pass anything. 301 00:14:07,460 --> 00:14:09,680 We are just extracting the maximum value. 302 00:14:09,680 --> 00:14:11,390 All right, so let's get started. 303 00:14:11,840 --> 00:14:19,100 Now we have a variable let's say maximum value because this is a max binary heap. 304 00:14:19,100 --> 00:14:24,380 So when we extract the first element from the array we will get the maximum value. 305 00:14:24,380 --> 00:14:30,350 So this will be equal to this dot heap and the element at zeroth index right in this array. 306 00:14:30,350 --> 00:14:32,210 So that would be the maximum value. 307 00:14:32,210 --> 00:14:34,850 Now let's go ahead and complete this. 308 00:14:34,850 --> 00:14:39,320 So we also need to pop or take out the last element from that array. 309 00:14:39,320 --> 00:14:39,560 Right. 310 00:14:39,560 --> 00:14:44,210 So let's say const last is equal to this dot heap. 311 00:14:45,510 --> 00:14:46,800 Dot pop. 312 00:14:47,070 --> 00:14:47,430 Right. 313 00:14:47,430 --> 00:14:49,320 So we get the last element out. 314 00:14:49,320 --> 00:14:54,000 Now we need to check whether the heap is now empty or not. 315 00:14:54,000 --> 00:14:54,210 Right. 316 00:14:54,210 --> 00:14:58,020 Because we are now going to reinsert that element in its right position. 317 00:14:58,020 --> 00:14:59,100 That's what we're doing, right. 318 00:14:59,100 --> 00:15:05,190 We are taking this value out and we will place it in the first value, and then we will bubble it down 319 00:15:05,190 --> 00:15:06,300 to its correct position. 320 00:15:06,300 --> 00:15:07,200 So that's what we are. 321 00:15:07,230 --> 00:15:08,250 That is what we are going to do. 322 00:15:08,250 --> 00:15:08,520 Right. 323 00:15:08,520 --> 00:15:13,680 But we need to do that only if the heap is not empty, if this is the last element, if we just took 324 00:15:13,680 --> 00:15:18,480 out the last element, if there was just one element, let's say the array was looking something like 325 00:15:18,480 --> 00:15:21,450 this, it just had one element. 326 00:15:21,720 --> 00:15:23,580 Let's say this is our max binary heap. 327 00:15:23,580 --> 00:15:26,850 In this case, if we just take out the ten it should be empty, right? 328 00:15:26,850 --> 00:15:28,500 We don't need to insert it back. 329 00:15:28,500 --> 00:15:34,560 So we need to insert it back only if the length of the array at this point is greater than zero. 330 00:15:34,560 --> 00:15:36,090 So let's put that check over here. 331 00:15:36,090 --> 00:15:37,590 If this dot heap. 332 00:15:38,500 --> 00:15:41,140 Dot length greater than zero. 333 00:15:41,620 --> 00:15:44,620 Now, if this is the case, then we have to put it back. 334 00:15:44,620 --> 00:15:47,110 And then we have to bubble down to its correct position. 335 00:15:47,110 --> 00:15:47,320 Right. 336 00:15:47,320 --> 00:15:53,920 So we say this dot heap at index zero that would be equal to last right. 337 00:15:53,920 --> 00:15:58,630 So this value over here the last value is taken and put into the first value. 338 00:15:58,630 --> 00:16:00,460 Now we just have to bubble down right. 339 00:16:00,460 --> 00:16:03,760 So we say this dot bubble down or heapify. 340 00:16:05,280 --> 00:16:09,390 And in this case we pass the whole heap which is an array. 341 00:16:09,390 --> 00:16:09,600 Right. 342 00:16:09,600 --> 00:16:11,610 So array and then the index is zero. 343 00:16:11,610 --> 00:16:15,120 Now we are using the same function bubble down which we wrote over here as well. 344 00:16:15,120 --> 00:16:15,360 Right. 345 00:16:15,360 --> 00:16:21,720 For the build heap uh function over here also we were bubbling down on each element over here. 346 00:16:21,720 --> 00:16:23,580 The parameters are array and index. 347 00:16:23,580 --> 00:16:28,320 Now when we call bubble down over here we pass in the heap this dot heap. 348 00:16:28,320 --> 00:16:29,850 And the index is zero right. 349 00:16:29,850 --> 00:16:33,090 So we are going to uh heapify. 350 00:16:33,090 --> 00:16:37,470 Or we are going to put the element in the zeroth index in the correct place. 351 00:16:37,470 --> 00:16:41,160 Because over here we have inserted the last element in the zeroth index. 352 00:16:41,160 --> 00:16:41,640 All right. 353 00:16:41,640 --> 00:16:42,300 So that is it. 354 00:16:42,300 --> 00:16:43,980 So this should work. 355 00:16:43,980 --> 00:16:47,970 Now at the end let's just return the maximum value. 356 00:16:47,970 --> 00:16:48,390 All right. 357 00:16:48,390 --> 00:16:49,980 So let's just return that. 358 00:16:51,240 --> 00:16:53,970 Return maximum value and that's that. 359 00:16:53,970 --> 00:16:56,520 So we are done with our extract max function. 360 00:16:56,520 --> 00:16:57,660 Now let's check it. 361 00:16:58,520 --> 00:17:01,220 Now, over here, we have our heap. 362 00:17:01,220 --> 00:17:03,050 Let's just, uh, run this. 363 00:17:05,290 --> 00:17:06,100 And. 364 00:17:07,640 --> 00:17:09,950 If we look at our heap, we can see. 365 00:17:11,260 --> 00:17:12,670 These are the elements over here. 366 00:17:12,670 --> 00:17:15,220 97364320. 367 00:17:15,220 --> 00:17:17,140 Now let's call heap dot. 368 00:17:17,140 --> 00:17:18,280 Extract Max. 369 00:17:21,600 --> 00:17:24,420 And we get the maximum value, which is nine. 370 00:17:24,450 --> 00:17:28,770 Now if you call this again, we get seven, which is the second largest value. 371 00:17:28,770 --> 00:17:32,880 If we call this again we get six, which is the third largest value right now. 372 00:17:32,880 --> 00:17:36,480 If you do this again we should get four because that's the next largest value. 373 00:17:36,480 --> 00:17:37,680 Then we get three. 374 00:17:37,680 --> 00:17:38,910 Then again we get three. 375 00:17:38,910 --> 00:17:42,390 Right now we are just left with two and zero right. 376 00:17:42,390 --> 00:17:43,590 So we should get two. 377 00:17:43,710 --> 00:17:44,850 Then we should get zero. 378 00:17:44,850 --> 00:17:50,040 And then when we do this we get undefined because we have put this condition over here that we insert 379 00:17:50,040 --> 00:17:53,610 it back only if this dot heap dot length is greater than zero. 380 00:17:53,610 --> 00:17:53,820 Right. 381 00:17:53,820 --> 00:17:58,470 So if we are removing the last element like for example this case, then we don't put it back. 382 00:17:58,470 --> 00:18:00,390 We just return that and that's that. 383 00:18:00,390 --> 00:18:02,460 So the heap is empty at that point. 384 00:18:02,460 --> 00:18:04,350 So we are done with this function also. 385 00:18:04,350 --> 00:18:07,200 Now let's proceed and write the insert function. 386 00:18:08,050 --> 00:18:09,580 So let's write it over here. 387 00:18:09,610 --> 00:18:12,160 Now in this case we have to pass a value. 388 00:18:12,160 --> 00:18:14,200 So insert and then we pass a value. 389 00:18:14,830 --> 00:18:15,430 Oops. 390 00:18:16,280 --> 00:18:17,990 Insert value. 391 00:18:19,140 --> 00:18:19,890 All right. 392 00:18:23,630 --> 00:18:25,730 Now what we do is. 393 00:18:26,390 --> 00:18:29,270 We push this value to the array. 394 00:18:29,270 --> 00:18:29,450 Right. 395 00:18:29,450 --> 00:18:30,560 So it's just an array right. 396 00:18:30,560 --> 00:18:35,810 So we first we say this dot heap dot push and then we push this value right. 397 00:18:36,620 --> 00:18:39,410 And so it's inserted at the end of the array. 398 00:18:39,440 --> 00:18:42,350 Now we need to bubble it up to its correct position. 399 00:18:42,350 --> 00:18:43,970 So we need to write another function. 400 00:18:43,970 --> 00:18:45,620 So let's call it bubble up. 401 00:18:47,390 --> 00:18:47,840 Right. 402 00:18:47,840 --> 00:18:50,540 So this dot bubble up and that's it. 403 00:18:50,540 --> 00:18:53,660 So always we will bubble up at the the last element. 404 00:18:53,660 --> 00:18:55,310 So I'm not passing anything over here. 405 00:18:55,310 --> 00:18:58,700 And at the end of this we can just return the heap. 406 00:18:58,700 --> 00:18:59,870 So return this. 407 00:18:59,870 --> 00:19:00,410 All right. 408 00:19:00,410 --> 00:19:02,780 So now let's go ahead and write the bubble up function. 409 00:19:02,780 --> 00:19:04,040 So let's write it over here. 410 00:19:04,400 --> 00:19:05,300 Bubble up. 411 00:19:06,010 --> 00:19:07,870 It has not taken any parameter. 412 00:19:07,900 --> 00:19:09,970 Now let's do this. 413 00:19:09,970 --> 00:19:13,270 So the index of the last element let's find that out. 414 00:19:13,270 --> 00:19:14,260 That would be. 415 00:19:15,780 --> 00:19:17,940 This dot heap which is an array. 416 00:19:17,940 --> 00:19:19,770 So we can say dot length. 417 00:19:20,350 --> 00:19:21,160 Minus one. 418 00:19:21,160 --> 00:19:23,740 So that would be the last index right. 419 00:19:23,740 --> 00:19:24,640 It will be zero index. 420 00:19:24,640 --> 00:19:26,260 So that's why we are doing minus one. 421 00:19:26,260 --> 00:19:27,580 Now that's the index. 422 00:19:27,580 --> 00:19:28,420 And what's the value. 423 00:19:28,420 --> 00:19:29,470 Let's find the value. 424 00:19:29,470 --> 00:19:33,400 So const value is equal to this dot heap. 425 00:19:33,990 --> 00:19:37,860 And the index will be ID which we have just found out. 426 00:19:38,550 --> 00:19:38,880 All right. 427 00:19:38,880 --> 00:19:40,020 So this is the value. 428 00:19:40,050 --> 00:19:43,320 Now we will bubble up and we'll have a while loop. 429 00:19:43,320 --> 00:19:43,530 Right. 430 00:19:43,530 --> 00:19:47,520 So this will iterate till ID is greater than zero. 431 00:19:47,520 --> 00:19:49,770 So when it when we reach zero we can stop. 432 00:19:49,770 --> 00:19:50,190 All right. 433 00:19:50,190 --> 00:19:51,690 So we are starting at the end. 434 00:19:51,690 --> 00:19:54,660 And then we move till ID is greater than zero. 435 00:19:55,260 --> 00:19:55,800 All right. 436 00:19:55,800 --> 00:19:58,980 Now what we need to do is we need to find this parent. 437 00:19:58,980 --> 00:19:59,190 Right. 438 00:19:59,190 --> 00:20:00,900 So we have the ID over here. 439 00:20:00,900 --> 00:20:03,630 Now we know that we can find the parent by doing math. 440 00:20:03,630 --> 00:20:07,470 Dot floor the ID minus one by two. 441 00:20:07,470 --> 00:20:07,680 Right. 442 00:20:07,680 --> 00:20:08,850 So we have already seen that. 443 00:20:08,850 --> 00:20:10,170 So let's find its parent. 444 00:20:10,170 --> 00:20:14,640 So let's say let parent ID let's call it parent ID. 445 00:20:15,000 --> 00:20:17,610 That's equal to math dot floor. 446 00:20:18,610 --> 00:20:20,800 And then we have an ID right. 447 00:20:20,800 --> 00:20:23,590 So ID minus one by two. 448 00:20:24,750 --> 00:20:29,340 And I'm just adding a back bracket over here so that we have sufficient brackets. 449 00:20:29,340 --> 00:20:32,250 So this will give us the parent index right. 450 00:20:32,280 --> 00:20:34,830 Now let's find the value at the parent index. 451 00:20:35,490 --> 00:20:35,730 All right. 452 00:20:35,730 --> 00:20:39,450 So instead of let I can use const again we are not going to change it. 453 00:20:39,450 --> 00:20:41,040 So let's just write const. 454 00:20:41,040 --> 00:20:43,230 Now let's find the parent value. 455 00:20:43,230 --> 00:20:50,040 Parent value is equal to this dot heap at the index where the parent index right. 456 00:20:50,040 --> 00:20:51,630 So we have just found that index. 457 00:20:51,660 --> 00:20:52,020 All right. 458 00:20:52,020 --> 00:20:53,070 So that's the value. 459 00:20:53,070 --> 00:20:57,420 Now we need to compare this value and this value. 460 00:20:57,420 --> 00:20:58,890 So that's what we are going to do. 461 00:20:58,890 --> 00:21:05,820 And if the value is less than equal to the parent value then we can just break. 462 00:21:05,820 --> 00:21:06,060 Right. 463 00:21:06,060 --> 00:21:11,460 But if it's greater than the parent value then it's not following the max heap property. 464 00:21:11,460 --> 00:21:12,390 And we need to swap them. 465 00:21:12,390 --> 00:21:13,920 So that's what we are going to do. 466 00:21:13,920 --> 00:21:21,540 So if value less than equal to parent value in this case it's in the right position and we can just 467 00:21:21,540 --> 00:21:22,080 break. 468 00:21:22,080 --> 00:21:24,870 But if that is not the case then we need to swap right. 469 00:21:24,870 --> 00:21:31,080 So this dot heap we say parent index is equal to the value. 470 00:21:32,260 --> 00:21:36,070 And we say that this dot heap at IDF. 471 00:21:38,590 --> 00:21:40,540 Is equal to the parent value. 472 00:21:40,540 --> 00:21:42,010 So we have swapped these two. 473 00:21:42,820 --> 00:21:43,300 All right. 474 00:21:43,300 --> 00:21:46,990 And now we just need to set ID is equal to parent ID. 475 00:21:48,070 --> 00:21:51,820 And then again we have to keep doing this as long as we don't break out. 476 00:21:51,820 --> 00:21:52,000 Right. 477 00:21:52,000 --> 00:21:59,380 So if we will break out if the value is in its current position or if ID is not, if this condition 478 00:21:59,380 --> 00:22:02,890 over here, that is ID is greater than zero does not become true. 479 00:22:04,450 --> 00:22:08,140 Now that could happen if ID for example, is equal to zero, right. 480 00:22:08,140 --> 00:22:11,650 So let's say over here we got the parent ID as the root node. 481 00:22:11,650 --> 00:22:13,240 So ID is equal to zero. 482 00:22:13,240 --> 00:22:15,250 And then we don't need to again check it. 483 00:22:15,250 --> 00:22:15,460 Right. 484 00:22:15,460 --> 00:22:17,590 So at this point we just swapped right. 485 00:22:17,590 --> 00:22:19,750 We just swapped the value with the parent index. 486 00:22:19,750 --> 00:22:22,060 Now there's nothing more to go up right. 487 00:22:22,060 --> 00:22:23,650 So at that point we can stop. 488 00:22:23,650 --> 00:22:28,570 So either we break out or if ID is no longer greater than zero we come out of this loop. 489 00:22:28,570 --> 00:22:30,670 So we are done with the bubble up function. 490 00:22:30,670 --> 00:22:31,300 All right. 491 00:22:31,300 --> 00:22:33,760 So yes there's nothing to clean up over here. 492 00:22:33,760 --> 00:22:34,690 So this should work. 493 00:22:34,690 --> 00:22:37,120 Now let's try to insert a value over here. 494 00:22:37,660 --> 00:22:39,700 We will try to insert the value nine. 495 00:22:39,700 --> 00:22:40,180 All right. 496 00:22:40,180 --> 00:22:43,930 So let's just call this we have called our code. 497 00:22:43,930 --> 00:22:47,260 So we have the heap object over here. 498 00:22:48,040 --> 00:22:51,310 Now let's say heap dot insert. 499 00:22:52,200 --> 00:22:54,900 And let's say we give the value 20. 500 00:22:56,010 --> 00:23:01,380 Now 20 is the greatest among these elements, which over here, which we have over here. 501 00:23:01,380 --> 00:23:03,450 So we should see that it's at the root. 502 00:23:03,450 --> 00:23:03,660 Right. 503 00:23:03,660 --> 00:23:04,470 So let's see that. 504 00:23:04,470 --> 00:23:06,270 So we have 20 over here which is correct. 505 00:23:06,270 --> 00:23:06,450 Right. 506 00:23:06,450 --> 00:23:09,690 So this is the same example that we used in the explainer video. 507 00:23:09,690 --> 00:23:11,280 So it's easy to test it out. 508 00:23:11,280 --> 00:23:14,820 So our insert function is also working right now. 509 00:23:14,820 --> 00:23:19,140 Let's quickly do the last function which is the peak function which is pretty straightforward right. 510 00:23:19,140 --> 00:23:22,140 So we just need to return that particular value. 511 00:23:22,140 --> 00:23:24,750 So let's write the peak function. 512 00:23:25,650 --> 00:23:31,500 And this just has to return this dot heap at index zero. 513 00:23:33,050 --> 00:23:34,010 Which is the greatest value. 514 00:23:34,010 --> 00:23:34,190 Right. 515 00:23:34,190 --> 00:23:34,700 So that's it. 516 00:23:34,700 --> 00:23:34,910 Right. 517 00:23:34,910 --> 00:23:37,310 So the peak function is pretty easy. 518 00:23:37,340 --> 00:23:39,980 Now if we say let's again run this. 519 00:23:42,070 --> 00:23:43,510 So we have our heap. 520 00:23:43,510 --> 00:23:45,460 And if I say heap dot peak. 521 00:23:46,240 --> 00:23:47,410 It should give us. 522 00:23:48,650 --> 00:23:49,340 Nine. 523 00:23:49,340 --> 00:23:49,700 Right. 524 00:23:49,700 --> 00:23:51,590 Again, at this point, 20 is not there, right? 525 00:23:51,590 --> 00:23:52,970 Because I've run the code again. 526 00:23:52,970 --> 00:23:56,270 So the heap is starting at nine, which is the largest value. 527 00:23:56,270 --> 00:23:58,550 And when I peek I get back the value nine. 528 00:23:59,990 --> 00:24:00,320 All right. 529 00:24:00,320 --> 00:24:02,120 So we have successfully coded this solution. 530 00:24:02,120 --> 00:24:04,790 We have created our max binary heap. 531 00:24:04,790 --> 00:24:07,010 We have written the build heap function. 532 00:24:07,010 --> 00:24:10,490 And this uses the bubble down function as a helper function. 533 00:24:10,490 --> 00:24:12,770 And then we have returned the extract max function. 534 00:24:12,770 --> 00:24:16,340 This also uses the bubble down function as a helper function. 535 00:24:16,340 --> 00:24:21,500 Then we have written the insert function which uses the bubble up function and we have written peak. 536 00:24:21,500 --> 00:24:27,020 Now let's take a few sample inputs and relook at the code to thoroughly understand it. 537 00:24:27,020 --> 00:24:31,430 And we will also take a quick look at the complexity of the solution.