-1

Can anybody please explain what is the meaning of this declaration:

typedef pair<long long, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > Q;

Is it to be treated as a priority queue of pair of long long and int or something else? Can please someone also explain what is greater<PII> here?

1

3 Answers 3

5

This declares a std::priority_queue containing std::pair<long long, int> instances where a std::vector<std::pair<long long, int>> is the underlying container of the priority queue (as it is a container adaptor).

The std::greater<std::pair<long long, int>> is used as the Comparator function object for the queue, checking whether the LHS pair is greater than the RHS pair. See below for a reference:

http://en.cppreference.com/w/cpp/utility/functional/greater

2

Using greater here means that lower values are considered of higher priority and come out of the priority queue earlier. By default less is used, and higher values are higher priority.

Pairs are ordered lexicographically; (1, 3) comes before (2, 1) and after (1, 2).

1
  • 1
    @Alan Stokes Exactly what I was looking for :)
    – Euler
    Apr 11, 2017 at 19:30
0

This is way to create min heap in c++ .

typedef pair<long long, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > Q;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.