Trouble with Sorting Algorithm of PriorityQueue(Java): Why is ordering different than a sorted ArrayList?

Question

I was working on the Huffman. But I found the sorting algorithm of PriorityQueue problematic; it does not make enough compares! Then I just wrote a simple class to test the Collections's sorting and PriorityQueue's sorting:

public class Student implements Comparable<Student>{

    String name;
    int score;
    int math;

    public Student(int score, int math, String name) {
       this.name = name;
       this.score = score;
       this.math = math;
    }

    public int compareTo(Student other) {
       if (this.score > other.score) {
           return -1;
       } else if (this.score < other.score) {
           return 1;
       } else {
           if (this.math > other.math) {
               return -1;
           } else {
               return 1;
           }
       }

       return 0;
   }

   public String toString() {
       return("[" + name + " has Score: " + score + "(Math: " + math + ")]");
   }
}

But I got the result like this(on the console):

Priority Queue::::::::::
[Jeremy Lin has Score: 2350(Math: 800)]
[Qian has Score: 2150(Math: 800)]
[PoorMath has Score: 2060(Math: 600)]
[Hui has Score: 1800(Math: 690)]
[Kaiyu has Score: 2060(Math: 800)]
[Chao has Score: 0(Math: 0)]

ArrayList sorted::::::::
[Jeremy Lin has Score: 2350(Math: 800)]
[Qian has Score: 2150(Math: 800)]
[Kaiyu has Score: 2060(Math: 800)]
[PoorMath has Score: 2060(Math: 600)]
[Hui has Score: 1800(Math: 690)]
[Chao has Score: 0(Math: 0)]

How to explain this? It's so wierd!

Thank you so much!!

Provide your testing method. My guess is that you are iterating the PriorityQueue, which does not guarantee iterating in any particular order: This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. 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()). (from http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html) — ahawtho, Jan 03 '14 at 19:04
I tried this, and I got the results to show up in order by using the `poll` method, which removes the "least" element from the queue and returns it. — ajb, Jan 03 '14 at 19:05

score 6 · Accepted Answer · answered Jan 03 '14 at 19:03

6

I think you may have a slight misunderstanding of how a priority queue works...

A PriorityQueue structure doesn't guarantee that the entire structure is sorted in any particular order. It only guarantees that the next element you pop off the top of it will be the highest priority item. If you look at the API for the PriorityQueue, it doesn't allow random access to any element in the PriorityQueue, it only allows access to the next element (much like a Stack or Queue structure).

An ArrayList, on the other hand, is a data structure that allows random access, and so when you sort it, all of the internal elements are in order.

So in your example, the structures are both correct because they both show Jeremy Lin as the first entry.

If you did something like this with your PriorityQueue, you should see the same ordering as the sorted ArrayList:

PriorityQueue<Student> pq;

//initialize PriorityQueue

while(pq.size() > 0)
{
   System.out.println(pq.poll());
}

I believe Java's PriorityQueue is based on a standard Heap data structure. You can find some basic details here: http://en.wikipedia.org/wiki/Heap_(data_structure)

answered Jan 03 '14 at 19:03

Brent Writes Code

19,075
7
52
56

_"A PriorityQueue structure doesn't guarantee that the entire structure is sorted in any particular order"_. Well they are ordered by priority. To quote the doc : _"The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time"_. This is a heap after all. – user2336315 Jan 03 '14 at 19:06
1

@user2336315 They're not sorted by priority in how they're stored internally. A priority queue is based on a min heap and there are a number of different ways to lay out elements in a min heap that will still exhibit proper priority queue behavior. There is no one correct ordering of elements. All that's guaranteed is that all the elements obey the `Min Heap Property` which is that each element in the Heap (which can be visualized as a nearly complete binary tree) is smaller than both its children. There are a number of different ordering for the PriorityQueue shown above that still work. – Brent Writes Code Jan 03 '14 at 19:07
@user2336315 You still have to use the right method to get at the ordering. The doc explicitly says that an iterator won't do this. – ajb Jan 03 '14 at 19:07
@BrentNash Thanks I got your point :). Sorry, now I remember. Could you find where it's mentionned that it's based on a min heap ? If you use a priority queue to store integers per example, with a reverse comparator (i.e reverse natural ordering), wouldn't it be a max heap ? – user2336315 Jan 03 '14 at 19:09
@BrentNash One minor nit - since heaps allow duplicates, the heap property is that the root of a subtree is less than or equal to the minimum value in the subtree, not just strictly smaller. Great explanation of the non-uniqueness of valid heaps, though! – pjs Jan 03 '14 at 19:13
@user2336315 Heaps can be either min- or max-based, depending on how you define the comparator. – pjs Jan 03 '14 at 19:17
@pjs Yes, but @ BrentNash said that _"A priority queue is based on a min heap"_ So I should assume that he said _"A priority queue is based on a min heap if you don't provide explictly a custom comparator when you create your queue"_ ? – user2336315 Jan 03 '14 at 19:19
@user2336315 When in doubt, check the [javadocs](http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html). Officially it's a "priority heap" using either the "natural ordering" or one based on a `Comparator` specified in the constructor. It goes on to say "The head of this queue is the least element with respect to the specified ordering", so looks like @BrentNash got it right. – pjs Jan 03 '14 at 19:25
@pjs Ok, yes a min heap according to ordering. So for 1,2,3 with a reverse natural order, 3 will be considered like the minimum and it'll be at the root of the min heap. Thanks :) – user2336315 Jan 03 '14 at 19:28

score 1 · Answer 2 · answered Jan 03 '14 at 19:03

PriorityQueue is not a sorted collection, it is a collection that efficiently maintains the "lowest" element. From the javadoc:

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

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

Trouble with Sorting Algorithm of PriorityQueue(Java): Why is ordering different than a sorted ArrayList?

2 Answers2