priority queue java example

¿Cómo iterar sobre un PriorityQueue?

Question

for (Event e : pq)

no itera en el orden de prioridad.

while(!pq.isEmpty()){
  Event e = pq.poll();
}

Esto funciona pero vacía la cola.

Answer 1

Desde los Javadocs :

No se garantiza que el iterador proporcionado en el método iterator() atraviese los elementos de PriorityQueue en ningún orden en particular. Si necesita un recorrido ordenado, considere usar Arrays.sort(pq.toArray()) .

Probablemente hay otros mecanismos equivalentes.

Answer 2

El método peek() no elimina nada de la cola, pero debido a esto, obtendrá continuamente el valor máximo hasta que esté vacío. Supongo que verificaste si estaba vacío después de tu bucle while, lo que te daría esta conclusión.

La única manera de hacer esto es ordenarlo usted mismo. Puedes obtener el comparador original de esta manera:

Event[] events = Arrays.sort(pq.toArray(), pq.comparator());
for (Event e : events) {
    // do stuff
}

Answer 3

Los carteles anteriores decían todo, pero nadie dio un ejemplo completo de trabajo (aparte de copiar pq), así que aquí está:

Event[] events = pq.toArray(new Event[pq.size()]);
Arrays.sort(events, pq.comparator());
for (Event e : events) {
    System.out.println(e);
}

Answer 4

No puede atravesar una cola de prioridad en ese orden debido a la implementación subyacente (creo que es min-heap en Java). No es una matriz ordenada, por lo que puede pasar de un elemento a uno con la menor prioridad. Mirar es un tiempo constante porque mira el elemento más pequeño. Para obtener el siguiente (en tiempo O (log n), debe sacar el elemento más pequeño de la cola, así es como funciona. La eliminación no es solo una cuestión de eliminar ese elemento, sino que la estructura subyacente se reorganiza para que el elemento tenga la menor prioridad en primer lugar.

Además, pasar por toda la cola de prioridad es una operación O (n log (n)). Por lo tanto, también puede tomar todos los elementos de la cola y ordenarlos (también O (n log (n))) y luego puede revisarlos como desee. La única desventaja es que tienes una copia extra de la cola.

No obstante, si necesita atravesar los datos de esta manera, una cola de prioridad puede no ser la estructura de datos adecuada para sus necesidades.

Answer 5

Por lo tanto, tomar la prioridadQueue en una lista y luego ordenarla es una buena opción como se mencionó anteriormente. Aquí hay algunos detalles de por qué el iterador da resultados inesperados:

El iterador no devuelve elementos en el orden correcto porque se imprime desde la estructura de datos subyacente (similar a ArrayList). El ArrayList tiene datos almacenados en él de la misma manera que los datos se almacenan en una implementación de Array de BinaryHeap. Por ejemplo:

PriorityQueue<Integer> pq = new PriorityQueue<>();
ArrayList<Integer> test = new ArrayList(Arrays.asList(6,12,7,9,2));
test.forEach(x -> pq.add(x)); 
System.out.println("Priority Queue:- "+pq); [2, 6, 7, 12, 9]

donde childOf (i) es 2 * i + 1 y 2 * i + 2 y parentOf (i) es (i-1) / 2

Answer 6

Puede hacer una copia de la cola y sondear en un bucle, en este ejemplo pq es la cola de prioridad original:

PriorityQueue<Your_class> pqCopy = new PriorityQueue<Your_class>(pq);
while(!pqCopy.isEmpty()){
    Your_Class obj = pqCopy.poll();
    // obj is the next ordered item in the queue
    .....
}

Answer 7

Recientemente, tuve el mismo problema. Quería usar algún objeto en particular de la cola de prioridad y luego mantener los elementos restantes conservados.

1) He creado un nuevoPriorityQueue. 2) Usé el iterador para analizar cada elemento en oldQueue 3) usé el método oldQueue.poll () para recuperar el elemento 4) inserte el elemento 3) en newPriorityQueue si no se usa.

 Queue<String> newQueue = new PriorityQueue<String>(); 
    // Assuming that oldQueue have some data in it.

    Iterator<String> itr = oldQueue.iterator();
    while(itr.hasNext()){
        String str = oldQueue.poll();
        // do some processing with str
        if(strNotUsed){
            newQueue.offer(str);
        }
    }

Al final, oldQueue estará vacío. @ Otros: - Por favor sugiera una mejor manera si puedo hacer lo mismo. No puedo usar el iterador ya que no devuelve elementos en el orden correcto.

Answer 8

Una cola de prioridad basada en el montón solo garantiza que el primer elemento sea el más alto / más bajo. No hay una forma barata (es decir, O (n)) de obtener los elementos en forma ordenada.

Si necesita hacer esto a menudo, considere usar una estructura que mantenga los elementos ordenados. Por ejemplo, use java.util.TreeSet y use pollFirst() o pollLast() en lugar de peek() / poll()

Answer 9

for (Event event: pq.toArray(new Event[pq.size()])) {
    event.toString();
}