Forum Stats

  • 3,837,899 Users
  • 2,262,306 Discussions
  • 7,900,429 Comments

Discussions

Behaviour of PriorityQueue using Java 6

652295
652295 Member Posts: 6
Hi,

I have a below code to test PriorityQueue ordering of elements using it's natural order.

Output of SOP1 is clear to me.

I was expecting
SOP2 as : [a, b, d]
SOP3 as : [a, b, c, d]

import java.util.*;
class PQTest {
public static void main(String... args) {
PriorityQueue<String> pq = new PriorityQueue<String>();

pq.add("b");
pq.add("d");
System.out.println(pq); //SOP1 output [b, d]

pq.add("a");
System.out.println(pq); //SOP2 output [a, d, b]

pq.add("c");
System.out.println(pq); //SOP3 output [a, c, b, d]
}
}

Could somebody shed the light?
Appreciate your help.

Best Answer

  • sabre150
    sabre150 Member Posts: 1,405
    edited Nov 5, 2011 7:53PM Answer ✓
    The toString() method of a PriorityQueue in no way reflect the order of the elements in the queue. Since the PriorityQueue is based on a 'heap' ( see http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html and http://www.cs.auckland.ac.nz/software/AlgAnim/heaps.html ) the order you see in the toString() is probably the physical order of the elements in the array used to back the 'heap' which is not the logical queue order.

Answers

  • sabre150
    sabre150 Member Posts: 1,405
    edited Nov 5, 2011 7:53PM Answer ✓
    The toString() method of a PriorityQueue in no way reflect the order of the elements in the queue. Since the PriorityQueue is based on a 'heap' ( see http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html and http://www.cs.auckland.ac.nz/software/AlgAnim/heaps.html ) the order you see in the toString() is probably the physical order of the elements in the array used to back the 'heap' which is not the logical queue order.
  • EJP
    EJP Member Posts: 32,920 Gold Crown
    Check the Javadoc. PrioriyQueue only exhibits ordering when you remove fom it.
    EJP
This discussion has been closed.