I have a Priority Queue in which I add a Node object to, where the Nodes should be sorted by a value that they contain. For some reason, the priority queue will not sort the Nodes on add. If anyone can see something wrong with this or has any guidance, I appreciate it. Here is a brief example:
PriorityQueue<Node> PQ = new PriorityQueue<Node>(); //for each entry create a node and add it to the PriorityQueue for(Entry<Character,Integer> entry : entries){ PQ.add(new Node(entry.getKey(),entry.getValue(), true)); }
here is the node's compareTo
method:
@Override public int compareTo(Node n) { if(n.frequency.intValue() > this.frequency.intValue()) return -1; else if(n.frequency.intValue() == this.frequency.intValue()) return 0; else return 1; }
util. PriorityQueue implements a binary heap. Unfortunately, there is no easy way to sort a PriorityQueue. If you poll() objects until the queue is empty, the elements will be in the comparator's order.
There is an obvious way to do sorting with priority queues: Take the items that you want to sort, and insert them into the priority queue (using the item itself as its own priority). Then remove items from the priority queue until it is empty. The items will come off the queue in order from largest to smallest.
Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue.
min-heap and max-heap are both priority queue , it depends on how you define the order of priority. That is to say, a priority queue can be a min-heap or a max-heap in your algorithm.
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 order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
The only guarantee provided by PriorityQueue
is that poll()
, peek()
, etc return the least element. If you need ordered iteration of elements, use some other collection such as TreeSet
.
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