PriorityQueue ordenados pero los dos más grandes [duplicados]

Nov 25 2020
public class Pair implements Comparable<Pair>{
    public String name;
    public int number;

    public int compareTo(Pair other) {
        if (other == null) {
            return 1;
        }
        return Integer.compare(number, other.number);
    }
}
ht = new Hashtable<String, Pair>(perLen);
PriorityQueue<Pair> pq = new PriorityQueue<Pair>(k);
set = ht.keySet();
for (String i: set) {
        tmp0 = ht.get(i);
        if (tmp0.compareTo(pq.peek()) > 0) {
            if (pq.size() == k) {
                pq.remove();
            }
            pq.add(tmp0);
        }
}
System.out.println(pq.toString());

SALIDA:

[OSCAR 822, ALBERTO 827, DAVID 1523, JAVIER 943]

Estoy buscando los k pares más grandes (su número) en la tabla hash y los de la salida son, de hecho, los correctos. Mi pregunta es, ¿por qué se intercambian los dos últimos?

Respuestas

2 fps Nov 25 2020 at 11:38

PriorityQueuesolo devuelve el elemento más bajo de su encabezado. No ordena todos los elementos, por lo que si atraviesa la cola con pq.toString(), es posible que los elementos no aparezcan en orden. Esto sucede porque, internamente, PriorityQueue.toString()usa el PriorityQueue.iterator()método y, según los documentos:

El iterador proporcionado en el método iterator()está no garantizado para atravesar los elementos de la cola de prioridad en cualquier orden particular. Si necesita un recorrido ordenado, considere usar Arrays.sort(pq.toArray()).

Si desea imprimir los elementos de la cola de prioridad en orden, debe cambiar este código:

System.out.println(pq.toString());

A lo siguiente:

while (!pq.isEmpty()) 
    System.out.println(pq.remove());
1 BrightSoul Nov 25 2020 at 11:32

El método toString () de la clase PriorityQueue no le garantiza el orden de los elementos, ya que utiliza un iterador.

Ashish Nov 25 2020 at 11:28

Puede verificar el pedido usando el método de encuesta como aquí:

Imprimir contenido de la cola de prioridad [java]