• 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Liutauras Vilda
  • Bear Bibeault
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Piet Souris
  • salvin francis
  • Stephan van Hulst
Bartenders:
  • Frits Walraven
  • Carey Brown
  • Jj Roberts

Query: Priority Queue Natural ordering of strings

 
T Sukdeo
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dear Java Community

I kindly want to inquire, what natural ordering strings use when being printed from a priority queue. I am questioning alphabetical natural ordering because of the following example:



When 'queue1' uses the 'addAll' method on 'queue2'. The result that is printed (from Eclipse IDE) is:

[Blake, George, George, Jim, Kevin, Michael, John, Katie, Kevin, Michelle, Ryan]

but, when I was asked to manually work out the output of the code. I had the following as a result:

[Blake, George, George, Jim, John, Katie, Kevin, Kevin, Michael, Michelle, Ryan]

Additional Question:
----------------------

1) When deciding which name comes first between 'Jim' and 'John'. I used their second letter 'i' and 'o' to decide which came first, which is Jim. I kindly want to clarify if I used the correct method?


Any advice is much appreciated.
 
Stephan van Hulst
Saloon Keeper
Posts: 12493
269
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Printing all elements uses the collection's iterator, and PriorityQueue specifies that its iterator doesn't use any particular order.

If you want to get all elements from the queue in natural sorting order, you must call remove() or poll() repeatedly.
 
Saket Barve
Ranch Hand
Posts: 237
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

It is using the comparator implemented by String's class doing lexicographical comparison whose behavior is not changing.  

Instead of relying on the internal iterator extract the PQ's elements like so:


Or:  
 
Campbell Ritchie
Marshal
Posts: 71066
292
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

T Sukdeo wrote:. . . what natural ordering strings use when being printed from a priority queue. . . . .

We see this sort of question every now and again and I am starting to wonder whether Strings have natural orderings or not. If you look up String, you will find it implements Comparable<String>, and the compareTo() method will give you all the details. Then you try sorting some Strings and can' work out how “lexicographic” order works; it is simply that the smaller the Unicode value of each character (small c) decides that this String comes first. So 'i' < 'o' so John comes after Jim, But 'Z' < 'a' so the Zoo comes before its star animal: the aardaark. And what about natural languages? In English Aarenson comes really early in the alphabet, but when Mr Aarenson goes home to Scandinavia, he might move to after Z. There is a Comparator<String> available to sort out the capitalisation problem, and there are classes called Collators (I think) that deal with different orderings in different languages, but all that sort of thing makes me think there isn't one total ordering for Strings at all.
 
T Sukdeo
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The answer I got from my lecturer is that priority queue uses an underlying data structure called 'heap'. The names in the priority queue are printed from the root of the heap, the heap is then reorganized according to alphabetic ordering (according to how they are inserted). This method is done for all parents in the heap.

e.g) Blake (has 'B') which is lower than 'G' from George, so Blake will be the root.
 
Mike Simmons
Master Rancher
Posts: 3719
47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:We see this sort of question every now and again and I am starting to wonder whether Strings have natural orderings or not.
[...]
but all that sort of thing makes me think there isn't one total ordering for Strings at all.



Right, there is no single ordering for strings that makes sense for everyone, and Collators are probably the best way to get locale-specific orderings that make sense for various purposes.  However, the term natural ordering is defined in Java to mean the ordering determined by the compareTo() method, if implemented.  String implements Comparable and so has a compareTo() method, therefore it has a natural ordering, which is the ordering determined by that method.  Whether that order really makes sense or not, in various contexts, is another question.  But it is the natural ordering, by definition.
 
The airline is called "Virgin"? Don't you want a plane to go all the way? This tiny ad will go all the way:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic