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).
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.