java - PriorityQueue.toString orden de elementos incorrecto

sorting printing

Question

Estoy tratando de hacer una cola prioritaria en Java con los nodos con la frecuencia más baja en prioridad. Sin embargo, mi comparador no funciona y el resultado es muy extraño. Creo que necesito cambiar mi comparador, pero no estoy seguro de cómo cambiarlo. Aquí está mi código:

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

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!

Answer 1

Debe 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 ordenado internamente, consulte cómo funciona un montón para obtener más detalles. El sondeo de elementos desde él corrige el montón durante las llamadas, por lo tanto, debería mostrar los elementos en orden ordenado.

Answer 2

Desea que la frecuencia más baja aumente, entonces:

  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 único grupo de subprocesos y vea el orden de los trabajos que se procesan en lugar de en cadena o iterador. como dice el documento 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 ningún orden en particular.

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

Answer 3

La respuesta de @Thomas funciona.

Mi enfoque es producir el mismo resultado sin vaciar realmente la cola . Entonces, en su lugar, creé un contenedor sobre PriorityQueue e implementé next() y hasNext() para ello. Además, para simular exactamente el comportamiento de la cola 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 ordenarla por encima.

public class MyPriorityQueue<E extends Comparable<T>, T> extends AbstractQueue<E> {
    Integer arrOfInts[] = { 11, 7, 15, 10, 2, 1, 4, 5, 7, 2, 18, 1, 19};
    PriorityQueue<E> 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<E> iterator() {
        ArrayList<E> list = new ArrayList(Arrays.asList(pq.toArray()));
        Collections.sort(list, null);
        return new Iterator<E>() {
            @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, 

Answer 4

System.out.println(queue) está imprimiendo la cola sin clasificar. Si desea imprimir el orden real de la cola, siga el siguiente código que utiliza sondeo 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,