Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Priority queue ordering of elements

Tags:

java

scjp

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?

like image 516
kittu Avatar asked May 06 '15 08:05

kittu


People also ask

In what order are elements in a priority queue removed or Dequeued?

Each element inserted in the Priority Queue has some priority. The element which has higher priority is dequeued first than the element having the low priority. If the two elements having the same priority, then the element which entered the priority queue first will get dequeued first.

Is priority queue FIFO or LIFO?

Typical stacks and queues are technically types of priority queues. The highest priority element in a stack is the most recently inserted one (LIFO), while the highest priority element in a queue is the least recently inserted one (FIFO).

How do I sort my priority queue?

There is an obvious way to do sorting with priority queues: Take the items that you want to sort, and insert them into the priority queue (using the item itself as its own priority). Then remove items from the priority queue until it is empty. The items will come off the queue in order from largest to smallest.

How do you get the first element in a priority queue?

PriorityQueue. peek() method in Java is used to retrieve or fetch the first element of the Queue or the element present at the head of the Queue. The element retrieved does not get deleted or removed from the Queue. Parameters: The method does not take any parameters.


2 Answers

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
like image 171
卢声远 Shengyuan Lu Avatar answered Sep 18 '22 09:09

卢声远 Shengyuan Lu


You are seeing that order because:

1. Internally System.out.println() will be invoking the toString() method which in turn uses the iterator to iterate through the elements of the queue. But the iterator does not guarantee any specific order to traverse the elements. Refer this

http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html


2. Priority queue is based on priority heap. When an element is inserted without any comparator then priority queue uses siftUpComparable() method internally. siftUpComparable() compares the current element with the element at it's parent position in the heap. If the order is not correct then current element and parent element are swapped. This is done until the current element and parent element are in correct order. Ordering is based on natural order of the element.

3. Since priority queue is based on priority heap its main focus will be on element in front of the queue. So the elements are ordered when an element is dequeued from the queue using poll(). This is done to increase the performance of Priority queue. Priority queue only orders the elements when it requires.
If you want to see the order as [1, 2, 3, 4] then use this

while(pq.size() != 0) { 
    System.out.println(pq.poll());
}
like image 36
Saathvik Avatar answered Sep 20 '22 09:09

Saathvik