How come the elements of priority queue are ordered according to natural order by default as it doesn't implement comparable interface?
From the documentation, it says elements are ordered based on natural ordering, but I can't find anywhere it talks about an equals method nor comparable. How is it happening internally?
All Implemented Interfaces: Serializable, Iterable, Collection, Queue.
If it implements comparable, then why doesn't it say in the above line?
Example:
public static void main(String[] args) {
PriorityQueue<String> pq = new PriorityQueue<String>();
pq.add("2");
pq.add("4");
System.out.println(pq); //prints [2, 4]
pq.offer("1");
System.out.println(pq); // prints [1, 4, 2]
pq.add("3");
System.out.println(pq); // prints [1, 3, 2, 4]
}
}
Also the third print statement prints [1, 3, 2, 4] instead of prints [1, 2, 3, 4]. Why? It should be natural ordering, right?
The actual internal data structure of PriorityQueue is not ordered. It is a heap.
PriorityQueue doesn't need to be ordered. Instead, it focuses on head of data. Insertion is in O(log n) time. Sorting wastes time and is useless for a queue.
Moreover, either the element is-a Comparable, or a Comparator is provided. Unfortunately, non-comparable checking is at runtime, rather than compile time. Once second element is added, ClassCastException occurs.
PLUS: My answer to why [1, 3, 2, 4] instead of prints [1, 2, 3, 4]?
As I mentioned before, it's not ordered. Instead it focuses on head q[0] is minimum; that's it.
You could see the [1, 3, 2, 4] as a tree which is not linear:
1
| \
3 2
|
4