jQuery in Action, 2nd edition*
The moose likes Beginning Java and the fly likes Using a comparator to sort a priority queue Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Using a comparator to sort a priority queue" Watch "Using a comparator to sort a priority queue" New topic
Author

Using a comparator to sort a priority queue

grace see
Greenhorn

Joined: Mar 31, 2013
Posts: 3
Hi! I am trying to implement a comparator to sort Integers in a priorityqueue. I've looked at many examples, but i cant think of why the following code doesnt sort integers in increasing/decreasing order.



the output is:
1
3
2
14
9
5
124
22
111
12
30

Is there something missing? Any help would be appreciated!
Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Welcome to the ranch Grace. Do you know what is a PriorityQueue? Do you know how it works? Read this first. I don't think you need a comparator at all to sort primitive types when you add them to a PriorityQueue. The implementation of the class is such that it should do it by itself for you. Read the description of the class carefully. The answer to why it is printing the stored integers randomly is given there.


~ Mansukh
grace see
Greenhorn

Joined: Mar 31, 2013
Posts: 3
Yup, I roughly know what a priority queue is. I suppose its just a normal queue with items sorted according to a specific priority. However, the implementation boggles me.

Basically my problem is like this: I have an Word object, that consists of an (int number) and a (double weight), i didnt put it in the code cos it might mix things up..

This Word object was what I wanted to sort with the priority queue, not the Integer object. The (int number) of the Word object is what i would like to use to sort these objects within the queue, and i thought i would need an comparator for this, since it isn't a primitive and Java might have trouble sorting it via its "natural order" (correct me if wrong). But i couldn't even get the basic case as illustrated in the code above correct. Hence I'd like to know why it may be not working.

The Word class looks something like this:

Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

Grace wrote: ....But i couldn't even get the basic case as illustrated in the code above correct. Hence I'd like to know why it may be not working.


So let us go step by step and not get ahead of ourselves. Why do you think it is printing the numbers in random order when the very definition of a PriorityQueue says that it sorts the elements according to their natural ordering or according to a comparator depending on the constructor being used. Did you read the whole description of the class in the link I provided? No. Hecn you missed this line:

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


Internally, the queue has actually stored the elements in their natural order. It just won't print them in that order unless you call the Arrays.sort(array []) method explicitly. This is baffling to me too. But it is how the class is designed.
grace see
Greenhorn

Joined: Mar 31, 2013
Posts: 3
Hmm... yeah i guess when I was reading it the dots didnt connect (Iterator=array?), and partly because i didnt think Arrays.sort would work on an object..

But anyway, thanks for the explanation! I realized after using poll(), that the queue is sorted afterall, just not when I converted it to an array... took me long enough >:\

Mansukhdeep Thind
Ranch Hand

Joined: Jul 27, 2010
Posts: 1157

... (Iterator=array?)


No. An iterator is not the same as an array. An iterator is simply a pointer that is used to traverse any collection of objects. The point is that when you traverse through the elements of a PriorityQueue, you may not see any sort order, although the queue sorts it internally. It's like you give me 10 cards with random numbers from 1 to 100. Now I know which is the largest and which is the smallest. I know the order. When you ask me for the largest, I shall give that card to you. But when you ask me to show you all the cards at once, I will simply show them to you in any random order. I have sorted them in my mind. That's how a PriorityQueue works.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Using a comparator to sort a priority queue