Priorityqueue Not Sorting on Add

PriorityQueue not sorting on add

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.

Priority queue is not maintaining sorting order

In a priority queue, the only guarantee you have is that the head is the lowest (or greatest, depending on your comparison). The internal structure is not necessarily a sorted list. Actually, in Java, it's a heap:

PriorityQueue

An unbounded priority queue based on a priority heap.

However, if you do a loop that poll() the first item, then print it, again and again until the priority queue is empty. The elements should be printed from the lowest to the greatest element.

Java Priority Queue Not Sorting Properly

What's likely happening is that you are modifying the bound of instances that are currently in the PriorityQueue when you do things like u.bound = bound(u);. First time through the loop, you set the u.bound and put it in, next time through you change u.bound again without pulling it off the queue first.

If you're using an organized collection (HashSet/Map, TreeSet/Map, PriorityQueue, etc) and you change an elements value in such a way as to affect how the collection is organized, you are breaking the assumptions on which that collection is organized, and they will fail in various interesting ways. I think that's what's happening here.

Some questions that talk about this for other collection types:

• Immutable object as key in hash collections
• Should custom key objects be immutable ?If yes , then why?

Min Priority Queue and Max Priority Queue not sorting correctly

When you iterate over the elements of a PriorityQueue those elements are not completely ordered. The only thing you can be sure of is that a PriorityQueue will enforce that the smallest and biggest elements are the first elements of the min_pq and max_pq priority queues, respectively.

From the PriorityQueue javadocs:

The head of this queue is the least element with respect to the
specified ordering.

Based on that assumption you can print in order if you use the method poll():

while(!max_pq.isEmpty())
{
    System.out.println(max_pq.poll());
}

The poll method:

Retrieves and removes the head of this queue, or returns null if this
queue is empty.

For comparing Doubles you should use the method Double.compare(o1, o2). Moreover, you can simplify your comparators using lambda and method references, namely instead of :

PriorityQueue<Double> max_pq = new PriorityQueue<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if(o1<o2) return +1;
                if(o1.equals(o2)) return 0;
                return -1;
            }
        });

        PriorityQueue<Double> min_pq = new PriorityQueue<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if(o1>o2) return +1;
                if(o1.equals(o2)) return 0;
                return -1;
            }
        });

you can use the more elegant and simple:

PriorityQueue<Double> max_pq = new PriorityQueue<>(Double::compareTo);
PriorityQueue<Double> min_pq = new PriorityQueue<>((o1, o2) -> Double.compare(o2, o1));

Alternatively, instead of PriorityQueue, you could opt for a TreeSet, and there you can iterate over the elements in the order based on the comparator that you have chosen, without having to remove any element.

TreeSet<Double> max_pq = new TreeSet<>(Double::compareTo);

Another benefit of the TreeSet is that it comes with the method descendingSet(). Therefore, you do not need to keep two data structures to keep both the min and max order, instead you can have just:

  TreeSet<Double> max_pq = new TreeSet<>(Double::compareTo);
   
  max_pq.forEach(System.out::println);
  max_pq.descendingSet().forEach(System.out::println); 

PriorityQueue not sorting map by value

If you check out the PriorityQueue Docs you will see, that

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()).

But

The queue retrieval operations poll, remove, peek, and element access the element at the >head of the queue.

Thus, if you use poll, or some of the other methods, you should get the elements in order


In order to achive a descending order of the Integers, you would have to change the comparison from

return lhs.getValue().compareTo(rhs.getValue());

to

return rhs.getValue().compareTo(lhs.getValue());

since the first orders the numbers in natural order (from smallest to largest)

PriorityQueue did not order its content correctly?

A priority queue gives no guarantee with regard to the ordering of the complete set; all it guarantees is that the smallest element is at the front (or the largest, if it's a max priority queue).

From the docs:

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()).

Maybe to add a little context: what a priority queue does internally is store the elements in a tree structure of logarithmic height (in the sensible implementations using trees anyway). The insert and remove-like operations are designed to keep the smallest element at the root of that tree and to keep the elements in each subtree larger than the element of the parent vertex (that's what makes them heaps, that property is called the heap property). It does not guarantee any ordering on the elements of subtrees that are siblings as we know it for example from sort trees. The heap property together with the logarithmic height is what gives priority queues their fast operation runtimes, but it comes with the downside that you'll only ever get one element quickly, and that's the smallest one (or largest one for max heaps).

priority queue cannot sort automatically when its value has been changed

PriorityQueue and other collections working with comparable elements (e.g. TreeSet) are not meant for mutable objects. They only work if the ordering of the elements does not change (either because you don't change them in that way, or they are immutable and hence cannot be mutated at all).

So what you do, you shouldn't. But if you still do, PriorityQueue does not provide a way to redo the ordering.

Your 2 options:

• remove all elements and add them again
• create a new PriorityQueue, add all elements and use that

On a side note, your Comparator is not even correct, it should return 0 if 2 values are equal. Try using o1.k - o2.k or Integer.compare(o1.k, o2.k).

Why are elements in a PriorityQueue not printed in their natural ordering?

From the Javadocs:

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()).

This means that the elements are not necessarily stored in the queue in their natural ordering. So if you want to obtain the elements in their natural order, you have to sort separately or use the queue operations, e.g.,:

while( !q.isEmpty() ) {
    System.out.println(q.remove());
}

---

Related Topics