greater (x,y) comparator basically returns whether (x>y).
Hence in a priority queue, when for comparison two values (A,B) are passed into the comparator, shouldn’t it return bool value whether A should appear before B, right? (such reasoning would mean if A>B, A should appear before B, hence forming a MAX HEAP)
However, when priority queue is declared using:
priority_queue<int,vector,greater > pq;
It forms a MIN HEAP. Why?
Greater<int> comparator
Max Heap : priority_queue pq;
Min Heap : priority_queue<int, vector, greater > pq;
greater(x,y) returns true when x>y. True means that the values should be swapped.
So when x>y, x and y are swapped and now y is above x in the heap. Hence it forms a min heap.
Okay sir. Here, greater comparator signifies whether (x,y) should be swapped.
Just want to confirm, that in sort() functions when we define a comparator, there greater comparator (x,y) signifies whether x should appear before y right? Because there greater comparator returns descending sorted array/vector.
Yes that’s correct for sort function as well.
Confirming again:
Priority queue- ComparatorClass(a,b)- bool directing whether they should be swapped (true = swap)
Vector/Array- Comparator(a,b)-bool directing whether they should stay the same (true = no swap)
true simply means that the values should be swapped. It applies to both priority queues and vectors.
Could you explain the output; using greater comparator on both vector and priority queue?
Input : 8,10,1,6,4,5,7,9,2,3
Using greater comparator:
Vector --> 10 9 8 7 6 5 4 3 2 1
Priority Queue --> 1 2 3 4 5 6 7 8 9 10
The inbuilt sort function used for sorting vector is a combination of 3-4 different sorting algorithms. So just learn it that by taking greater, it sorts the elements in descending order.
And this applies for priority queue as well.
But sir, taking greater is sorting vector in descending order and priority queue in ascending order…
Yes that’s right. Just learn it as a concept.