¿Cómo iterar sobre 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 el Javadocs:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using 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, continuamente obtendrá el valor superior hasta que esté vacío. Supongo que verificó si estaba vacío después de su ciclo while, lo que le daría esta conclusión.

La única forma de hacerlo es ordenarlo usted mismo. se puede obtener el comparador original para de esta manera:

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

Answer 3

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 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 en forma ordenada. Por ejemplo, utilice java.util.TreeSet, y utilizar cualquiera pollFirst() o pollLast() en lugar de peek()/poll()

Answer 4

No se puede atravesar una cola de prioridad en ese orden, debido a la implementación subyacente (creo que es min en heap en Java). No es una matriz ordenada, por lo que puede pasar de un elemento a otro con menor prioridad. Leer a escondidas es un tiempo constante porque mira el elemento más pequeño. Para obtener el siguiente (en el tiempo O (log n)) debe dequeue el elemento más pequeño, así es como funciona. Dequeing no es solo una cuestión de sacar ese elemento, la estructura subyacente se reorganiza a sí misma para traer el elemento con la menor prioridad primero.

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

Sin embargo, si necesita recorrer los datos de esta manera, una cola de prioridad puede no ser la estructura de datos correcta para sus necesidades.

Answer 5

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

1) Creé una nuevaPriorityQueue. 2) Iterator usado para analizar cada elemento en oldQueue 3) método oldQueue.poll() utilizado para recuperar el elemento 4) inserte el elemento 3) en newPriorityQueue si no se utiliza.

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á vacio. @ Otros: - sugiera una forma mejor si puedo hacer lo mismo. No puedo usar el iterador ya que no devuelve elementos en el orden correcto.

Answer 6

Se puede hacer una copia de la cola y sondeo 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

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

Answer 8

Así que teniendo la PriorityQueue en una lista y luego la clasificación es una buena opción como se menciona arriba. Aquí hay algunos detalles de por qué el iterador proporciona resultados inesperados:

El iterador no devuelve elementos en el orden correcto porque se imprime desde la estructura de datos subyacente (similar a ArrayList). ArrayList tiene datos almacenados en él de la misma manera que los datos se almacenan en una implementación 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