PriorityQueue.toString order element

Question

Sto tentando di creare una coda di priorità in java con i nodi con la frequenza più bassa in priorità. Tuttavia, il mio comparatore non funziona e l'output è molto strano. Credo di aver bisogno di cambiare il mio comparatore, ma non sono sicuro di come cambiarlo. Ecco mio codice:

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); 
} 
} 

L'uscita è il seguente: [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]. Tuttavia, l'output dovrebbe essere [z, q, x, j, k, v, b ........]. Grazie in anticipo!

Answer 1

È necessario eseguire il polling degli articoli da PriorityQueue uno per uno. toString non lo fa.

Così, invece della vostra System.out.println(queue); fare questo:

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

La ragione è che il PriorityQueue non è mai completamente risolto internamente, di ricerca come funziona un mucchio per maggiori dettagli. Gli elementi di polling da esso risolvono l'heap durante le chiamate, pertanto dovrebbe generare gli elementi in ordine ordinato.

Answer 2

Si desidera frequenza più bassa di andare così in alto:

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

Se volete provarlo, inviarlo a un unico pool filettato e vedere la sequenza dei lavori in fase di elaborazione al posto di stringa o di iteratore. come dice il documento allo http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#iterator%28%29:

Restituisce un iteratore sugli elementi di questa coda. L'iteratore non restituisce gli elementi in alcun ordine particolare.

Può vedere http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Executors.html#newSingleThreadExecutor%28%29 per un rapido pool a thread singolo per verificarlo.

Answer 3

Il System.out.println(queue) sta stampando la coda non ordinata. Se si desidera stampare il vero ordine coda di seguire il codice qui sotto che utilizzano sondaggio per ottenere gli elementi dalla parte superiore della coda verso il basso:

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

e si vedrà questa uscita come previsto:

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