Menu
The Priority Queue implementation in the Java standard library appears to be a min Priority Queue which I found somewhat confusing. In order to turn it into a max one I created a custom comparator object.
Comparator<Integer> cmp = new Comparator<Integer>() { public int compare( Integer x, Integer y ) { return y - x; } }; I was wondering if there was a more elegant solution. Essentially I wan't a generic priority queue that could be used to implement Dijkstras etc. I didn't even realise there would be ones which operated in reverse :/
306
Q #4) Is Java Priority queue max or min? Answer: By default, the priority queue in Java is min Priority queue with natural ordering. To make it max, we have to use a custom comparator so that head of the queue returns the greatest element in the queue.
To update priority in Priority Queue, get the index of the element that you want to update the priority of and assign a new key to the element. After updating the priority of an element, we need to heapify the heap to maintain the heap data structure.
PriorityQueue allows duplicates. So if you want to avoid that, you need to implement your own version of Queue. You can find very elegant way, how to do that in "Effective Java", page 85.
Now when you need to change the priority of an item, simply add the same item to the queue with a different priority (and update the map of course). When you poll an item from the queue, check if its priority is the same than in your map. If not, then ditch it and poll again.
Here is a code snippet using Collections.reverseOrder()-
PriorityQueue<Integer> maxPQ = new PriorityQueue<Integer>(20,Collections.reverseOrder()); You also need to provide the initial capacity of the Priority Queue (20 here) along with the Comparator.
120
Use Java's Collections.reverseOrder() comparator.
Java Reference
40
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
