3

When I used std::greater<int> as a comparison function object in std::sort as the following:

std::sort(array_name, array_name + length, std::greater<int>());

The array sorted in non-increasing order (i.e. the largest number first)

But, when I used the same comparison function in std::priority_queue as the following:

std::priority_queue <int, std::vector<int>, std::greater<int> > pq_name;

Why the std::priority_queue::top member function returns the smallest number first?

(I need a clear comparison between the two cases).

Improve this question
2
  • 1
    perhaps it would be clearer if you read first the difference between min heap and max heap. Commented Apr 9, 2018 at 0:17
  • @codekaizer Ok, I'm reading about that now and it's seems like an useful hint from you, thank you. Commented Apr 9, 2018 at 0:38

2 Answers 2

Reset to default
4

In order to understand why this happens, you have to understand the data structures that you're working with.

Q: What is an array? A: An array is a contiguous region of memory containing a type. As far as we are concerned it can contain any type of object. But since you're working with int, in C++ an integer is tipicaly formed by 32 bits, but it depends. Therefore, your representation in memory would be something like,

| 4 bytes | 4 bytes | 4 bytes | (...)

When you're sorting an array, the std::greater<int>operator will "sort" your array by keeping the greater integer in the first position, the second largest value in the second position, and so on.

Q: What is a std::priority_queue? A: A priority queue is a heap, more specifically, a binary tree. A heap is a data structure that is optimized to return the largest value by default. This type of heaps are called max heaps. But when you overload the comparison within the priority_queue using the std::greater operator, you are transforming the heap into a min heap. This kind of heaps, similarly to what happens when you overload the std::sort method operator, is implemented to retrieve the minimum value first.

Keep in mind that the representation of a heap in memory is completely different from the one found in an array.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Your way in explaining is very simple and amazing, thank you.
4

CPPRef says on it:

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater would cause the smallest element to appear as the top().

Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare.

So, for a default std::less-based ordering, top of the queue is the largest element, the one that comes the last when sorted. OTOH with std::greater the last element is the smallest one.

Improve this answer

2 Comments

Actually I read that in the same reference before asking, but I really still don't have a clear comparison between the two cases and why std::priority_queue behaves like that ?!!. thank you.
While std::priority_queue outputs largest elements first, why the default is std::less instead of std::greater (unlike the first case in the question) ?!

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.