PriorityQueue.toString false element order

Question

Ich versuche eine Prioritätswarteschlange in Java mit den Knoten mit der niedrigsten Häufigkeit in der Priorität zu machen. Mein Komparator funktioniert jedoch nicht und die Ausgabe ist sehr seltsam. Ich glaube, ich muss meine Vergleichsperson ändern, aber ich bin mir nicht sicher, wie ich sie ändern soll. Hier ist mein Code:

public class HuffmanComparator implements Comparator<TreeNodeHuffman> { 
    public int compare(TreeNodeHuffman p1, TreeNodeHuffman p2) { 
     if (p1.frequency < p2.frequency) return -1; 
     if (p1.frequency > p2.frequency) return 1; 
     return 0; 
    }  
} 

public class TreeNodeHuffman { 
public static void main(String[] args) {  
    HuffmanComparator compare = new HuffmanComparator(); 
    TreeNodeHuffman e = new TreeNodeHuffman('e', 12702); 
    TreeNodeHuffman t = new TreeNodeHuffman('t', 9056); 
    TreeNodeHuffman a = new TreeNodeHuffman('a', 8167); 
    TreeNodeHuffman o = new TreeNodeHuffman('o', 7507); 
    TreeNodeHuffman i = new TreeNodeHuffman('i', 6966); 
    TreeNodeHuffman n = new TreeNodeHuffman('a', 6749); 
    TreeNodeHuffman s = new TreeNodeHuffman('s', 6327); 
    TreeNodeHuffman h = new TreeNodeHuffman('h', 6094); 
    TreeNodeHuffman r = new TreeNodeHuffman('r', 5987); 
    TreeNodeHuffman d = new TreeNodeHuffman('d', 4253); 
    TreeNodeHuffman l = new TreeNodeHuffman('l', 4025); 
    TreeNodeHuffman c = new TreeNodeHuffman('c', 2782); 
    TreeNodeHuffman u = new TreeNodeHuffman('u', 2758); 
    TreeNodeHuffman m = new TreeNodeHuffman('m', 2406); 
    TreeNodeHuffman w = new TreeNodeHuffman('w', 2360); 
    TreeNodeHuffman f = new TreeNodeHuffman('f', 2228); 
    TreeNodeHuffman g = new TreeNodeHuffman('g', 2015); 
    TreeNodeHuffman y = new TreeNodeHuffman('y', 1974); 
    TreeNodeHuffman p = new TreeNodeHuffman('p', 1929); 
    TreeNodeHuffman b = new TreeNodeHuffman('b', 1492); 
    TreeNodeHuffman v = new TreeNodeHuffman('v', 978); 
    TreeNodeHuffman k = new TreeNodeHuffman('k', 772); 
    TreeNodeHuffman j = new TreeNodeHuffman('j', 153); 
    TreeNodeHuffman x = new TreeNodeHuffman('x', 150); 
    TreeNodeHuffman q = new TreeNodeHuffman('q', 95); 
    TreeNodeHuffman z = new TreeNodeHuffman('z', 74); 
    PriorityQueue<TreeNodeHuffman> queue = new PriorityQueue<TreeNodeHuffman>(26, compare); 
    queue.add(e); 
    queue.add(t); 
    queue.add(a); 
    queue.add(o); 
    queue.add(i); 
    queue.add(n); 
    queue.add(s); 
    queue.add(h); 
    queue.add(r); 
    queue.add(d); 
    queue.add(l); 
    queue.add(c); 
    queue.add(u); 
    queue.add(m); 
    queue.add(w); 
    queue.add(f); 
    queue.add(g); 
    queue.add(y); 
    queue.add(p); 
    queue.add(b); 
    queue.add(v); 
    queue.add(k); 
    queue.add(j); 
    queue.add(x); 
    queue.add(q); 
    queue.add(z); 
    System.out.println(queue); 
} 
} 

Der Ausgang ist wie folgt: [z, k, q, g, v, x, u, d, f, y, b, m, j, i, c , e, s, o, w, a, r, h, p, t, l, a]. Die Ausgabe sollte jedoch [z, q, x, j, k, v, b .......] sein. Vielen Dank im Voraus!

Answer 1

Sie müssen die Elemente einzeln aus der PriorityQueue abfragen. toString macht das nicht.

Anstatt also Ihre System.out.println(queue); dies tun:

while(!queue.isEmpty()) { 
    System.out.println(queue.poll()); 
} 

Der Grund dafür ist, dass die PriorityQueue intern nie ganz sortiert, Lookup, wie ein Haufen für mehr Detail funktioniert. Beim Abrufen von Nachrichten wird der Heap während der Aufrufe fixiert. Daher sollten die Elemente in sortierter Reihenfolge ausgegeben werden.

Answer 2

Sie wollen niedrigere Frequenz höher geht so:

public int compare(TreeNodeHuffman p1, TreeNodeHuffman p2) { 
      if (p1.frequency < p2.frequency) return 1; 
      if (p1.frequency > p2.frequency) return -1; 
      return 0; 
     }  
    } 

Wenn Sie sie testen wollen, um es zu einem Single-Threaded-Pool senden und die Reihenfolge der Aufträge in Bearbeitung statt zu bespannen oder Iterator zu sehen. as doc sagt unter http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#iterator%28%29:

Gibt einen Iterator über die Elemente in dieser Warteschlange zurück. Der Iterator gibt die Elemente nicht in einer bestimmten Reihenfolge zurück.

Können Sie http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Executors.html#newSingleThreadExecutor%28%29 für einen schnellen Single-Thread-Pool, um dies zu testen.

Answer 3

Die System.out.println(queue) druckt die Warteschlange unsortiert. Wenn Sie die Warteschlange realen folgen, um den Code unten drucken möchten, die Umfrage verwenden Sie die Elemente aus der Warteschlange von oben nach unten zu bekommen:

TreeNodeHuffman tn = null; 
    do{ 
     tn = queue.poll(); 
     if(tn!=null){ 
      System.out.print(tn.key+","); 
     } 
    }while(tn != null); 

und Sie werden diese Ausgabe sehen, wie erwartet:

z , q, x, j, k, v, b, p, y, g, f, w, m, u, c, l, d, r, h, s, a, ich, o, a, t, e ,