In the previous video we discussed distro and how it can be used to find the shortcuts.
But the functionality of the algorithm relied heavily on the implementation of a priority queue so that
we all is the node with the least cost.
So this begs the question how exactly are we going to implement a bride to queue?
The most suitable way, especially for design, is that is to implement it using heaps.
So what are he and why did the first choice implementation of a prior.
Well he's a specialized breeder structures that's satisfied that he property now he property is where
the child node is less than or greater than spirit for a mean he this amounts to the GI node being greater
than or equal to is greater.
And this is opposite for Maxim.
If we look on the right hand side, we have an example of a maxim where child is less than or equal
to is better.
This means that the top node or the root node will have the maximum value of the whole heap.
This property is particularly useful for desktop.
If all nodes represent the respective traversal goals, then the root node will have the least value
and the highest priority customer is the first for the types of heap.
There are many types that can be used to implement a priority group, but we'll be focusing on binaries
for now.
What are my critiques widely heaps agree that have at max two children so a binary tree and to satisfy
the following two properties.
Number one, they are complete, which means that all rules except possibly the last point is filled.
For the last.
All those are as leftmost as possible.
So by this we can even see right here we have three levels in this binary.
And for the first two row they are completely filled.
But the last row is not filled, but all nodes are leftmost as possible.
So this is a complete grid and there is a complete binary retreat in the second property because if,
say, he is satisfied that he property, which means that it can be either a mini heap or a max heap.
Now because of the complete poverty binary he is liberty was entered into an array of so this complete
property becomes very useful in the presentation of a binary hit.
And following are the rules which from which we can represent a binary heap into an array.
The first rule is that the first element of the array is the root note of the binary heap.
The second rule is that if nought is an index sign, then its left child would index a two plus one
and write.
I would have index II plus two and its parent will be at and minus one divided by two flawed.
Let's see how this pans out in this example.
So if we take the root node that is an index zero, the left child would be at two plus one that is
two and two zero plus one that becomes one.
And that is the correct answer for the left chart.
Right here.
And for the right time, we take the same formula for the right foot potato that is doing the zero plus
two that becomes two.
So that is the correct answer for the right.
And if you want to find the pattern of the right chart, that is an index, too.
So we can do that by using the rerun formula that is flawed.
And minus one that is two minus one.
Divide by two, that becomes one and a half point five and floating equals to approximately zero.
So that is the correct answer for the parent.
So this is how we represent a binary heap into an array.
There is no risk because some of the important functions all bind.
The first and the most important function is known as extract.
Now this function returns the root element of the binding domain.
This means the element with the least value.
Now just getting to the top alone happens in constant time.
But because we're in a priority group, we need we will need to remove the root node.
So this disturbs the heap property.
So it needs to be here before.
So a total time complexity now becomes or log in.
And following are the three steps necessary to perform the external function.
Number one.
Remove the root node and keep it separate.
Number two, move the last note.
To the top.
And number three.
He'd be fine now because we have moved a lot more to stop this disturbed he property.
So now we will need to keep it part of the heap.
Five Is that because we have moved the last note to top it needs to be compared with the side note and
gets trapped with the least of a side note.
So too goes to a top and six goes to the bottom.
Now same step repeats for the remaining notes.
For example, six gets replaced with four, four goes to the top and six goes to the bottom.
Here the heap five stops and the effect on function finishes.
Now, the second most important function of this job is known as decrease.
Now, this function happens when we are found shorter role.
So we decrease a squeeze on node value.
So just updating nodes value happens in constant time, but because this might disturb the heap property.
So this needs to be typified.
So the total time complexity now becomes of log in.
Are two steps necessary for decrease.
Number one is updating the nose value and number to keep five.
For example, if you look right here, if we have a node that has a value of five and gets decreased
to one.
So we will now need to compare it for disappearance because one is less than two.
So it needs to be swept.
And this step repeats for the remaining top notes because one and one of same value.
So stripping these to be stopped.
So five stops right here for a decrease.
The function finishes.
Now there are definite few advantage of using heaps as a priority queue.
The first of them is the faster insertion and deletion, which is all again as compared to orphan list
implementation.
And number two, the key property which gives us the smallest value note always in top to task, providing
us easier access.