PriorityQueue.toString ordem do elemento errado

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,