Win a copy of Murach's MySQL this week in the JDBC and Relational Databases forum!
  • 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

What do you mean by natural ordering?

 
Ranch Hand
Posts: 924
1
Netbeans IDE Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I understand the difference between ordered collections and sorted collections. for sorted collections we have some sort of "sort order" based on rule/rules , defined by the properties of the object. and there is "natural ordering " e.g alphabetic order for strings etc". I was reading Collections from KB 6 and my question is relating to following lines

A PriorityQueue's elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a Comparator.



I want to know that does natural ordering means implementing comparable interface as opposed to comparator interface ? or in other words if a class implements comparable interface then does it mean that its natural order will be decided by implementation of compareTo() method? i hope you got my confusion what i want to say?
 
Saloon Keeper
Posts: 15433
361
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, when a class implements the Comparable interface, it's said to have a natural order.

Note that a PriorityQueue doesn't keep its elements ordered, by the way. The peek() and poll() methods just return elements in some order.
 
gurpeet singh
Ranch Hand
Posts: 924
1
Netbeans IDE Fedora Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


A PriorityQueue's elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a Comparator.



the above line is copied directly from java se 6 docs. Please refer the following http://docs.oracle.com/javase/6/docs/api/. then how can we say that PriorityQueue doesn't keep its elements ordered. i made a sample code and it did not maintained any order when iterating over the elements but i would like to know then why it is written about natural ordering in javadocs. kindly help

 
Stephan van Hulst
Saloon Keeper
Posts: 15433
361
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
They probably made a mistake while writing the documentation, because it implies that when you iterate over such a queue, it will return its elements in some well defined order. However, the documentation for the iterator() and toArray() methods clearly state that the class does not make any guarantees about the order of the elements they return.
 
Marshal
Posts: 28126
94
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Note that a PriorityQueue doesn't keep its elements ordered, by the way. The peek() and poll() methods just return elements in some order.



I don't think that's right. The API documentation says:

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.



So if you repeatedly call the poll() method, then you're going to get the elements in order. Whereas if you call the iterator() method and go through the resulting Iterator, you aren't.
 
Ranch Hand
Posts: 451
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Elements in priority queue is sorted by heap sort.
The elements are put in a binary tree structure. But it is not a binary search tree. The left child node may not be smaller than the right child node.
For more detail, google heap sort.

But one important notes for heap sort in ascending order is: the root is the smallest element, the next level contains bigger elements, the next next level contains elements that is bigger than the previous level and so on.
When a poll() is called, the root is retrieved and removed. The smallest element on the next level moves up to fill the vacant position in the root.
When a poll() is called again, the root is retrived and removed and so on.

 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic