In the previous scoring session, we developed and tested the DFS for finding all possible paths to
the goal and the shortest path.
Now DFS seems to work fine for the case where we had unweighted and smaller graphs.
But if we had larger graphs like Google Maps, we will all for much intelligent approaches like distro
and stuff.
Now, both of these algorithms require implementation of a priority queue so that they always know which
notes to visit next.
So in this coding session will be developing a heap class for the implementation of the prior to you.
For this.
We go inside to board plane and cleared the place.
So we start by creating a glass heap and then we define its first function.
The very first function would be the initialization function, which takes in the input argument of
self.
Now inside this function will be defining the instance variable for this class.
The very first instance variable would be an array that would be initialized to an empty list.
Now this particular array would contain the whole of binary heap.
Inside of it is structure would be a list of list, and each list inside the main list would represent
the vertex or each of the binary, and each node would contain two components inside of it.
One is the vortex that represents that node, and other is spectrum distance.
The next instance variable would be the size of the binary heap and this would be initialized to zero.
Now this particular variable will help us keep track of the ever changing size of the priority queue.
The next and the final instance variable would be the position of vertices and this would be initialized
and empty.
This to this particular variable will help us keep track of the position of each vertex inside the binary
heap.
Now we can define the first function that will help us create a new node for our binary heap so it will
be named as Neumann heap.
Note This takes in the input argument of self and the other two arguments are simply the components
of a note of a binary that is the vertex and its distance.
And if the user provides these values, we simply return a list that is composed of vertex and its distance.
So once we have defined this function, we define the third function that we performed.
Actual task of maintaining the heap property by performing mean Hebrew before, so it would be named
as main heap for it.
And this takes in the input argument of self.
And the next argument is basically the index of the node from which you want to start your file from.
So we name it as node index and this starts with checking whether the heap property is maintained for
the particular node that we are right now on.
So the heap property says that whichever current node that we are on it should be have value less than
is side nodes if it is a heap.
So we see that the current node is the smallest and then we extract its child node to compare it with
the current node, which I node can be accessed by simply multiplying the node index with two and then
adding one, and the right charge can be accessed by multiplying the node index with you, but this
time adding do once you have the left and the right side node index, we can now do the comparison to
see if the left node is has indeed value less than the smallest node.
Note So if it is indeed less than the smallest known node, then this means that the heap properties
disturb.
We need to swap the left node with the smallest and this should also satisfy the property that the left
is indeed part of the binary heap.
And that would be if it has size less than the standard size or in size.
So if this condition becomes true, we update the smallest to be the left and the same process decrease
for the right.
Note Because if this condition becomes true, where the right knows distance is less than the smallest
known distance, then we need to say that the smallest is now right.
If either of these condition becomes true, then the smallest known index would not be equal to the
node index that we were provided with earlier.
So we check that if the smallest is not equal to the node index, then that means it has been modified.
And if it has been modified, then this means that the heap property was just too and we need to keep
ify it and the heap five boxes that we start by performing three steps simultaneously.
The fourth step is that we need to update the position of the vertex from which we want to swap.
So the smallest known index is not the node index that we were provided with, but rather one of its
charged node is smaller than its parent index.
So we need to update the provision.
But writing said the position of vertices.
We provided the vertex from which position we want to set.
So we tried several array.
We provided the node index, that is the index or node that we want to strip or this vertex that we
want to square.
And then we access vertex where accessing the zeroth value of the list, that is the vertex.
And then we provide this the smallest node index.
So the node index will the decision has been modified to smallest known index.
And we do the same
for the position.
Words is 7.3.
This time we provided the smallest index and accessed its world expert rating zero and then update this
to the node index.
So both of these positions have been swept and this means we need to now perform the sweeping of the
nodes itself.
And that can be done by creating a new function that perform the swapping of the nodes inside the self
portrait.
So we like to serve definition swept nodes.
This takes in the input argument of self and the two nodes index 31% and B.
Now this function will simply run in such a way that we create a temp, we will restore the node or
in or inside of it.
And then we simply update.
A node with a value.
Of the North.
And once we have updated in or we can now update the value of the vineyard with a temporal note.
So this has done the swiping inside the cell, and now we can simply call this function inside the main
Hebrew part by writing self swept nodes, providing the first node index, that is the node index.
And then for the second index that I want to spread basically is the smallest.
Once we have done this, all we need to do is to recursively call this function by writing some document
here before it, and for the note index will be providing the smallest.
So whichever node that has been swept, we need to restart this function from that particular note to
continue seeing the key properties maintain till the very end.
If the heap property is maintained, the function stops right here, otherwise it will continue until
the key property is maintained throughout the whole primary heap.
So this completes.
The main function.
After we have defined the mean hip fire function, it's now time to define the next function for our
heap class.
That would be extract main.
It sticks an input argument offset.
And this function is used to retrieve the node with the minimum value.
And because this binary is a mean heap, it's root node is a node with a minimum value.
So we will extract that.
We start off by checking for the boundary condition, which says that if standard size equal equal to
zero, then the binary heap is empty.
There's nothing to extract.
So data on empty.
Then we move further to extract the root node from our array that exists in its zeroth index.
Now, because we have replaced or extracted the root node from our binding heap, we have the complete
property.
So to maintain is complete property something or some other node needs to replace that note.
So what we need to do is simply extract the last node from our binary heap and that is located as the
support array at a certain size minus one.
Because we've extracted the last note, we can now replace the root node location that is the zero index
location of our array with the last node.
Now because we have done a little bit of stripping, we need to update this word, this location inside
the position of vertex variable.
So we access the position of vertex variable or list and then we update the location of our root node
root vertex accessing root zero with seven dot size minus one because the root node location is now
the last index location of the array.
And we do the same for the position of vertex for the last node vertex by accessing its zeroth index
and updating it to zero.
So the last note, this is right now at the zeroth index.
Right now, once we're done there, we update the size of our binary heap that has declined by one.
And the reason it has decreased because we have extracted the root note and now we can simply call the
Sabatini heap five function to tell it that I want to maintain the heap property.
So this makes me very functional.
Do exactly that and it needs to start from the node.
So I pass in zero and then we simply return the root.
So this is the output of this function.
The root note Now after we have defined extract main function, we proceed on to defining the lost important
function of this heap class.
That is the decreased key function.
Decreased key function fixed in three arguments.
The first is the self.
Second is the vertex.
And third and the third is the distance.
Now, what this function is used for is to update the new shortest distance with a new found shortest
distance of a particular vertex.
And this is why the two arguments that it takes is the vertex that we want to update the known distance
to a new, shorter distance.
And the distance represents the new shaka's distance or newfound shorter distance.
So we want to decrease a particular note key, because we have found a new shortest distance to that
particular note.
So the way this function works is that because we have the vertex at our disposal, it was the exact
index of this vertex.
So we extract the index of vertex and that can be accessed from the position of vertices and passing
in the vertex from which we want the index off.
Plus, we have the index of vertex.
We can now update.
It's distance on the vertex distance by accessing saved or passing in the index of vertex and then accessing
its one index.
And this will provide me the value of the distance, a known distance.
We now update this with a new found shortest distance.
Now, because we have updated a nodes value, it might be smaller than its parent, so we need to check
exactly that.
If it is more than a sprint, then this has to stop the he property.
So we need to maintain the he property.
So we perform a few operations.
We start out by checking, so we start off by checking if the grant node, which you are right now on,
has the distance value less than a sprint, then the heap properties disturb.
And we also need to check whether the current node has index greater than zero but is part of the binary
heap.
So if this condition becomes true, we need to perform the swapping of the current for this pattern.
We need to update its equation and then we need to be five.
So we start all by updating the provision of the vertices of our current node and the pain and note.
So this is done exactly like we did before.
We re passing for the position of vertex.
We pass in the new position for our current note, our parent note.
Then we simply swept the card node with a parent or by calling swept nodes.
And then finally we update or navigate from our current law for the parent or check.
But if the property is maintained did so skipping or navigating to our from current or to the pinnacle
happens like this.
Now once we have done this, this process repeats until all the heap property or the complete bind to
heap property has been retained.
So this completes the major functions of our heap, plus the last function that is important for the
last function that is left for the heap.
Last to write is basically to check if the if any vertex is part of the main heap.
So if the vertex is not bothered with heap, that can be checked if the position of vertex is less than
standard size.
So if it is greater than several size, ignore part of the heap, otherwise it is less than standard
size.
That means that it was, it was and it is are the mean because every other support this is that has
been removed from our main heap or our priority queue would be placed at the end of the array and this
is why it will be greater than the standard size.
So this is how we check if a vertex is part of the main heap or not.
So this completes the heap, class or definition of our heap class that we would be using for maintaining
or implementing a priority queue for the shortest path defining algorithm like disaster and stuck.
Let's see them in action till then.
Thank you.
And by.