• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Using a comparator to sort a priority queue

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
Ranch Hand
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
grace see
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1164
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

... (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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic