PriorityQueue.toString orden de elemento incorrecto

Estoy tratando de hacer una cola de prioridad en Java con los nodos con la frecuencia más baja en prioridad. Sin embargo, mi comparador no funciona y la salida es muy extraña. Creo que necesito cambiar mi comparador, pero no estoy seguro de cómo cambiarlo. Aquí está mi 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); } } 

La salida es la siguiente: [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]. Sin embargo, la salida debe ser [z, q, x, j, k, v, b ……..]. ¡Gracias por adelantado!

Necesita sondear los elementos de PriorityQueue uno por uno. toString no hace eso.

Entonces, en lugar de su System.out.println(queue); hacer esto:

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

La razón es que PriorityQueue nunca está completamente ordenada internamente, busca cómo funciona un montón para obtener más detalles. Los elementos de sondeo de él corrigen el montón durante las llamadas, por lo tanto, debe mostrar los elementos en orden ordenado.

System.out.println(queue) está imprimiendo la cola sin clasificar. Si desea imprimir el orden real de la cola, siga el código a continuación que utiliza la encuesta para obtener los elementos de la cola de arriba a abajo:

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

y verá esta salida como se esperaba:

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, mi,

Desea que la frecuencia más baja sea más alta, así que:

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

Si desea probarlo, envíelo a un solo grupo de subprocesos y vea el orden de los trabajos que se procesan en lugar de cadena o iterador. como dice el doc en http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#iterator%28%29 :

Devuelve un iterador sobre los elementos en esta cola. El iterador no devuelve los elementos en un orden particular.

Puede ver http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Executors.html#newSingleThreadExecutor%28%29 para obtener un grupo de un solo subproceso rápido para probar esto.

@Thomas responde trabajos.

Pero, vaciar la cola por solo imprimir la cola me hizo sentir incómodo. Entonces, en su lugar, creé un contenedor sobre PriorityQueue , e implementé next() y hasNext() para él. Además, para simular exactamente el comportamiento de colas de prioridad, extend AbstractQueue y delegue llamadas a métodos como offer , peek , poll y size través del objeto PriorityQueue.

 priorityQueueObject.methodName() 

Descargo de responsabilidad: Esto cuesta copiar toda la cola en una lista y hacer la clasificación sobre ella.

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

huellas dactilares:

 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, 
    Intereting Posts