Hi everyone, let's do this question.
Implement a priority queue as a min binary heap.
The priority queue class should support the following functions n queue to insert an element.
D queue to extract the element with the highest priority.
Lowest numerical priority is treated as highest priority.
All right.
So let's go ahead and do this question.
Now notice over here it's mentioned we have to implement the priority queue as a min binary heap.
And the same thing is mentioned over here.
Lowest numerical priority is treated as the highest priority.
All right so let's go ahead.
Now remember priority one is the lowest numerical priority right.
So let's treat it as let's treat this as like this.
Now again it's unlikely that functionally we would say that something has a priority minus one.
But again if that is taken in then we would treat that as lesser than one.
But again, it depends on how we are on the use case.
Right on why we are implementing this.
So over here we are treating that priority one is the highest priority.
So I'm just writing this over here to show that we are building a min priority queue or a min binary
heap, right?
We are using a min binary heap to implement this min priority queue.
Now let's say we have first a job A so it can be any value.
Now it has a priority three.
Now the difference of this implementation from the implementation where we implemented the max binary
heap is that there we only had the value.
But over here we have a value.
This is the value which is job A.
So it can be a text or it can be something like that.
And then we have a priority right.
So there are two properties to each node.
So we'll have a node class over here to implement this.
Now let's say to the priority queue we insert another job which is job B and that has a priority one.
All right.
So again we insert at the end.
So we have inserted this.
And then now we need to shift it up or bubble it up to its correct position.
Right.
So we need elements with a lower priority up.
So over here we will need to swap them right.
So let's go ahead and swap them.
And we will have job B over here at the root.
And then job A comes over here.
All right.
So we have swapped them.
Now let's say we insert another job which is job C over here.
And let's say it has a priority two.
Now we have to check whether we do need to shift up.
And over here we see that we don't need to.
Right.
Because the priority is the children priorities are, uh lower.
So with higher priority, I mean, numerically it has to be lower.
So three and two are greater than one.
So they are in the correct position.
All right.
So again we will be storing these as nodes.
So let's say this is node b.
This is node A and this is node c.
So the array will look like this.
So this is node b node a and node c in our array.
So when we implement the min binary heap we will still implement it as an array.
But then in the array instead of just a value we will have nodes over here.
And each node has a value and a priority.
Now let's say we insert one more element again which is job D.
Again we insert it at the end.
All right.
So that's similar to what we discussed when we discussed the max binary heap implementation.
So we inserted over here.
And then we shift up or we bubble up to the correct position.
Right.
So again adding over here can is visually that's how we see it visually.
But when it comes to the array we are storing it as an array.
Right.
So we will be just pushing to the array.
That is we are just adding over here.
And then we bubble up.
So let's check these two.
This one and its parent right.
So A is the parent of D.
Now you can see that three is greater than two right.
So this is not following the min heap property.
So we have to swap them.
So let's swap them.
All right.
So we swap them and we have D over here and a over here.
And now this is how it looks like we have B.
Then we have d and C and then we have a.
So this is how it looks.
So this is how the enqueue function of this priority queue works.
So it's pretty similar to the case where we discussed the max binary heap.
The difference is that over here we have nodes and each node has a value and a priority.
And then of course we are implementing a min binary heap over here.
Earlier we did a max binary heap.
Now let's see how d queue works.
Or removing or extracting the uh the job with the highest priority.
Now priority one is the highest priority or numerically we want to extract the job with the numerically
lowest priority, which is one over here.
Now let's say we extract this.
That is we are returning this value.
Right.
So we return or serve the job B serve job B when we call the dequeue function.
And then what we do is.
So again look at the scenario.
We are taking this element over here which is the first element.
So that is served first right.
So we remove from the beginning.
And then what we do is so this is just served.
And then we pop the last node from the array and we place it at the zeroth index.
So we put this over here.
And after we do this we just sift down or bubble down.
So this is the same thing that we discussed previously.
So let's see how this looks now.
Now right A is now at the root node.
And then we have D and C over here.
And then we bubble down.
Now let's check over here.
The children both have the same priority right.
So we can just swap with this one over here.
So we swap and we need to swap because three is greater than two right.
So we swap and we have D over here and A and C over here.
And that's that.
So that is how enqueue and dequeue work in the priority queue where we have implemented the priority
queue as a min binary heap.
Now let's quickly look at the complexity analysis of the enqueue and dequeue functions which we just
now discussed.
You will see that the time complexity of both of this is O of log n in the best average and worst case,
and the space complexity is the same is is constant.
So it runs in constant space, which is O of one.
You can see that because we implemented the priority queue as a min binary heap, the time and space
complexity is the same as that for a binary heap, which is O of log n and O of one space.
And again, this is because of the bubble up and bubble down which is happening.
Right?
So when we enqueue something, when we insert something, we insert at the end, and then what we do
is we bubble up, right?
So we bubble up.
And we have seen that the time complexity of the bubble up function is O of log n.
So the same logic appears over here.
And when we dequeue we uh serve the first element.
And then we take the last element and put it at the root node.
And then we bubble down right or sift down.
And again, we have seen previously already that the time complexity of the bubble down function is
O of log n.