Hello again! In this video, we are going to look at the priority queue.
We were discussing at the end of the last video, that the standard queue has the element arranged
in arrival time.
And sometimes we need to be able to process some element before others.
For example, if we have a restaurant, the customers who have a reservation will get seated first, and
then we see if there are any seats for customers who do not have a reservation.
If we have an event and some celebrities or VIPs turn up, they expect to go straight to the front of
the queue and not have to stand behind the peasants. And in C++, we could implement this using a priority
queue.
So this is pretty much the same as the standard queue, except that the order of the element depends
on their importance, and not their arrival time.
So the most important element are going to be at the front, so they get processed first. And the least
important element are going to be at the back, so they get processed last.
And C++ has a priority queue, which is also in the queue header. By default,
the less-than operator of the element's type is used for ordering the element in the queue.
If two or more element have the same priority, then by default the queue does not take account of
that.
So there could be in any order, relative to each other.
So our queue could look like this. We have our element. The most important element is at the front, and the
least important element is at the back.
These are ints, so they are ordered using the less-than operator.
If we add a new element, it goes into the appropriate place for its priority.
So 2 is greater than 1, but not greater than 3.
So it goes between 3 and 1.
When we remove an element, it is always the one with the highest priority. And then the element with
the next highest priority moves to the front of the queue.
The priority queue in the library can be implemented using a vector or a deque.
The interface is similar to queue, but not quite the same. So we can use push() and pop() to add and remove
element.
When we add an element, it goes in front of all the element which have lower priority. When we call
pop(),
this removes the element from the front of the queue. And then the element with the next highest priority
becomes the new front element.
To get the element from the front of the queue, we call top(). So that returns the element with the highest
priority.
There is no function for getting the element at the back of the queue.
And then we have empty() and size() again.
So here is our example. We have our print() function again, for getting the details.
We have to call top() instead of front(), because that is the name.
And there is no back member function.
Then we create a priority queue
object. We call push() a few times.
So we would expect that 5 is at the front of the queue, and 1 is at the back.
So this is the same queue that we had on the slide.
Then we call push(), to add in element with value 2.
So that should go between 1 and 3.
And then we call pop(), to get the top element.
So that 5 has been removed from the queue, and now the element at the front is 4.
So there we are. So the highest priority element is 5. Then we add the element. And then, after
removing the top element, the highest priority element is now 4.
Priority quese are useful for processing data which needs to be - well, prioritized!
So, for example, if you are writing an operating system scheduler.
So this will decide when the process gets time from the CPU processor.
And if we have an important process, we can give it more time, more attention from the processor.
And the less important processes gets less time.
For networking, sometimes we need to have so-called "out of band" of communication. So we can send our
data packets with a normal priority.
And then if we have some important message: for example, we want to drop the connection immediately.
We can send that with a higher priority and the receiving end will process that immediately.
So that avoids having to wait for it to get through
all the data it has already received, by which time it could be too late.
And if we have a management system for bug reports, we could order the bugs by priority. So the serious bugs
get fixed before the developers look at the minor bugs.
In a priority queue, we can only access the top element. If you are going to need access to other
elements, then you can use a map instead.
The key for the map will be the priority of the element and the value will be the data.
Elements which have the same priority are not necessarily in arrival order. If that is important,
then are were a couple of things you can do.
You could use a nested map.
So this is a map whose key is the priority.
And then the value is another map, which has the arrival
time as key, and the data as value.
If we are using a class of our own, then we could redefine the less-than operator.
So it takes account of the arrival time.
Okay, so that is it for this video.
I will see you next time.
But until then, keep coding!