Hi everyone.
In this video, let's get introduced to a new data structure called Priority Queue.
Now a priority queue is a data structure where each element has a priority.
All right.
Now typically a priority queue is implemented with a heap though you can do it in different ways.
Implementing it with a heap is more efficient.
And that's why we will go ahead in this manner in this section.
Now, in a priority queue, every node has a value as well as a priority.
Now earlier when we discussed a binary heap, we epiphyte based on the value.
But in the case of a priority queue we will heapify based on the priority.
All right.
So that's the only difference.
So over here we will need a node class because every node will have a value and a priority.
And then if you want we can store it as an array.
But then every element will be a node in the array.
All right.
Now we will have two types of priority queues.
One is a max priority queue.
In this case the top element or the first element which would be returned or removed will be the element
with the maximum priority.
All right.
And similarly, in the case of a min priority queue, the first element which would be returned would
be the element with a minimum priority.
Again, it depends on how you define it.
Let's say you define that some something that is of priority one is most important.
In that case you would ideally implement a min priority queue.
But then if you implement something where you say that as high the priority, let's say you have a priority
100 greater than priority five.
In that case you would implement a max priority queue.
So again it depends on how you want to do it.
Now let's quickly take a look at a common Big-O operations operations of a priority queue.
You can see that removal and insertion is O of log n time complexity.
That's because we are implementing the priority queue as a binary heap.
So you will see that it's the same for a binary heap as well.
That's because we have to do just one comparison per level.
And because a binary heap is a complete binary tree, the height of the binary heap will be log n,
right.
So the number of comparisons would be the maximum depth of the tree, or the height of the tree, which
is log n and then peaking at the maximum or minimum priority element, depending on whether you have
a max binary heap or a min binary heap is going to be constant time and space.
Again, that's because you know that the value with the maximum priority in the case of a max binary
heap would be the topmost element.
And similarly, in a min binary heap, the value with the minimum priority would be the top element,
so you know where it is.
So you can directly go ahead and peek at that element.
So that's why the time and space complexity of this operation is o of one.