In this video, we'll learn more about the Priority Queue.
The priority queue is a container adapter just like
the stack and the queue.
The priority queue allows insertions and removal of elements in order
from the front of the container.
Elements are stored internally in vectors by default.
But a data structure called the heap is used behind the scenes.
Don't confuse a heap data structure with the heap that
we used to store dynamically allocated data in our program.
They're totally different.
Elements are inserted in priority order.
So, the largest priority element will always be at the front of the
priority queue, that's pretty cool.
We can insert elements at the front and when we get an element from the
front, we're guaranteed that it will be the largest element in the container.
And it's super-efficient.
Iterators make no sense with priority queues, so they're not supported
and neither are the STL algorithms.
In order to use the priority queue, we must include the queue header file.
The priority queue has just a couple of methods that are super powerful.
The push method inserts an element into the priority queue in sorted order.
The pop method removes the top element from the priority queue.
And the top method accesses the top element without removing it.
The top element will always be the highest priority element which defaults
to the element with the greatest value.
Finally, we have the empty and size methods as we've seen before.
So, let's see a simple example of using the priority queue.
First, we create a priority queue, and we'll call it pq.
Behind the scenes, it's using the vector as the underlying container.
Then we push 4 integers onto the priority queue.
And then we display the top with pq.top.
In this case, 20 will be displayed because 20 was the largest element
inserted into the priority queue.
We can remove the element from the top with pq.pop.
And if we display the top again, we'll display 10 since 10 is
the next largest integer that was added to the priority queue.
That's it, it's really very simple and very powerful.
Let's head over to the ide and I'll show you an example
of using a priority queue.
Okay, so I'm back in the ide.
I'm in the section 20 workspace.
And I'm in the priority queue project, so what we'll do here is we'll
play around with a priority queue.
We'll do it both with integers, and we'll do it with an
object here at person objects.
So, I'm including q that's where the priority queue lives.
So, I need to include that to make sure that we have access to it.
We've got our good old person class that we've been using
throughout this section.
And again, it's same as it has been before.
This is the really important one right here that operator less standard
overloaded less than operator.
That's one we're going to use in a moment.
So, remember what it's doing.
Actually, what we'll do is we'll use it, and then we'll change it.
So, remember what it's doing here, it's comparing ages.
So, that's the ordering.
That it's going to use.
And that's what the priority key uses as well.
And let's see we've got the overloaded insertion operator
exactly like we did before.
I've got a template function here that expects a priority queue
of any type and it displays it.
This is destructive, so I'm passing by value.
You've probably seen this a bunch of times, now with queues and stacks.
And you're getting used to it.
So, I'm just getting the free while it's not empty.
I'm getting the top which is the biggest element.
I'm popping it and printing it until it's empty.
Alright, so that's what's happening there.
So, let's take a look at these two tests.
Test one, I'm creating a priority queue, and I'm looping through this
collection of integers here, and I'm pushing it on to the queue, to
the priority queue I should say.
Remember, what's happening here is when they're being pushed in, everything
the pushing all happens at the top but behind the scenes, it's ordering.
So, it's using a heap data structure behind the scenes, so
the top of this priority queue will always be the largest integer.
Now, in this case, notice I have 3, 5, 7 here.
And I have 3, 5, 7 here.
The duplicates will be put in there.
It's okay to have duplicates and priority queues, so that's
why I put them in there.
So, that's what we're doing here.
We're pushing all of those integers and then what's the
size, well, I pushed 12 of them.
What's the top one?
It's the biggest one, it's that 100 right there.
When I display the priority queue, you can see 100, 23, 12, 12,
7, 7, all the way down to zero.
You can see the ordering, it's exactly as we would expect
the top which is right there.
It's that 100 right there that is the greatest or the largest
integer in the priority queue.
So, let me clear this up.
So, now what I'll do is I'll pop that max element from the priority queue,
so that's going to take the 100 off.
And then when I display the priority queue, now the new top is 23, it's the
next largest number that was there.
That's really all there is to a priority queue, super powerful.
A lot of times, we have needs for something like this.
Let's say, we're doing operating systems, and we're scheduling
jobs, and they have to run based on a certain priority.
This is awesome.
We use priority queues all the time because they make a lot of
sense and they're super-efficient.
So, let's take a look at test two.
In test two, I've created a priority queue right here, pq
again of person objects this time.
And I'm pushing a bunch of person objects now.
I named these people a through f just so we can see the
ordering with the string.
And then I've got some, just random numbers here.
We can see that the largest number is 27.
Remember before we said that the operator less than for
the person class was checking age that's the discriminant.
So, in this case, when we put these things on these person
objects on the priority queue, and we display the priority queue,
look what we're getting here.
Notice that it's not ordered by name, we've got f, and d, and c, and a, and
e, and b, it's ordered by that age.
So, the person with the largest age is at the top of the priority queue.
So, we've got 27, 18, 14, 10, 7, and down to 1.
That's it, that's pretty cool.
So, if I decided to, let me just stop this and if I decided
to change the order, remember, right here, it's ordered by age.
So, if I decided to come up here to my person class, let me scroll
up a little bit right here.
And let's say that I want to change this, so it doesn't check age
instead it'll do, let's say, name, so we're going to return this.>name
less than the right hand sides name: something like that.
Now when we run this again, you can see the output right over here.
Let me move that over just a little bit, so I can write.
You can see the output right here now.
It�s no longer by age, right.
It just happens to be 27 there because of the f, but
it's f, e, d, c, b, a, right.
So, f is the largest name.
If we go the other way, we've got a, b, c, d, e, f, right, so there you go.
So, if I remove the top, it's going to remove f: 27 right there, that's it.
That's it for the priority queues, very useful data structure to know
about, dead simple to use in C++ with the standard template library.
A lot of other programming languages have libraries that
support just about everything that's in the STL, and they're
all pretty easy to use actually.
What's really important is that you practice and you understand the
STL, you just do a lot of examples.
I did a lot of examples in these videos.
And I did that as I said for a reason, it's really the best way to learn this
is to just go along with me, and tweak yours, and make yours different, and
change like I just did right here.
You know, change this, and see what the effect is and that's how you
really, really, learn this stuff.
Alright, so that is actually the end of the STL.
Hurray! Right?
It ended up being a lot longer than I thought it was going to be.
I re-recorded some videos, and I hope it's useful to you all.