¿Cómo se supone que funciona la cola de prioridad de Java?

Breve historia, estoy implementando un gráfico y ahora estoy trabajando en el Kruskal, necesito una cola de prioridad. Mi definición de una cola de prioridad es que el elemento con la clave más pequeña vendría primero? ¿Esto esta mal? Porque cuando inserto los bordes pesados (o números) en la cola, no terminan ordenados.¿Cómo se supone que funciona la cola de prioridad de Java?

PriorityQueue<Integer> tja = new PriorityQueue<Integer>(); 
tja.add(55); 
tja.add(99); 
tja.add(1); 
tja.add(102); 
tja.add(54); 
tja.add(51); 
System.out.println(tja);

Eso imprimiría esto; [1, 54, 51, 102, 99, 55]. ¡Esto no está ordenado como quiero que lo sean! Y sí, formulé un compevor que entra en la cola de prioridad que extrae el número del objeto de borde y lo compara en función de ese int. Entonces, ¿debería funcionar o simplemente he entendido mal el concepto completo de cómo funciona esta estructura de datos?

Fuente

2009-11-25 Algific

para obtener el diseño ordenado debe usar 'while (! Tja.isEmpty()) { System.out.println (tja.poll()); } ' – serhii

System.out.println invoca el método toString(), que utiliza el iterador, que no se garantiza que respete el orden natural. Del docs: "No se garantiza que el iterador provisto en el iterador de método() atraviese los elementos de la cola de prioridad en un orden en particular".

Fuente

2009-11-25 09:02:19 omerkudat

Entonces, ¿hay alguna posibilidad de imprimir la cola de prioridad? –

No importa, no hay forma de hacerlo ... Actualizaré la respuesta si me lo permite. –

que no tienen experiencia con PriorityQueue en Java, pero parece que la cosa prioridad no está integrado en iterator() o toString() (que utiliza iterator()).

Si lo hace:

while (tja.size()>0) 
     System.out.println(tja.remove());

obtener los resultados adecuados.

Fuente

2009-11-25 09:00:46

Perfecto, por lo que la estructura no está ordenada correctamente hasta que ejecute eliminar. – Algific

No, la estructura siempre se ordena correctamente, pero no cuando se itera sobre ella. Pero si llama a poll(), o peek(), o remove(), obtiene los elementos en el orden correcto. – omerkudat

@data_hepp No. Remove no ordena la estructura. La estructura ya está ordenada, pero toString() o iterator() que utiliza internamente no garantiza el recorrido en orden. – Varun

¿Está familiarizado con el funcionamiento de los montones binarios? Si no, ve a través de las estructuras de montón mínimo y montón máximo. PriorityQueue se implementa en montones. PriorityQueue no ordena los elementos en orden creciente, pero sí lo ordena en forma de montón.

Ir a través del enlace: Priority Queue

La salida que se obtiene es correcta.

Fuente

2015-03-18 11:30:03

¿Cómo se supone que funciona la cola de prioridad de Java?

Respuesta

Cuestiones relacionadas