Lors de l'ajout de valeurs à une file d'attente prioritaire, à quel moment exactement les valeurs sont-elles triées?

Question

ce pseudo-Tenir compte code:

PriorityQueue <Integer> pq = new PriorityQueue(new Comparator() 
{ 
    public int compare(Object o1, Object o2) 
    { 
     Integer e1 = (Integer)o1; 
     Integer e2 = (Integer)o2; 
     if (e1 > e2) {return -1;} 
     if (e2 > e1) {return 1;} 
     return 0; 
    } 
}); 

pq.add(4); 
pq.add(7); 
pq.add(5); 
pq.add(2); 
pq.add(9); 

Maintenant, je me demande, quand exactement pendant la durée d'exécution ne la file d'attente exécuter la méthode compare()? Je suppose qu'il suivrait cet ordre:

i) D'abord les chiffres 4,7,5,2,9 sont ajoutés à la file d'attente dans cet ordre

ii) Ensuite, la file d'attente prioritaire utilise la méthode comparer à trier les valeurs

En d'autres termes, les valeurs sont d'abord insérées dans la file d'attente. Ensuite, ils sont triés. Cette pensée est-elle correcte? Ou les valeurs sont-elles triées lorsqu'elles sont ajoutées à la file d'attente?

Answer 1

Les PriorityQueues ne sont pas de simples structures de données triées comme un type de tableau trié. PriorityQueue dans Java a été implémenté en utilisant des segments de priorité. Vous devriez apprendre comment fonctionnent les tas, mais au fond, quand vous ajoutez un nouvel élément, les comparaisons de log (n) maximum se produisent. La comparaison de tous les éléments entre eux n'est pas nécessaire. Vous pouvez en apprendre davantage sur les files d'attente prioritaires à https://en.m.wikipedia.org/wiki/Priority_queue

Answer 2

PriorityQueue classe a un champ privé Comparator défini pour l'ordre d'insertion (private final Comparator<? super E> comparator) ... donc quand vous faites:

PriorityQueue<Integer> pq = new PriorityQueue<>(foo); 

où foo est une instance de la comparateur, cet objet sera initialisé en interne pour cette instance ...

Après la création de la collection, vous commencez à ajouter des éléments et c'est ici que la magie se produit.

regarder juste à l'intérieur de la classe PriorityQueue et vous trouverez la méthode siftUpUsingComparator, qui sera appelée, et utilise le comparateur que vous avez défini pour vérifier l'ordre d'insertion ...

private void siftUpUsingComparator(int k, E x) { 
    while (k > 0) { 
     int parent = (k - 1) >>> 1; 
     Object e = queue[parent]; 
     if (comparator.compare(x, (E) e) >= 0) 
      break; 
     queue[k] = e; 
     k = parent; 
    } 
    queue[k] = x; 
} 

---

Offtopic:

vous utilisez des collections brutes et ce qui est mauvais, je sugest d'adapter votre code à quelque chose comme:

Comparator<Integer> foo = (o1, o2) -> { 
    Integer e1 = o1; 
    Integer e2 = o2; 
    if (e1 > e2) { 
     return -1; 
    } 
    if (e2 > e1) { 
     return 1; 
    } 
    return 0; 
}; 
PriorityQueue<Integer> pq = new PriorityQueue<>(foo); 

pq.add(4); 
pq.add(7); 
pq.add(5); 
pq.add(2); 
pq.add(9);