Comment la file d'attente de priorité Java est-elle supposée fonctionner?

Petite histoire, j'implémente un graphique et maintenant je travaille sur le Kruskal, j'ai besoin d'une file d'attente prioritaire. Ma définition d'une file d'attente prioritaire est que l'élément avec la plus petite clé viendrait en premier? Est-ce mal? Parce que quand j'insère les bords pondérés (ou nombres) dans la file d'attente ils ne finissent pas triés.Comment la file d'attente de priorité Java est-elle supposée fonctionner?

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

Cela imprimerait cela; [1, 54, 51, 102, 99, 55]. Ce n'est pas trié comme je le veux! Et oui j'ai fait un comperator qui va dans la file d'attente prioritaire qui extrait le nombre de l'objet de bord et compare basé sur ce int. Donc cela devrait fonctionner, ou est-ce que j'ai complètement mal compris tout le concept de fonctionnement de cette structure de données?

Source

2009-11-25 Algific

Pour obtenir une disposition triée, vous devez utiliser 'while (! Tja.isEmpty()) { System.out.println (tja.poll()); } ' – serhii

System.out.println appelle la méthode toString(), qui utilise l'itérateur, dont le respect de l'ordre naturel n'est pas garanti. De la docs: "L'Iterator fourni dans la méthode iterator() n'est pas garanti de parcourir les éléments de la file d'attente prioritaire dans un ordre particulier."

Source

2009-11-25 09:02:19 omerkudat

Alors, est-il possible d'imprimer la file d'attente prioritaire? –

Peu importe, il n'y a aucun moyen de le faire ... Je vais mettre à jour la réponse si vous me laissez. –

Je n'ai aucune expérience avec PriorityQueue en Java, mais il semble que la chose prioritaire ne soit pas intégrée dans iterator() ou toString() (qui utilise iterator()).

Si vous faites:

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

Vous obtenez les résultats appropriés.

Source

2009-11-25 09:00:46

Parfait, donc la structure n'est pas triée correctement jusqu'à ce que vous exécutiez supprimer. – Algific

Non, la structure est toujours triée correctement, mais pas quand vous itérez dessus. Mais si vous appelez poll(), peek() ou remove(), vous obtenez les éléments dans le bon ordre. – omerkudat

@data_hepp Non. Supprimer ne permet pas de trier la structure. La structure est déjà triée, mais toString() ou iterator() qu'elle utilise en interne ne garantit pas la traversée dans l'ordre. – Varun

Êtes-vous familier avec le fonctionnement des tas binaires? Sinon, passez par les structures de tas minimum et de tas maximum. PriorityQueue est implémenté sur des tas. PriorityQueue ne triera pas les éléments dans l'ordre croissant, mais il effectuera le tri des segments.

Aller via le lien: Priority Queue

La sortie que vous obtenez est correcte.

Source

2015-03-18 11:30:03

Comment la file d'attente de priorité Java est-elle supposée fonctionner?

Répondre

Questions connexes