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 );
From the documentation of PriorityQueue.iterator(): Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order. That’s what toString() is using to construct the string representation, as the implementation is inherited from AbstractCollection: Returns a string representation of this collection. The string representation consists of a … Read more
Array based heaps seem ideal for your purpose. I am not sure why you rejected them. You use a max-heap. Say you have an N element heap (implemented as an array) which contains the N smallest elements seen so far. When an element comes in you check against the max (O(1) time), and reject if … Read more
que.add(d); if (que.size() > YOUR_LIMIT) que.poll(); or did I missunderstand your question? edit: forgot to mention that for this to work you probably have to invert your comparTo function since it will throw away the one with highest priority each cycle. (if a is “better” b compare (a, b) should return a positvie number. example … Read more
The reason for using decrease-key rather than reinserting nodes is to keep the number of nodes in the priority queue small, thus keeping the total number of priority queue dequeues small and the cost of each priority queue balance low. In an implementation of Dijkstra’s algorithm that reinserts nodes into the priority queue with their … Read more
Two things need to be adjusted in your implementation. First, you should use a queue, rather than a stack, as your auxiliary data structure. The pushing items into a stack and then popping them back out will result in them being added back into your priority queue in reverse order. If they come out of … Read more
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
Below is what I believe to be a truly efficient version of a PriorityQueue which uses an array-based binary heap (where the root is at index 0, and the children of a node at index i are at indices 2i + 1 and 2i + 2, respectively). This implementation includes the classical priority queue methods … Read more
The priority queue adaptor uses the standard library heap algorithms to build and access the queue – it’s the complexity of those algorithms you should be looking up in the documentation. The top() operation is obviously O(1) but presumably you want to pop() the heap after calling it which (according to Josuttis) is O(2*log(N)) and … 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