How come the elements of priority queue are ordered according to natural order by default as it doesn't implement comparable interface.
From the docs, it says elements are ordered based on natural ordering but I can't find anywhere it talks about equals method nor comparable. Hows 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 third print statement prints [1, 3, 2, 4] instead of prints [1, 2, 3, 4]. Why? It should be natural ordering right?
Answer
Actually 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 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