FULL PRODUCT VERSION :
1.6.0_05-b13
HotSpot Client VM

ADDITIONAL OS VERSION INFORMATION :
Windows XP SP3 (not OS specific though)

A DESCRIPTION OF THE PROBLEM :
When a PriorityQueue contains objects with mutable state that affect compareTo(), or when compareTo() uses time-sensitive data to produce its result, polling objects does not honour the natural ordering of the elements at the time of the pop() operation.

The queue heap invariant is established every time an element is inserted (that it, the elements are re-sorted to maintain the heap invariant). However, on poll() the head is always returned before re-sorting.

We came across this bug while trying to use DelayQueue (which internally uses a PriorityQueue) to implement a priority queue + delay behaviour.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run the attached executable test program.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
mutableF
mutableE
mutableD
mutableC
mutableB
mutableA

ACTUAL -
mutableA
mutableF
mutableE
mutableD
mutableC
mutableB


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.PriorityQueue;

public class Test {

	public static void main(String[] args) {

		Mutable mutableA = new Mutable("mutableA", 0);
		Mutable mutableB = new Mutable("mutableB", 1);
		Mutable mutableC = new Mutable("mutableC", 2);
		Mutable mutableD = new Mutable("mutableD", 3);
		Mutable mutableE = new Mutable("mutableE", 4);
		Mutable mutableF = new Mutable("mutableF", 5);

		PriorityQueue<Mutable> q = new PriorityQueue<Mutable>();
		q.add(mutableA);
		q.add(mutableB);
		q.add(mutableC);
		q.add(mutableD);
		q.add(mutableE);
		q.add(mutableF);

		// Mess with values
		mutableA.value = 600;
		mutableB.value = 500;
		mutableC.value = 400;
		mutableD.value = 300;
		mutableE.value = 200;
		mutableF.value = 100;

		System.out.println(q.poll());
		System.out.println(q.poll());
		System.out.println(q.poll());
		System.out.println(q.poll());
		System.out.println(q.poll());
		System.out.println(q.poll());
	}

	private static class Mutable implements Comparable<Mutable> {

		private final String name;
		private int value;

		private Mutable(String name, int value) {
			this.name = name;
			this.value = value;
		}

		public int compareTo(Mutable o) {
			Integer thisValue = this.value;
			Integer otherValue = o.value;
			return thisValue.compareTo(otherValue);
		}

		public String toString() {
			return name;
		}
	}
}

---------- END SOURCE ----------