First define the lambda object, then pass it to the template’s type using decltype and also pass it directly to the constructor. auto comp = []( adjist a, adjlist b ) { return a.second > b.second; }; priority_queue< adjlist_edge , vector<adjlist_edge>, decltype( comp ) > adjlist_pq( comp );
As you discovered, a priority queue does not resort all elements whenever an element is added or removed. Doing that would be too expensive (remember the n log n lower bound for comparison sort), while any reasonable priority queue implementation (including PriorityQueue) promises to add/remove nodes in O(log n). In fact, it doesn’t sort its … Read more
The logical argument is as follows std::priority_queue is a container adaptor; basic memory considerations make the back the preferred place for modifications (with pop_back() and push_back()) for sequence containers such as std::vector. the priority_queue primitives are based on std::make_heap (constructor), std::pop_heap + container::pop_back (priority_queue::pop) and on container::push_back + std::push_heap (priority_queue::push) pop_heap will take the front … Read more
You can’t traverse a Priority Queue in that order because of the underlying implementation (I think it’s min-heap in Java). It’s not a sorted array, so that you can just go from one element to the one with the lesser priority. Peeking (read the top element heap in the heap) is constant time O(1) because … Read more
How can you say Lucene’s doesn’t support a custom comparator? Its abstract and you must implement the abstract method lessThan(T a, T b)
I guess you expect PriorityQueue to return elements in particular order when you iterate it. However, PriorityQueue doesn’t provide such a behaviour, because it’s implemented as a priority heap rather than sorted list. From javadoc: The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular … Read more
Note – You may also want to check other answers, especially the one with decltype and lambda You should declare a class Compare and overload operator() for it like this: class Foo { }; class Compare { public: bool operator() (Foo, Foo) { return true; } }; int main() { std::priority_queue<Foo, std::vector<Foo>, Compare> pq; return … Read more
You have to remove and re-insert, as the queue works by putting new elements in the appropriate position when they are inserted. This is much faster than the alternative of finding the highest-priority element every time you pull out of the queue. The drawback is that you cannot change the priority after the element has … Read more
You need to poll the items from the PriorityQueue one by one. toString doesn’t do that. So instead of your System.out.println(queue); do this: while(!queue.isEmpty()) { System.out.println(queue.poll()); } The reason is that the PriorityQueue is never completely sorted internally, lookup how a heap works for more detail. Polling items from it fixes the heap during the … Read more
Use the constructor overload which takes a Comparator<? super E> comparator and pass in a comparator which compares in the appropriate way for your sort order. If you give an example of how you want to sort, we can provide some sample code to implement the comparator if you’re not sure. (It’s pretty straightforward though.) … Read more