Come si suppone che la coda di priorità Java funzioni?

Question

Breve storia, sto implementando un grafico e ora sto lavorando su Kruskal, ho bisogno di una coda di priorità. La mia definizione di una coda di priorità è che l'elemento con la chiave più piccola sarebbe il primo? È sbagliato? Perché quando inserisco i bordi ponderati (o numeri) nella coda non finiscono ordinati.

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); 

Questo dovrebbe stamparlo; [1, 54, 51, 102, 99, 55]. Questo non è ordinato come voglio che siano! E sì ho creato un comperatore che entra nella coda di priorità che estrae il numero dall'oggetto edge e lo confronta in base a quell'int. Quindi dovrebbe funzionare o ho semplicemente frainteso l'intero concetto di come funziona questa struttura dati?

Answer 1

System.out.println sta invocando il metodo toString(), che utilizza l'iteratore, che non garantisce il rispetto dell'ordine naturale. Da docs: "L'Iterator fornito nel metodo iteratore() non è garantito per attraversare gli elementi della coda di priorità in un ordine particolare."

Answer 2

Non ho esperienza con PriorityQueue in Java, ma sembra che la cosa priorità non è integrato in iterator() o toString() (che utilizza iterator()).

Se lo fai:

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

È possibile ottenere i risultati corretti.

Answer 3

Hai familiarità con il funzionamento degli heap binari? In caso contrario, passa attraverso le strutture min heap e max heap. PriorityQueue è implementato su heap. PriorityQueue non ordina gli elementi in ordine crescente, ma esegue l'ordinamento heap su di esso.

passare attraverso il link: Priority Queue

L'output che si ottiene è corretta.