Welcome back.
Let's now code the priority queue which we discussed in the previous video.
Now as we discussed we will be using a binary heap to implement this.
And let's make the priority queue a minimum by binary heap.
Now over here we will need a node class because every node will have a value as well as a priority.
And then based on the priority, we will take the value with the minimum priority to the front or to
the beginning of the array, because we will treat that priority one is the highest priority.
All right.
So we say class node.
And then over here we will need a constructor.
So let's write that.
And over here we will pass the value and priority.
And inside this we will say this dot value is equal to the value.
And this dot priority is equal to the priority.
All right.
Now let's go ahead and code the priority class priority queue class.
So we have priority.
You.
Let's call it Priority queue.
And over here also we need a constructor.
So let's write that.
And inside the constructor we don't pass anything.
And we just say this dot data is an empty array.
All right.
Now over here we will write the instance methods to insert a value to the priority queue and to take
the element with the highest priority out.
So the highest priority over here means the minimum priority.
That's why we are implementing a minimum binary heap over here.
So let's call the methods in queue.
And Dick.
So let's just have placeholders.
So this is NQ.
This is DQ.
Now for the NQ function, we will need to pass a value and a priority.
All right.
So let's go ahead and finish the NQ function.
So once we call this and a value and a priority is passed we will need to create a new node.
So let's say let node is equal to new.
And then we have the node class right.
So we say node and we say value and priority.
We pass these two.
So we create a new node and then we just push this to the array over here.
Right.
We are storing the priority queue as an array.
So we just push it over here.
And this will be an array of nodes.
So we say this dot data dot push and we say node.
All right.
So we have pushed it.
Now we need to place this node in its correct position based on the priority.
Right.
So the item with the minimum priority should be at the beginning.
So it's just like a minimum binary heap right.
So for this we will need to call the bubble up function.
So let's say this dot bubble up and we need to write this function now.
All right.
So let's go ahead and write the function.
And as far as the enqueue is concerned that's it.
Right.
So we have inserted it and we could return it right.
So let's say we say return this.
So at the end we return the priority queue.
So that's it.
Now let's go ahead and write the bubble up function.
All right.
So this will always deal with the element with the last element.
Right.
Because we are pushing it to the array.
Right.
So we can say that that particular index where we have just pushed that would be the length of the array
minus one.
Right.
So let's say let id x is equal to this dot data dot length minus one.
All right.
And the value let's also take the value.
So let's say const element.
Is equal to this dot data at ID.
So this is the value or this is the node which we just now pushed into the array.
Right.
All right.
Now let's proceed.
Now we will have a while loop.
It's pretty similar to the binary heap question which we did.
So while ID greater than zero we'll just loop through and we will break out if the priority is greater
than the parent's priority.
So if the node's priority is greater than its parent's priority right.
So then we can break out because again remember over here we are treating priority one as the highest
priority.
And we are implementing a minimum binary heap.
All right.
So let's now find the parent ID.
So let parent id.
Is equal to math dot floor.
And we just need to do ID minus one divided by two.
We have discussed this.
Right.
So it's it's similar to what we've discussed in the binary heap section.
So we get the parent index.
Now we can just find the parent value.
So let parent value is equal to this dot data.
At parent index right.
So parent ID so we get the value.
All right.
Now again remember this is the node.
So let's just say parent is not just the value.
That's the node actually.
All right.
Now what we need to check is we need to check the priority of this node and the priority of this node.
So we need to compare these two priorities.
So let's write that.
So if the element's priority element dot priority is greater than equal to the parent's priority.
If this is the case, then it's the node is in the correct, the element node is in the correct position
and we can just break out.
Right.
But if this is not the case, that is if the element priority is less than the parent's priority then
we need to swap these two.
So we say this dot data at id.
That should have the parent node.
Right.
And this dot data at parent index this should have the element node.
So these are elements nodes right.
So we have already stored these two.
So we can just use that.
So we have element over here.
And we have also defined parent over here.
Right.
So we can just use them over here and here.
And we swap the values.
And that's it.
And we just now have to change ID to parent ID right.
That's it.
Now it will keep looping right.
It will keep looping.
So if this is the case, if the element gets to the position where the priority of the parent is less
than the element's priority, then we just break out.
Otherwise we keep looping.
And if it becomes zero then there is no parent.
So we loop out.
So this will keep on happening till ID as long as ID is greater than zero.
Now once this is the once we are out of this we are done.
So we should have it now.
Ready.
Now what we will do over here is let's go ahead and write the dequeue function also, because after
that it's very easy to test.
Right.
So whenever we dequeue we should get the element with the highest with the lowest priority because priority
one is the highest priority.
So the element with the lowest numerical priority let me just call it as like that, because actually
we are treating it as the highest priority.
If you were to think of, um, any real life scenario, if a job has a priority one and another job
has a priority two, now let's say we define that priority one is more important than priority two.
So we take that out first, right.
So we say on a functional basis that it is of higher priority.
But numerically one is lower than two.
All right.
So let's go ahead and write our dequeue function.
And then we'll test this out together.
Now for the dequeue function.
What is it that we need to do?
We need to just find give the minimum value back right.
So let's have a variable const min.
Numerically it's minimum right.
So this is this dot data.
And that would be at index zero because that's how we are storing it over here.
Right when we are enqueuing it and bubbling up we are ensuring this.
Right.
All right.
So we just take the numerically minimum value, the item with minimum priority numerically out.
And then we replace it with the last item.
So let's say const last is equal to this dot data.
And we just pop right.
We just pop the last node from this array.
And then if this is not the last element right.
So again we have discussed this in the binary heap section as well.
But let's quickly discuss it.
Let's say there is a node over here and there's just one node left in the priority queue.
Let's say that's like job one.
That's the value.
And let's say it has a priority of two and there's nothing else over here.
Now what are we doing over here.
Because this is this is the zeroth node right.
So we are going to allocate this to min.
And last is also going to be this one.
So we are popping it out and we don't need to insert it back.
Right.
So we are done.
So if there is just one node then we are done.
And the priority queue after taking out the element over here will be empty.
But if that is not the case, then we take out the last element, put it at the beginning, and then
we bubble down to its correct position.
So that's what we are trying to do.
So let's say if uh this dot data dot length.
Greater than zero right after popping out, right after popping the last element.
If there is still something over there, then we say this dot data at zero.
Is equal to the last element.
See this node over here.
Right last.
So this is the last node.
So we put that first and then we just call bubble down.
So this dot.
Bubble down, right?
So that it gets to its correct position.
And finally we will just return this node.
So return min.
And we are done with the DQ function.
We just need to write the bubble down function.
So let's go ahead and do that as well now.
So bubble down.
All right.
Now, what is it that we have to do over here?
We have to find its two children, and then we have to compare the elements priority and the children's
priority.
Right now, if the child's priority is less than the elements priority, then we have to swap it, right?
Because we need the the items with lower priority.
We want them up.
All right.
So let's go ahead and implement our bubble down function.
Let's say let ID is equal to zero because over here we are always going to start at the root node because
we are setting the node which we took out which is the last node.
We are setting it at the zeroth index.
Right.
So we have to bubble down from here only.
So let id is equal to zero.
And to make our code a bit shorter let's just write.
Let length is equal to this dot data dot length.
All right.
Now let's also find the element right.
So let element.
Is equal to this dot data at index zero.
That's the element which just got inserted.
This one over here.
All right.
Now let's go ahead and loop.
We need to have a while loop.
All right.
So let's write while true.
And we will break out of this when the node the element is at its right priority level.
All right.
So we'll see that.
And again remember it's pretty similar to the binary heap that we have already discussed.
Now let's go ahead and find its left and right child.
So for this let's find the index let's say left child.
ID is equal to two into id plus one.
And let right child ID is equal to two into id plus two.
So we have found the two indices of the children.
Now let's just make variables for the left child and the right child.
So let left child comma right child.
All right.
Now we also need a variable.
Let's call it smallest over here to understand to know whether we need to make a swap or not, or whether
the element is in the right place.
And we can just break out.
So we will track that with this variable smallest over here.
So initially we we make it just null.
Now we are going to check whether the left child index is less than the length.
If that is so then this is a valid index.
That means there is an element.
There is a child over there right.
So we will just find the left child which will be this dot data.
At the index.
Left child index.
All right.
Now we are going to compare the priority of this node and the priority of this element node over here.
All right.
So let's go ahead and check do that over here.
If left child dot priority.
If this priority.
Is less or greater.
What?
What do you think it should be?
We are.
We are going to check whether it is less right because we are we we are trying to understand whether
we need to make a swap or not.
So if it is less, then we need to make a swap, right?
So if it is less than element dot priority then we need to make a swap.
So we will change this.
Initially smallest was null.
So if this is the case then we will say smallest is equal to left child index.
So that indicates that yes a swap is required.
Now we do the same thing for right child.
So let's check whether the there is a right child.
So we check whether right child index is less than the length.
If that is the case yes there is a valid child over there.
So let's find the right child.
So right child will be this dot data at right child index.
All right.
Now we need to know whether we need to swap with this child or with this child.
So there are two possibilities, as by this time, one possibility is that smallest is still null,
right.
So that is a possibility or smallest could be left child index.
So let's write that over here.
Parallelly we will write that and discuss it.
All right.
So if smallest is null right.
Let me just write that over here.
If smallest is equal to null that means that it did not come over here.
Right.
So it was null initially and it did not come over here.
That means the left child with respect to the element is in the right position.
And we don't need to make any swaps, but we need to check whether the right child is in the right position.
So over here we will check whether right child dot priority.
Is less than element priority.
Now, if this is the case, even though the left child is correct with respect to the element, the
right child is not correct.
So we need to make a swap right now.
This could be a possibility or another possibility is that.
Let's just make some space.
Yep.
So another possibility is that smallest is not null.
That means smallest has been changed over here and smallest now is equal to left child index.
So let's write that parallelly.
So smallest is not equal to null.
Now it means that we have to make a swap.
Definitely.
But now we need to identify which is the correct element to swap.
Should I swap the element with the left child or with the right child?
So if in this case if the right child priority.
Is less than the left child priority right?
So the left child priority.
In this case, we swap with the right child right.
So we are trying to identify the element with the lowest priority because we want that to be the parent.
Right.
So we are going to check it like this over here.
Now if any one of these conditions is true let me just add a bracket over here.
Then we set smallest is equal to right child index.
All right.
So by this time when we reach over here, when we are done with these two areas, right when we have
checked this and this, we know whether we need to make a swap or not.
So that is one thing we know.
And if we need to make a swap, we know whether we need to swap the element with the left child or with
the right child.
All right.
So now let's go ahead and check whether smallest is still null.
If smallest is equal to null, that means that element is in the right position.
And we can just break out.
Right.
We don't need to make any swaps.
So we are done.
The element is in the right position.
So it has bubbled down to the correct position.
Right.
And we can break out.
But if this is not the case then we need to swap.
All right.
So if this is not the case let's go ahead and swap.
So we can say this dot data at ID.
Is equal to this dot data at smallest, right?
Now this would either be the right child index or the left child index, depending on which is the best,
which has the smaller prior priority.
All right.
So we we put that value over here.
Then we say this dot data.
At smallest.
Is equal to element, right.
We have already stored that over here.
So element is.
This one over here.
That was the initial node.
Right.
So we put that to this dot data at smallest.
Now we have swapped these two values.
Now we just need to set ID is equal to smallest.
This is required because once we have done a swap, we have to check that node with its parent, right.
So it has to keep happening.
The loop has to go on till the node is at its right place, such that the parent's priority is not less
than the child's priority.
So that would happen over here.
And when we find smallest is equal to null, we will break out.
So that is it.
So we have successfully coded the bubble down as well.
Now let's go ahead and test our function.
So we have written the n q function.
And we needed the bubble up function along with the n q function.
And we have written the dequeue function.
And we needed bubble down over here as well.
All right.
Now let's go ahead and test it.
Now let's say let.
Priority queue.
Is equal to new priority queue.
Now let's go ahead and NQ five jobs with different priorities.
So let's say.
Prior q dot nq.
And let the value be job one.
And the priority is three.
So it's like a to do list, right?
A to do list with different jobs and different priorities.
And we define that priority one is the most important thing for us which is most urgent to be done.
All right.
So let's have the second job and let it have a priority of four.
And then we have the third job.
Let it have a priority of one.
Then we have the fourth job.
Let it have a priority of two.
And then we have one more job.
This is job five.
Let it have a priority of one.
All right.
So let's go ahead and run our code now.
All right.
So we have n cubed these five nodes to our priority queue.
Now let's keep this over here so that we can test whether it's working.
All right.
Now, how should it be initially when let's just parallelly create it probably over here.
Right.
So let me just use these numbers only.
Right.
So initially we have three.
So I have three.
Let's just write it over here.
Then when we end Q four.
Right.
So four will be added over here.
And then you can see that three has a lower priority than four.
So it's fine.
So it's in its correct position right.
Next we insert job three which has priority one.
So that's inserted over here.
Right now we can see that the priority of three is greater than one.
So we would have to swap it right.
So we get one over here and we will get three over here.
All right.
And then after that we insert job with priority two.
So that's over here.
All right.
Now, when we check these two, the priority of four is higher, right.
So we need to swap them.
So we get two over here and we get four over here.
And when we compare one and two, it's in the correct position.
Then what?
We have inserted this one.
Then we insert another job with priority five.
Priority one.
Right.
So it will it will come over here.
It comes over here.
Now when we compare this and its parent, we have to swap, right?
Because this is a higher priority.
So we get one over here and we get two over here.
And that's it.
Right.
So again with with respect to this this is equal priority.
So we don't need to swap.
So this is how it should look.
That means we should have one then one three and four and two.
So let's look at the data over here our output.
So this is the expectation.
So we have job three which is priority one.
So that's correct.
Job three right.
It has priority one.
So that's this one over here.
After that we have job five which also has priority one which is this one over here which is correct.
After this we should get this one with priority three.
Right.
Which is job one.
Yes.
Job one with priority three.
That's correct.
Then we should get job with priority four which is job two.
So we have job two over here.
Priority four.
And then we have job four over here which is which has a priority of two.
So yes our output is correct.
Right.
So again let me just comment this out.
All right.
Now let's go ahead and call the DQ function over here.
Now we should be getting always the job with highest priority.
And with highest priority.
We mean numerically the lowest value because we have defined priority one to be the highest priority.
All right.
So let's go ahead and do that.
So we have.
Prior q and then dot d q.
Now it's giving me job three with priority one, which is correct.
Now let me do it again.
So I get job five with priority one, which is correct.
If I do it again I get job four with priority two, which is correct, right?
This is the next, uh, after removing these two are gone among three, four, two, two is the minimum.
So yes, our function, our dequeue function is working.
Correct.
If I call it again I get priority three.
And if I do it again I get priority four.
Now if I do it, there's nothing because the priority queue is empty.
So yes, our function our enqueue and dequeue functions are working.
Now we have returned the enqueue function and we have used bubble up over here.
We have written the dequeue function and we have used bubble down in the dequeue function.
Let's take a sample input and again walk through the code and also relook at the complexity analysis
of this solution.