El iterador incorporado para PriorityQueue de java no atraviesa la estructura de datos en ningún orden en particular. ¿Por qué?

Question

Esto es directamente de la Java Docs:

Esta clase y su iterador implementar todos los métodos opcionales de las interfaces Collection e Iterator. No se garantiza que el iterador proporcionado en el iterador de método() atraviese los elementos de la cola de prioridad en un orden en particular. Si necesita un recorrido ordenado, considere usar Arrays.sort (pq.toArray()).

Así que, básicamente, mi PriorityQueue funciona bien, pero que se puede imprimir a la pantalla usando su método propio construido en toString() me causó ver esta anomalía en la acción, y se preguntaba si alguien podría explicar por qué es que el iterador provisto (y utilizado internamente) no atraviesa el PriorityQueue en su orden natural?

Answer 1

Porque la estructura de datos subyacente no lo admite. Un montón binario está solo parcialmente ordenado, con el elemento más pequeño en la raíz. Cuando quitas eso, el montón se reordena para que el siguiente elemento más pequeño esté en la raíz. No existe un algoritmo transversal ordenado eficiente, por lo que no se proporciona ninguno en Java.

Answer 2

En primera instancia, es probable que atraviese los datos en el orden en que se almacenan. Para minimizar el tiempo de insertar un elemento en la cola, normalmente no almacena todos los elementos en orden ordenado.

Answer 3

Bueno, como dice el Javadoc, así es como se ha implementado. La cola de prioridad probablemente usa un montón binario como la estructura de datos subyacente. Cuando elimina elementos, el montón se reordena para conservar la propiedad de montón.

En segundo lugar, no es prudente vincular una implementación específica (forzando una orden ordenada). Con la implementación actual, puede recorrerla en cualquier orden y usar cualquier implementación.

Answer 4

Los montones binarios son una forma eficiente de implementar colas de prioridad. La única garantía sobre el orden que hace un montón es que el elemento en la parte superior tiene la prioridad más alta (tal vez sea el "más grande" o el "más pequeño" de acuerdo con algún orden). Un montón es un árbol binario que tiene las propiedades: Propiedad de forma: el árbol se llena de arriba a abajo de izquierda a derecha Propiedad de orden: el elemento en cualquier nodo es mayor (o menor si el más pequeño tiene la prioridad más alta) que sus dos Nodos de niños. Cuando el iterador visita todos los elementos, probablemente lo haga en un recorrido de nivel, es decir, visita cada nodo en cada nivel por turno antes de pasar al siguiente nivel. Como la única garantía sobre el orden que se hace es que un nodo tiene una prioridad mayor que sus hijos, los nodos en cada nivel no estarán en un orden particular.

Answer 5

PriorityQueues se implementan usando montón binario. Un montón no es una estructura ordenada y está parcialmente ordenada. Cada elemento tiene una "prioridad" asociada a él. Usando un montón para implementar una cola de prioridad, siempre tendrá el elemento de mayor prioridad en el nodo raíz del montón. por lo tanto, en una cola de prioridad, un elemento con alta prioridad se sirve antes que un elemento con baja prioridad. Si dos elementos tienen la misma prioridad, se sirven según su orden en la cola. El montón se actualiza después de cada eliminación de elementos para mantener la propiedad de montón