L’iteratore integrato per PriorityQueue di java non attraversa la struttura dei dati in alcun ordine particolare. Perché?

Questo è direttamente dai documenti Java :

Questa class e il suo iteratore implementano tutti i metodi facoltativi delle interfacce Collection e Iterator. L’iteratore fornito nel metodo iteratore () non è garantito per attraversare gli elementi della coda di priorità in un ordine particolare. Se hai bisogno di attraversamenti ordinati, considera l’utilizzo di Arrays.sort (pq.toArray ()).

Quindi, in pratica, il mio PriorityQueue funziona bene, ma stamparlo sullo schermo usando il suo built-in toString () mi ha indotto a vedere questa anomalia in azione, e mi chiedevo se qualcuno potesse spiegare perché è l’iteratore fornito (e usato internamente) non attraversa il PriorityQueue nel suo ordine naturale?

Perché la struttura dati sottostante non lo supporta. Un heap binario è solo parzialmente ordinato, con l’elemento più piccolo nella radice. Quando lo rimuovi, l’heap viene riordinato in modo tale che l’elemento più piccolo successivo si trovi alla radice. Non esiste un algoritmo di traversal ordinato efficiente, quindi non viene fornito in Java.

I PriorityQueues sono implementati usando l’ heap binario. Un heap non è una struttura ordinata ed è parzialmente ordinato. Ad ogni elemento è associata una “priorità”. Utilizzando un heap per implementare una coda di priorità, avrà sempre l’elemento di massima priorità nel nodo radice dell’heap. quindi in una coda di priorità, un elemento con priorità alta viene servito prima di un elemento con priorità bassa. Se due elementi hanno la stessa priorità, vengono offerti in base al loro ordine nella coda. L’heap viene aggiornato dopo ogni rimozione di elementi per mantenere la proprietà heap

Bene, come dice Javadoc, è così che è stato implementato. La coda di priorità utilizza probabilmente un heap binario come struttura dati sottostante. Quando rimuovi gli elementi, l’heap viene riordinato per conservare la proprietà heap.

In secondo luogo, non è saggio bind un’implementazione specifica (forzare un ordine ordinato). Con l’attuale implementazione, sei libero di attraversarlo in qualsiasi ordine e utilizzare qualsiasi implementazione.

Gli heap binari sono un modo efficiente per implementare le code prioritarie. L’unica garanzia sull’ordine che un heap produce è che l’elemento in cima ha la priorità più alta (forse è il “più grande” o “il più piccolo” secondo un certo ordine). Un heap è un albero binario che ha le proprietà: Proprietà shape: l’albero si riempie da cima a fondo sinistra a destra Ordine prptyty: l’elemento in ogni nodo è più grande (o più piccolo se il più piccolo ha la priorità più alta) rispetto ai suoi due nodes figli. Quando l’iteratore visita tutti gli elementi probabilmente lo fa in un attraversamento di ordine di livello, cioè visita ogni nodo in ogni livello a sua volta prima di passare al livello successivo. Poiché l’unica garanzia sull’ordine che viene effettuata è che un nodo abbia una priorità più alta rispetto ai suoi figli, i nodes di ogni livello non saranno in ordine particolare.