Now that we've learned about Queues, let's learn about Priority Queues, which are an application of them.

Why is the modifier "Priority" attached?

The queue we know is a data structure where the first one in is the first one out.

You can think of a "Priority" Queue as a queue where the "priority" of what comes out first is specifically defined.

Let's look at the basic declaration method.

#include <queue>
using namespace std;

priority_queue <int> pq;

The header for a priority queue also uses #include <queue>, just like a regular queue.

The functions of a priority queue are similar to the queue we learned earlier.

push() for inserting elements, pop() for extracting them, and size() and empty() related to the number of data items are all the same.

However, there is only one difference.

In a queue, we used the front() function to find the first element,

but a priority queue uses the top() function. As you can tell from the function name, it's called the top, not the front. Keep this in mind.

So, what is that "priority" that determines which element comes out of a priority queue? Which element comes out first?

Usually, the size of the data is the criterion. Let's look at the code below.

priority_queue <int> pq;

pq.push(1);
pq.push(10);
pq.push(7);

cout << pq.top() << '\n'; // Output 10
pq.pop();
cout << pq.top() << '\n'; // Output 7

If this were just a regular queue, the 1 that was inserted first should come out first.

However, in a priority queue, 10 comes out first.

This is because 10 is the largest among the elements inside.

When you call the pop() function once, the largest element, 10, is removed.

Now, the largest among the remaining elements becomes 7.

Therefore, if you output top() once more in the code, 7 will be printed.

Priority queues are simple. The largest element is always at the top.

When you pop(), the maximum element that was at the top is extracted,

and it's a structure where the largest among the remaining elements moves back to the top.

Then, how do we make the smallest element move to the top?

There are two methods. Both are widely used.

Method 1: Inserting with the sign reversed

If you want to find the minimum value among several integers x1, x2, x3, ...,

you can find the maximum value among -x1, -x2, -x3, ..., which have their signs reversed.

Then, you can just reverse the sign of that maximum value again.

The simple code is as follows.

priority_queue <int> pq;

pq.push(-1);
pq.push(-10);
pq.push(-7);

cout << -pq.top(); // Output 1

Push -1, -10, -7 instead of 1, 10, 7.

Then, the largest among them, -1, is stored in top(), and by reversing its sign again, you can find the minimum value, 1.

Method 2: Declaring priority_queue with a comparator

If you declare it by adding vector<data_type> and greater<data_type> at the end, as in the code below,

the minimum value automatically comes to the top instead of the maximum value.

It requires a bit of memorization, but it has the advantage of making subsequent processes more convenient.

priority_queue <int, vector<int>, greater<int>> pq;

pq.push(1);
pq.push(10);
pq.push(7);

cout << pq.top(); // Output 1

By adding vector and greater as in the code above, there's no need to handle 1, 10, and 7 by reversing their signs later.

The minimum value, 1, automatically moves to the top().

Finally, let's put a struct inside the priority queue.

Naturally, to compare the sizes of struct data, you must overload the comparison operator inside the struct.

If you don't remember this theory well, check out this link again.

struct Data{
    int x, y;
    bool operator<(const Data &Right)const{
        return x < Right.x;
    }
};

priority_queue <Data> pq;

In the code above, the operator compares two structs based on x.

If you define and insert the operator like this,

the struct with the largest x value will come to the top of the pq.

Conversely, to make the struct with the smallest x value come to the top, just change the sign like return x > Right.x.

struct Data{
    int x, y;
    bool operator<(const Data &Right)const{
        return x > Right.x;
    }
};

priority_queue <Data> pq;

Why use a priority queue? When should we use it?

A priority queue can find the maximum/minimum value quickly and in real-time.

Both the push() and pop() functions have a time complexity of O( log N ), where N is the number of data items.

Because it has a logarithmic time complexity, the processing speed is very fast.

Even if there are 1 million data items, finding the maximum/minimum value only takes about log 1,000,000 ≒ 20 operations.

When high-speed operations are required,

and when you only need information about the maximum/minimum value, think of a priority queue.

<Application Problem>

At the Jungol Surgical Emergency Room, when patients are admitted, they are asked for their age and the amount of bleeding.

The higher the amount of bleeding, the sooner the surgery is performed; if the amount of bleeding is the same, the older patient is operated on first.

Write a program that processes patient admission and surgery data in real-time.

Admission data is given in the order of name, age, and bleeding amount (ml), such as "push Thomas 37 120.6",

and surgery data is given as "pop". In this case, if there are no patients, it is ignored.