Datentypen PriorityQueue sortiert falsch?

[_dp]

Hi

Ich möchte mir eine PriorityQueue erstellen, die ich mit elementen fülle und die mir dann mittels eigenem Comparator die Elemente in Aufsteigender Reihenfolge eines bestimmten Attributs zurückgibt.

Leider hab ich damit Probleme, ich bin mir zwar sicher alles richtig gemacht zu haben, dennoch stimmt die Anordnung der Testelemente nicht.

Hier die Testklasse:

public class HuffmanTreeTests {

	static HuffmanTree<String> uut;
	
	@Before
	public void setUp() throws Exception {
		uut = new HuffmanTree<String>();
	}

	@Test
	public void testCreateQueue() {
		uut.add("888", 12);
		uut.add("112", 2);
		uut.add("111", 1);
		uut.add("434", 4);
		
		Collection<HuffmanTreeNode<String>> queue = uut.getQueue();
		System.out.println("====== Dumping priority queue");
		for (HuffmanTreeNode<String> s : queue) {
			System.out.println(s.getPayload());
		}
		System.out.println("====== Dump end");
		
	}

}

Konsolenoutput:

Comparing 2 vs. 12, returning -1
Comparing 1 vs. 2, returning -1
Comparing 4 vs. 12, returning -1
Comparing 4 vs. 1, returning 1
====== Dumping priority queue
111
434
112
888
====== Dump end

Tree Klasse, die die PriorityQueue erzeugt und befüllt, außerdem dem Comparator bereitstellt:

public class HuffmanTree<E> {
	
	HuffmanTreeNode<E> root;
	
	HuffmanTreeNode<E> current;
	
	PriorityBlockingQueue<HuffmanTreeNode<E>> queue;
	
	public HuffmanTree() {
		queue = new PriorityBlockingQueue<HuffmanTreeNode<E>>(43, new Comparator<HuffmanTreeNode<?>>() {
			@Override
			public int compare(HuffmanTreeNode<?> o1, HuffmanTreeNode<?> o2) {
				int ret;
				if (o1.getWeight() == o2.getWeight()) ret = 0;
				if (o1.getWeight() > o2.getWeight()) ret = 1;
				else ret = -1;
				System.out.println("Comparing "+o1.getWeight()+" vs. "+o2.getWeight()+", returning "+ret);
				return ret;
			}
		});
	}
	
	public void add(E payload, Integer weight) {
		HuffmanTreeNode<E> node = new HuffmanTreeNode<E>(payload, weight);
		queue.add(node);
	}
	
	public PriorityBlockingQueue<HuffmanTreeNode<E>> getQueue() {
		return queue;
	}
}

Hier noch die Node Klasse:

public class HuffmanTreeNode<E> {

	private E payload;
	
	private int weight;
	
	private HuffmanTreeNode<E> left;
	
	private HuffmanTreeNode<E> right;

	private HuffmanTreeNode<E> parent;

	public HuffmanTreeNode(E payload, int weight) {
		this.payload = payload;
		this.weight = weight;
	}

	public int getWeight() {
		return weight;
	}
}

Wenn ich nicht komplett daneben liege, sollte der Konsolenoutput doch so aussehen:

111
112
434
888

Und ich meine auch, dass das 3. einzufügende Element nicht nur gegen das 2. sondern auch das 1. Testelement verglichen werden sollte, oder?

Die PriorityBlockingQueue war vorher auch mal eine normale PriorityQueue, aber das gab mir kein positiveres Ergebnis leider.

Wo ist der Fehler?

 

[SlaterB]

die Queue hat nicht zu jedem Zeitpunkt eine vollständige Sortierung, sondern legt besonders darauf wert, dass das erste Element richtig ist,
alle werden übrigens in Baumdarstellung gespeichert

111
112
434
888
bedeutet dass 111 die Wurzel ist, 112 der linke Nachfolger mit unten noch 888 dran, 434 der rechte Nachfolger,

der normale Iterator geht das Array dieser Baumdarstellung ab, sorgt sich nicht um Reihenfolge

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

PriorityQueue (Java 2 Platform SE 5.0)

wenn du 4x poll() aufrufst, dann kommen die Elemente in richtiger Reihenfolge und dann gibts auch weitere Compare-Aufrufe

noch ein Link:
Descending Priority Heap (2008)

 

[Marco13]

Ansonsten, mal drübergeschaut:

if (o1.getWeight() == o2.getWeight()) ret = 0;
if (o1.getWeight() > o2.getWeight()) ret = 1;
else ret = -1;

Ich weiß nicht genau, wann da was womit verglichen wird, aber überleg' mal genau, welchen Wert 'ret' dort bekommt, wenn das erste Gewicht NICHT größer als das zweite (sondern NUR gleich!!!) ist...

 

[Landei]

-- redundater Beitrag war wegen Redundanz redundant --

 

[_dp]

die Queue hat nicht zu jedem Zeitpunkt eine vollständige Sortierung, sondern legt besonders darauf wert, dass das erste Element richtig ist,

Danke, dieses Detail war mir nicht bekannt.

Ansonsten, mal drübergeschaut:

if (o1.getWeight() == o2.getWeight()) ret = 0;
if (o1.getWeight() > o2.getWeight()) ret = 1;
else ret = -1;

Ich weiß nicht genau, wann da was womit verglichen wird, aber überleg' mal genau, welchen Wert 'ret' dort bekommt, wenn das erste Gewicht NICHT größer als das zweite (sondern NUR gleich!!!) ist...

Danke für den Hinweis, hab ich so garnicht bemerkt.
Vorher waren dort "return" statements statt der zwischenvariable, bevor ich dann die Debug Ausgabe hinzugefügt hatte. das >= kommt aber im Grunde aufs Selbe hinaus da in meinem Falle eh kein Key doppelt vor kommt. Danke trotzdem!

 

[Crian]

Wenn du aus dem > ein >= machst, wirst du nie eine 0 als Ergebnis bekommen. Wie wäre es mit [c]return o1.getWeight() - o2.getWeight();[/c] ?

 

[Marco13]

das >= kommt aber im Grunde aufs Selbe hinaus da in meinem Falle eh kein Key doppelt vor kommt. Danke trotzdem!

Dass kein Key doppelt vorkommt heißt (bei einer Priority Queue vielleicht(!) schon, aber evtl. auch nicht, und ) im allgemeinen sicher nicht, dass nicht mal ein Key mit sich selbst verglichen wird - und dann sollte er definitv NICHT sagen, dass er "größer ist als er selbst"!

Der Vorschlag von Crian löst das Problem. (Ich hatte irgendwie gedacht die "weights" wären double, da geht das nicht, aber bei int kann man das so machen)