PriorityQueue.toString ordem do elemento errado

Eu estou tentando fazer uma fila de prioridade em java com os nós com a menor frequência em prioridade. No entanto, meu comparador não está funcionando e a saída é muito estranha. Acredito que preciso mudar meu comparador, mas não sei como alterá-lo. Aqui está o meu código:

public class HuffmanComparator implements Comparator { public int compare(TreeNodeHuffman p1, TreeNodeHuffman p2) { 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 queue = new PriorityQueue(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); } } 

A saída é a seguinte: [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]. No entanto, a saída deve ser [z, q, x, j, k, v, b ……..]. Desde já, obrigado!

Você precisa pesquisar os itens do PriorityQueue um por um. toString não faz isso.

Então, ao invés do seu System.out.println(queue); faça isso:

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

O motivo é que o PriorityQueue nunca é completamente classificado internamente, pesquise como um heap funciona para mais detalhes. Itens de busca a partir dele fixam o heap durante as chamadas, portanto, devem exibir os elementos na ordem de sorting.

O System.out.println(queue) está imprimindo a fila não classificada. Se você deseja imprimir a ordem real da fila, siga o código abaixo, que usa poll para obter os elementos da fila de cima para baixo:

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

e você verá esta saída como esperado:

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

Você quer uma freqüência menor para subir, então:

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

Se você quiser testá-lo, envie-o para um único conjunto de encadeamentos e veja a ordem dos trabalhos que estão sendo processados, em vez de a sequência ou o iterador. como o documento diz em http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#iterator%28%29 :

Retorna um iterador sobre os elementos nessa fila. O iterador não retorna os elementos em nenhuma ordem específica.

Pode ver http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Executors.html#newSingleThreadExecutor%28%29 para um único conjunto de threads rápido para testar isso.

@ Thomas responde a obras.

Mas esvaziar a fila apenas para imprimir a fila me deixou pouco à vontade. Então, em vez disso, criei um wrapper sobre o PriorityQueue e implementei next() e hasNext() para ele. Além disso, para simular exatamente o comportamento da fila de prioridade, extend AbstractQueue e delegue chamadas para methods como offer , peek , poll e size através do object PriorityQueue.

 priorityQueueObject.methodName() 

Disclaimer: Isso custa copiar toda a fila em uma lista e fazer a sorting sobre ela.

 public class MyPriorityQueue, T> extends AbstractQueue { Integer arrOfInts[] = { 11, 7, 15, 10, 2, 1, 4, 5, 7, 2, 18, 1, 19}; PriorityQueue pq = new PriorityQueue<>(); public static void main(String[] args) { MyPriorityQueue mpq = new MyPriorityQueue<>(); mpq.addAll(Arrays.asList(arrOfInts)); //Using iterator Iterator it = mpq.iterator(); System.out.println("The internal priority queue:" + mpq.pq); System.out.println("Using Iterator:"); while(it.hasNext()) { System.out.print(it.next() + ", "); } System.out.println("\nUsing simple system out println:"); System.out.println(mpq); System.out.println("Using foreach: "); for(Object o : mpq) { System.out.print(o + ", "); } } @Override public boolean offer(E arg0) { return pq.offer(arg0); } @Override public E peek() { return pq.peek(); } @Override public E poll() { return pq.poll(); } @Override public Iterator iterator() { ArrayList list = new ArrayList(Arrays.asList(pq.toArray())); Collections.sort(list, null); return new Iterator() { @Override public boolean hasNext() { return !list.isEmpty(); } @Override public E next() { assert (hasNext()); return list.remove(0); } }; } @Override public int size() { return pq.size(); } } 

impressões:

 The internal priority queue:[1, 2, 1, 7, 5, 2, 4, 11, 7, 10, 18, 15, 19] Using Iterator: 1, 1, 2, 2, 4, 5, 7, 7, 10, 11, 15, 18, 19, Using simple system out println: [1, 1, 2, 2, 4, 5, 7, 7, 10, 11, 15, 18, 19] Using foreach: 1, 1, 2, 2, 4, 5, 7, 7, 10, 11, 15, 18, 19,