2

Following code uses same comparator function with vector and priority queue. However order produced by both data structures is different. I would like priority queue to behave in same way as vector.

I have two questions

  1. Why is order different?
  2. How can i make priority queue's order to be same as vector?

Here's the output of following code:

enter image description here

//Please ignore extra header files, I know I don't need them. #include <iostream> #include <vector> #include <algorithm> #include <string> #include <queue> #include <stack> #include <iterator> #include <unordered_map> #include <functional> using namespace std; class Solution { public: typedef pair<string, int> PII; static bool cmp(const PII& a, const PII& b) { if (a.second == b.second) return a.first < b.first; return a.second > b.second; } void func(vector<string>& words) { unordered_map<string, int> hMap; for (const auto& w : words) hMap[w]++; std::priority_queue< PII, std::vector<PII>, std::function<bool(PII, PII)> > Q(cmp); vector<PII> V; for (const auto& e : hMap) { Q.emplace(e); V.emplace_back(e); } std::sort(V.begin(), V.end(), cmp); //Now why does order of elements is different in vector V and priority_queue Q, despite using same comparator function? int size = Q.size(); cout << "Order in priority Queue:" << endl; for (int i = 0; i < size; i++) { PII e = Q.top(); cout << e.first << ":" << e.second << endl; Q.pop(); } cout << "Order in vector:" << endl; for (const auto& e : V) { cout << e.first << ":" << e.second << endl; } } }; int main() { Solution s; vector<string> words = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is" , "we" , "we" , "we" }; s.func( words ); return 0; }
Improve this question
2
  • Quote from cpreference "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." Commented Apr 29, 2020 at 8:17
  • @Evg Why is it being closed as duplicate? I know how to use comparator for min heaps. This question is about the way comparator is interpreted by both data structures. Commented Apr 29, 2020 at 8:19

3 Answers 3

Reset to default
3

The order is different because < relation implies that std::sort sorts values in ascending order, and that std::priority_queue places the maximum element at the top. This is by design.

If you want to reverse the order in the priority queue, you need another comparator that swaps the arguments,

bool cmp2(const T& a, const T& b) { return cmp(b, a); } //... std::priority_queue<T, std::vector<T>, decltype(&cmp2)> queue(cmp2);

This is in perfect analogy with going from std::less to std::greater as explained in this question.

Instead of introducing a separate function, you can use a lambda:

auto cmp2 = [](const auto& a, const auto& b) { return cmp(b, a); }; std::priority_queue<T, std::vector<T>, decltype(cmp2)> queue(cmp2);
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Priority Queues and vectors use comparators differently. To understand the output of priority queue, you must understand its working. Priority Queue is effectively a heap with an element on top depending on the comparison function. To quote from boost Priority Queue

The comparison function used to determine whether one element is smaller than another element. If Compare(x,y) is true, then x is smaller than y. The element returned by Q.top() is the largest element in the priority queue. That is, it has the property that, for every other element x in the priority queue, Compare(Q.top(), x) is false.

In your case changing the comparison function to reverse the order should solve the issue.

Improve this answer

Comments

0

This can be confusing, but I will try to explain why this happens.

To understand the Comparator, we need to know when it is called in both contexts:

1. Priority Queue: When a new element is inserted, the Comparator is invoked. A priority queue is implemented as a complete binary tree using a vector. When a new element is inserted, it is initially placed at the last index of the vector. After insertion, the "heapify-up" process occurs, where the inserted element is compared with its parent. In a max-heap, if the inserted element is greater than its parent, a swap occurs. This process is repeated until the element reaches the top of the heap. The Comparator determines whether or not to perform the swap: for example, in a max-heap, if the Comparator indicates that the top element should be greater than the child, the swap will not occur if the top is already greater; otherwise, if the top is less, the swap will happen.

2. Vector Sorting: When sorting a vector using any sorting algorithm, the Comparator is used to compare two values and determine whether to swap them. For instance, if the Comparator indicates that the left-hand side (lhs) value is less than the right-hand side (rhs) value, then no swap is made. Conversely, if lhs is greater than rhs, a swap will occur.

Comparator Logic:

  • For a min-heap, the Comparator should define that lhs < rhs means no swap is needed, as the smaller element should be at the top.(here in this context lhs is top or parent of the node that we are comparing with)
  • For a max-heap, the Comparator should define that lhs > rhs means no swap is needed, as the larger element should be at the top.
  • For **ascending order sorting, lhs < rhs indicates that no swap is needed, as the smaller element should come first.
  • For descending order sorting, lhs > rhs indicates that no swap is needed, as the larger element should come first.
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.