1 00:00:00,740 --> 00:00:06,440 In the previous scoring session, we developed and tested the DFS for finding all possible paths to 2 00:00:06,440 --> 00:00:08,240 the goal and the shortest path. 3 00:00:08,750 --> 00:00:13,760 Now DFS seems to work fine for the case where we had unweighted and smaller graphs. 4 00:00:14,270 --> 00:00:20,390 But if we had larger graphs like Google Maps, we will all for much intelligent approaches like distro 5 00:00:20,570 --> 00:00:21,380 and stuff. 6 00:00:21,920 --> 00:00:27,860 Now, both of these algorithms require implementation of a priority queue so that they always know which 7 00:00:27,860 --> 00:00:29,120 notes to visit next. 8 00:00:30,130 --> 00:00:35,970 So in this coding session will be developing a heap class for the implementation of the prior to you. 9 00:00:37,140 --> 00:00:37,650 For this. 10 00:00:37,650 --> 00:00:41,040 We go inside to board plane and cleared the place. 11 00:00:41,490 --> 00:00:46,740 So we start by creating a glass heap and then we define its first function. 12 00:00:46,950 --> 00:00:51,450 The very first function would be the initialization function, which takes in the input argument of 13 00:00:51,450 --> 00:00:51,810 self. 14 00:00:53,130 --> 00:00:56,640 Now inside this function will be defining the instance variable for this class. 15 00:00:56,760 --> 00:01:01,350 The very first instance variable would be an array that would be initialized to an empty list. 16 00:01:01,680 --> 00:01:04,920 Now this particular array would contain the whole of binary heap. 17 00:01:04,920 --> 00:01:11,010 Inside of it is structure would be a list of list, and each list inside the main list would represent 18 00:01:11,010 --> 00:01:17,430 the vertex or each of the binary, and each node would contain two components inside of it. 19 00:01:17,700 --> 00:01:22,020 One is the vortex that represents that node, and other is spectrum distance. 20 00:01:22,620 --> 00:01:27,930 The next instance variable would be the size of the binary heap and this would be initialized to zero. 21 00:01:28,110 --> 00:01:32,790 Now this particular variable will help us keep track of the ever changing size of the priority queue. 22 00:01:33,840 --> 00:01:38,670 The next and the final instance variable would be the position of vertices and this would be initialized 23 00:01:38,670 --> 00:01:39,170 and empty. 24 00:01:39,180 --> 00:01:45,680 This to this particular variable will help us keep track of the position of each vertex inside the binary 25 00:01:45,680 --> 00:01:45,900 heap. 26 00:01:46,620 --> 00:01:53,370 Now we can define the first function that will help us create a new node for our binary heap so it will 27 00:01:53,370 --> 00:01:54,930 be named as Neumann heap. 28 00:01:54,930 --> 00:02:00,870 Note This takes in the input argument of self and the other two arguments are simply the components 29 00:02:00,870 --> 00:02:04,740 of a note of a binary that is the vertex and its distance. 30 00:02:05,040 --> 00:02:12,900 And if the user provides these values, we simply return a list that is composed of vertex and its distance. 31 00:02:14,370 --> 00:02:19,410 So once we have defined this function, we define the third function that we performed. 32 00:02:19,410 --> 00:02:24,660 Actual task of maintaining the heap property by performing mean Hebrew before, so it would be named 33 00:02:24,660 --> 00:02:26,550 as main heap for it. 34 00:02:27,480 --> 00:02:29,550 And this takes in the input argument of self. 35 00:02:29,850 --> 00:02:34,890 And the next argument is basically the index of the node from which you want to start your file from. 36 00:02:35,520 --> 00:02:41,760 So we name it as node index and this starts with checking whether the heap property is maintained for 37 00:02:41,760 --> 00:02:44,010 the particular node that we are right now on. 38 00:02:44,460 --> 00:02:51,090 So the heap property says that whichever current node that we are on it should be have value less than 39 00:02:51,090 --> 00:02:53,010 is side nodes if it is a heap. 40 00:02:53,460 --> 00:03:01,870 So we see that the current node is the smallest and then we extract its child node to compare it with 41 00:03:01,870 --> 00:03:07,260 the current node, which I node can be accessed by simply multiplying the node index with two and then 42 00:03:07,260 --> 00:03:13,590 adding one, and the right charge can be accessed by multiplying the node index with you, but this 43 00:03:13,590 --> 00:03:19,230 time adding do once you have the left and the right side node index, we can now do the comparison to 44 00:03:19,230 --> 00:03:23,760 see if the left node is has indeed value less than the smallest node. 45 00:03:23,760 --> 00:03:29,190 Note So if it is indeed less than the smallest known node, then this means that the heap properties 46 00:03:29,190 --> 00:03:29,640 disturb. 47 00:03:29,880 --> 00:03:35,970 We need to swap the left node with the smallest and this should also satisfy the property that the left 48 00:03:36,090 --> 00:03:37,980 is indeed part of the binary heap. 49 00:03:38,220 --> 00:03:42,720 And that would be if it has size less than the standard size or in size. 50 00:03:43,320 --> 00:03:48,990 So if this condition becomes true, we update the smallest to be the left and the same process decrease 51 00:03:48,990 --> 00:03:49,500 for the right. 52 00:03:49,500 --> 00:03:55,200 Note Because if this condition becomes true, where the right knows distance is less than the smallest 53 00:03:55,200 --> 00:03:58,920 known distance, then we need to say that the smallest is now right. 54 00:03:59,820 --> 00:04:05,460 If either of these condition becomes true, then the smallest known index would not be equal to the 55 00:04:05,460 --> 00:04:08,010 node index that we were provided with earlier. 56 00:04:08,490 --> 00:04:17,550 So we check that if the smallest is not equal to the node index, then that means it has been modified. 57 00:04:17,820 --> 00:04:23,430 And if it has been modified, then this means that the heap property was just too and we need to keep 58 00:04:23,430 --> 00:04:28,860 ify it and the heap five boxes that we start by performing three steps simultaneously. 59 00:04:29,130 --> 00:04:33,540 The fourth step is that we need to update the position of the vertex from which we want to swap. 60 00:04:33,960 --> 00:04:40,770 So the smallest known index is not the node index that we were provided with, but rather one of its 61 00:04:40,770 --> 00:04:43,080 charged node is smaller than its parent index. 62 00:04:43,410 --> 00:04:45,030 So we need to update the provision. 63 00:04:46,010 --> 00:04:47,810 But writing said the position of vertices. 64 00:04:48,620 --> 00:04:52,190 We provided the vertex from which position we want to set. 65 00:04:52,490 --> 00:04:53,780 So we tried several array. 66 00:04:54,470 --> 00:05:00,050 We provided the node index, that is the index or node that we want to strip or this vertex that we 67 00:05:00,050 --> 00:05:00,620 want to square. 68 00:05:00,950 --> 00:05:06,680 And then we access vertex where accessing the zeroth value of the list, that is the vertex. 69 00:05:07,820 --> 00:05:11,870 And then we provide this the smallest node index. 70 00:05:12,350 --> 00:05:15,950 So the node index will the decision has been modified to smallest known index. 71 00:05:16,550 --> 00:05:17,480 And we do the same 72 00:05:20,420 --> 00:05:21,080 for the position. 73 00:05:21,110 --> 00:05:23,000 Words is 7.3. 74 00:05:24,740 --> 00:05:32,240 This time we provided the smallest index and accessed its world expert rating zero and then update this 75 00:05:32,540 --> 00:05:33,590 to the node index. 76 00:05:33,920 --> 00:05:39,710 So both of these positions have been swept and this means we need to now perform the sweeping of the 77 00:05:39,710 --> 00:05:40,520 nodes itself. 78 00:05:40,820 --> 00:05:45,620 And that can be done by creating a new function that perform the swapping of the nodes inside the self 79 00:05:45,620 --> 00:05:46,070 portrait. 80 00:05:46,640 --> 00:05:49,310 So we like to serve definition swept nodes. 81 00:05:49,610 --> 00:05:55,070 This takes in the input argument of self and the two nodes index 31% and B. 82 00:05:57,200 --> 00:06:03,530 Now this function will simply run in such a way that we create a temp, we will restore the node or 83 00:06:03,530 --> 00:06:04,730 in or inside of it. 84 00:06:05,870 --> 00:06:08,060 And then we simply update. 85 00:06:11,660 --> 00:06:13,200 A node with a value. 86 00:06:14,370 --> 00:06:15,090 Of the North. 87 00:06:16,890 --> 00:06:23,460 And once we have updated in or we can now update the value of the vineyard with a temporal note. 88 00:06:24,750 --> 00:06:30,090 So this has done the swiping inside the cell, and now we can simply call this function inside the main 89 00:06:30,120 --> 00:06:36,990 Hebrew part by writing self swept nodes, providing the first node index, that is the node index. 90 00:06:38,820 --> 00:06:42,540 And then for the second index that I want to spread basically is the smallest. 91 00:06:43,170 --> 00:06:49,150 Once we have done this, all we need to do is to recursively call this function by writing some document 92 00:06:49,150 --> 00:06:52,530 here before it, and for the note index will be providing the smallest. 93 00:06:53,070 --> 00:06:59,790 So whichever node that has been swept, we need to restart this function from that particular note to 94 00:06:59,790 --> 00:07:03,660 continue seeing the key properties maintain till the very end. 95 00:07:03,990 --> 00:07:08,910 If the heap property is maintained, the function stops right here, otherwise it will continue until 96 00:07:08,910 --> 00:07:11,520 the key property is maintained throughout the whole primary heap. 97 00:07:12,330 --> 00:07:13,110 So this completes. 98 00:07:14,720 --> 00:07:16,040 The main function. 99 00:07:17,600 --> 00:07:22,400 After we have defined the mean hip fire function, it's now time to define the next function for our 100 00:07:22,400 --> 00:07:23,090 heap class. 101 00:07:25,690 --> 00:07:27,730 That would be extract main. 102 00:07:28,180 --> 00:07:30,280 It sticks an input argument offset. 103 00:07:32,050 --> 00:07:35,320 And this function is used to retrieve the node with the minimum value. 104 00:07:35,560 --> 00:07:40,330 And because this binary is a mean heap, it's root node is a node with a minimum value. 105 00:07:40,480 --> 00:07:41,800 So we will extract that. 106 00:07:42,280 --> 00:07:48,160 We start off by checking for the boundary condition, which says that if standard size equal equal to 107 00:07:48,160 --> 00:07:50,350 zero, then the binary heap is empty. 108 00:07:50,350 --> 00:07:51,520 There's nothing to extract. 109 00:07:51,850 --> 00:07:53,440 So data on empty. 110 00:07:54,160 --> 00:08:01,930 Then we move further to extract the root node from our array that exists in its zeroth index. 111 00:08:02,440 --> 00:08:07,840 Now, because we have replaced or extracted the root node from our binding heap, we have the complete 112 00:08:07,840 --> 00:08:08,320 property. 113 00:08:08,950 --> 00:08:13,720 So to maintain is complete property something or some other node needs to replace that note. 114 00:08:14,320 --> 00:08:20,020 So what we need to do is simply extract the last node from our binary heap and that is located as the 115 00:08:20,020 --> 00:08:24,010 support array at a certain size minus one. 116 00:08:24,790 --> 00:08:30,760 Because we've extracted the last note, we can now replace the root node location that is the zero index 117 00:08:30,760 --> 00:08:33,370 location of our array with the last node. 118 00:08:33,890 --> 00:08:39,520 Now because we have done a little bit of stripping, we need to update this word, this location inside 119 00:08:39,520 --> 00:08:41,230 the position of vertex variable. 120 00:08:41,680 --> 00:08:49,510 So we access the position of vertex variable or list and then we update the location of our root node 121 00:08:50,290 --> 00:08:59,740 root vertex accessing root zero with seven dot size minus one because the root node location is now 122 00:08:59,830 --> 00:09:02,110 the last index location of the array. 123 00:09:02,980 --> 00:09:09,340 And we do the same for the position of vertex for the last node vertex by accessing its zeroth index 124 00:09:10,000 --> 00:09:12,010 and updating it to zero. 125 00:09:12,400 --> 00:09:15,520 So the last note, this is right now at the zeroth index. 126 00:09:15,820 --> 00:09:22,690 Right now, once we're done there, we update the size of our binary heap that has declined by one. 127 00:09:23,020 --> 00:09:29,140 And the reason it has decreased because we have extracted the root note and now we can simply call the 128 00:09:29,230 --> 00:09:33,940 Sabatini heap five function to tell it that I want to maintain the heap property. 129 00:09:34,120 --> 00:09:35,550 So this makes me very functional. 130 00:09:35,560 --> 00:09:38,200 Do exactly that and it needs to start from the node. 131 00:09:38,350 --> 00:09:41,890 So I pass in zero and then we simply return the root. 132 00:09:43,380 --> 00:09:45,150 So this is the output of this function. 133 00:09:45,260 --> 00:09:52,770 The root note Now after we have defined extract main function, we proceed on to defining the lost important 134 00:09:52,770 --> 00:09:54,360 function of this heap class. 135 00:09:54,810 --> 00:09:56,580 That is the decreased key function. 136 00:09:57,810 --> 00:10:00,800 Decreased key function fixed in three arguments. 137 00:10:00,810 --> 00:10:01,920 The first is the self. 138 00:10:02,910 --> 00:10:04,050 Second is the vertex. 139 00:10:04,830 --> 00:10:08,550 And third and the third is the distance. 140 00:10:09,060 --> 00:10:15,510 Now, what this function is used for is to update the new shortest distance with a new found shortest 141 00:10:15,510 --> 00:10:17,310 distance of a particular vertex. 142 00:10:17,490 --> 00:10:22,560 And this is why the two arguments that it takes is the vertex that we want to update the known distance 143 00:10:22,560 --> 00:10:23,580 to a new, shorter distance. 144 00:10:23,790 --> 00:10:27,480 And the distance represents the new shaka's distance or newfound shorter distance. 145 00:10:27,840 --> 00:10:32,880 So we want to decrease a particular note key, because we have found a new shortest distance to that 146 00:10:32,880 --> 00:10:33,480 particular note. 147 00:10:33,990 --> 00:10:40,170 So the way this function works is that because we have the vertex at our disposal, it was the exact 148 00:10:40,170 --> 00:10:41,430 index of this vertex. 149 00:10:41,850 --> 00:10:50,260 So we extract the index of vertex and that can be accessed from the position of vertices and passing 150 00:10:50,260 --> 00:10:53,650 in the vertex from which we want the index off. 151 00:10:54,150 --> 00:10:55,650 Plus, we have the index of vertex. 152 00:10:55,860 --> 00:10:56,850 We can now update. 153 00:10:58,430 --> 00:11:06,410 It's distance on the vertex distance by accessing saved or passing in the index of vertex and then accessing 154 00:11:06,590 --> 00:11:08,120 its one index. 155 00:11:08,360 --> 00:11:12,140 And this will provide me the value of the distance, a known distance. 156 00:11:12,410 --> 00:11:15,260 We now update this with a new found shortest distance. 157 00:11:15,920 --> 00:11:22,430 Now, because we have updated a nodes value, it might be smaller than its parent, so we need to check 158 00:11:22,430 --> 00:11:23,210 exactly that. 159 00:11:23,600 --> 00:11:27,290 If it is more than a sprint, then this has to stop the he property. 160 00:11:27,470 --> 00:11:29,300 So we need to maintain the he property. 161 00:11:29,480 --> 00:11:31,010 So we perform a few operations. 162 00:11:31,430 --> 00:11:38,120 We start out by checking, so we start off by checking if the grant node, which you are right now on, 163 00:11:38,570 --> 00:11:43,040 has the distance value less than a sprint, then the heap properties disturb. 164 00:11:43,250 --> 00:11:49,250 And we also need to check whether the current node has index greater than zero but is part of the binary 165 00:11:49,250 --> 00:11:49,460 heap. 166 00:11:49,700 --> 00:11:54,380 So if this condition becomes true, we need to perform the swapping of the current for this pattern. 167 00:11:54,680 --> 00:11:58,130 We need to update its equation and then we need to be five. 168 00:11:58,550 --> 00:12:03,680 So we start all by updating the provision of the vertices of our current node and the pain and note. 169 00:12:04,160 --> 00:12:06,680 So this is done exactly like we did before. 170 00:12:06,950 --> 00:12:08,810 We re passing for the position of vertex. 171 00:12:09,080 --> 00:12:12,800 We pass in the new position for our current note, our parent note. 172 00:12:13,520 --> 00:12:16,910 Then we simply swept the card node with a parent or by calling swept nodes. 173 00:12:17,180 --> 00:12:22,250 And then finally we update or navigate from our current law for the parent or check. 174 00:12:22,640 --> 00:12:29,660 But if the property is maintained did so skipping or navigating to our from current or to the pinnacle 175 00:12:29,810 --> 00:12:30,710 happens like this. 176 00:12:31,190 --> 00:12:36,880 Now once we have done this, this process repeats until all the heap property or the complete bind to 177 00:12:36,890 --> 00:12:38,570 heap property has been retained. 178 00:12:39,320 --> 00:12:46,520 So this completes the major functions of our heap, plus the last function that is important for the 179 00:12:46,520 --> 00:12:48,080 last function that is left for the heap. 180 00:12:48,080 --> 00:12:53,900 Last to write is basically to check if the if any vertex is part of the main heap. 181 00:12:54,260 --> 00:13:00,290 So if the vertex is not bothered with heap, that can be checked if the position of vertex is less than 182 00:13:00,350 --> 00:13:01,220 standard size. 183 00:13:01,520 --> 00:13:06,410 So if it is greater than several size, ignore part of the heap, otherwise it is less than standard 184 00:13:06,410 --> 00:13:06,770 size. 185 00:13:06,980 --> 00:13:13,430 That means that it was, it was and it is are the mean because every other support this is that has 186 00:13:13,430 --> 00:13:19,100 been removed from our main heap or our priority queue would be placed at the end of the array and this 187 00:13:19,100 --> 00:13:21,830 is why it will be greater than the standard size. 188 00:13:22,190 --> 00:13:25,520 So this is how we check if a vertex is part of the main heap or not. 189 00:13:25,970 --> 00:13:32,000 So this completes the heap, class or definition of our heap class that we would be using for maintaining 190 00:13:32,000 --> 00:13:37,210 or implementing a priority queue for the shortest path defining algorithm like disaster and stuck. 191 00:13:37,820 --> 00:13:39,680 Let's see them in action till then. 192 00:13:40,100 --> 00:13:40,460 Thank you. 193 00:13:40,460 --> 00:13:40,880 And by.