Comment utiliser un PriorityQueue?

Comment obtenir un PriorityQueue tri sur ce que je veux qu'il trie?

De plus, y a-t-il une différence entre les méthodes offeret add?

Utilisez la surcharge du constructeur qui prend un Comparator<? super E> comparator et passez dans un comparateur qui compare de la manière appropriée pour votre ordre de tri. Si vous donnez un exemple de la façon dont vous souhaitez trier, nous pouvons fournir un exemple de code pour implémenter le comparateur si vous n'êtes pas sûr. (C'est assez simple cependant.)

Comme cela a été dit ailleurs: offeret ne addsont que des implémentations de méthodes d'interface différentes. Dans la source JDK que j'ai, les addappels offer. Bien addque le offercomportement soit potentiellement différent en général en raison de la possibilité offerd'indiquer que la valeur ne peut pas être ajoutée en raison de limitations de taille, cette différence n'est pas pertinente et n'est pas limitée PriorityQueue.

Voici un exemple de tri de file d'attente prioritaire par longueur de chaîne:

// Test.java
import java.util.Comparator;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        Comparator<String> comparator = new StringLengthComparator();
        PriorityQueue<String> queue = new PriorityQueue<String>(10, comparator);
        queue.add("short");
        queue.add("very long indeed");
        queue.add("medium");
        while (queue.size() != 0) {
            System.out.println(queue.remove());
        }
    }
}

// StringLengthComparator.java
import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {
    @Override
    public int compare(String x, String y) {
        // Assume neither string is null. Real code should
        // probably be more robust
        // You could also just return x.length() - y.length(),
        // which would be more efficient.
        if (x.length() < y.length()) {
            return -1;
        }
        if (x.length() > y.length()) {
            return 1;
        }
        return 0;
    }
}

Voici la sortie:

court

moyen

très long en effet

Solution Java 8

Nous pouvons utiliser lambda expressionou method referenceintroduire dans Java 8. Dans le cas où nous avons des valeurs de chaîne stockées dans la file d'attente prioritaire (ayant une capacité 5), nous pouvons fournir un comparateur en ligne (basé sur la longueur de la chaîne):

Utilisation de l'expression lambda

PriorityQueue<String> pq=
                    new PriorityQueue<String>(5,(a,b) -> a.length() - b.length());

Utilisation de la référence de méthode

PriorityQueue<String> pq=
                new PriorityQueue<String>(5, Comparator.comparing(String::length));

Ensuite, nous pouvons utiliser l'un d'eux comme:

public static void main(String[] args) {
        PriorityQueue<String> pq=
                new PriorityQueue<String>(5, (a,b) -> a.length() - b.length());
       // or pq = new PriorityQueue<String>(5, Comparator.comparing(String::length));
        pq.add("Apple");
        pq.add("PineApple");
        pq.add("Custard Apple");
        while (pq.size() != 0)
        {
            System.out.println(pq.remove());
        }
    }

Cela imprimera:

Apple
PineApple
Custard Apple

Pour inverser l'ordre (pour le changer en file d'attente prioritaire), changez simplement l'ordre dans le comparateur en ligne ou utilisez reversedcomme:

PriorityQueue<String> pq = new PriorityQueue<String>(5, 
                             Comparator.comparing(String::length).reversed());

Nous pouvons également utiliser Collections.reverseOrder:

PriorityQueue<Integer> pqInt = new PriorityQueue<>(10, Collections.reverseOrder());
PriorityQueue<String> pq = new PriorityQueue<String>(5, 
                Collections.reverseOrder(Comparator.comparing(String::length))

Nous pouvons donc voir qu'il Collections.reverseOrderest surchargé pour prendre un comparateur qui peut être utile pour les objets personnalisés. Le reversedutilise en fait Collections.reverseOrder:

default Comparator<T> reversed() {
    return Collections.reverseOrder(this);
}

offer () vs add ()

Selon le doc

La méthode d'offre insère un élément si possible, sinon renvoie false. Cela diffère de la méthode Collection.add, qui peut échouer à ajouter un élément uniquement en lançant une exception non vérifiée. La méthode d'offre est conçue pour être utilisée lorsque la défaillance est une occurrence normale, plutôt qu'exceptionnelle, par exemple, dans des files d'attente à capacité fixe (ou "délimitée").

Lorsque vous utilisez une file d'attente à capacité limitée, offer () est généralement préférable d'ajouter (), qui ne peut pas insérer un élément uniquement en lançant une exception. Et PriorityQueue est une file d'attente prioritaire illimitée basée sur un segment de priorité.

Passez juste approprié Comparatorau constructeur :

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

La seule différence entre offer et addest l'interface à laquelle ils appartiennent. offerappartient à Queue<E>, alors que l' addon voit à l'origine dans l' Collection<E>interface. En dehors de cela, les deux méthodes font exactement la même chose - insérez l'élément spécifié dans la file d'attente prioritaire.

de API Queue :

La méthode d'offre insère un élément si possible, sinon renvoie false. Cela diffère de la méthode Collection.add, qui peut échouer à ajouter un élément uniquement en lançant une exception non vérifiée. La méthode d'offre est conçue pour être utilisée lorsque la défaillance est une occurrence normale, plutôt qu'exceptionnelle, par exemple, dans des files d'attente à capacité fixe (ou "délimitée").

pas différent, comme le déclare javadoc:

public boolean add(E e) {
    return offer(e);
}

Juste pour répondre à la question add()vs offer()(puisque l'autre est parfaitement répondu imo, et cela pourrait ne pas l'être):

Selon JavaDoc sur l' interface de file d' attente , "La méthode offre insère un élément si possible, sinon renvoie false. Cela diffère de la méthode Collection.add, qui ne peut pas ajouter un élément uniquement en lançant une exception non vérifiée. La méthode offre est conçue pour à utiliser lorsque l'échec est une occurrence normale, plutôt qu'exceptionnelle, par exemple, dans les files d'attente à capacité fixe (ou "délimitée"). "

Cela signifie que si vous pouvez ajouter l'élément (ce qui devrait toujours être le cas dans un PriorityQueue), ils fonctionnent exactement de la même manière. Mais si vous ne pouvez pas ajouter l'élément, vous offer()obtiendrez un falseretour agréable et joli , tout en add()lançant une méchante exception non vérifiée que vous ne voulez pas dans votre code. Si l'échec de l'ajout signifie que le code fonctionne comme prévu et / ou que c'est quelque chose que vous vérifierez normalement, utilisez offer(). Si l'échec de l'ajout signifie que quelque chose est cassé, utilisez add()et gérez l'exception résultante levée conformément aux spécifications de l'interface Collection .

Ils sont tous deux implémentés de cette manière pour remplir le contrat sur l'interface de file d'attente qui spécifie les offer()échecs en renvoyant un false( méthode préférée dans les files d'attente à capacité limitée ) et également maintenir le contrat sur l'interface de collecte qui spécifie add()toujours les échecs en lançant une exception .

Quoi qu'il en soit, j'espère que cela clarifie au moins cette partie de la question.

Ici, nous pouvons définir un comparateur défini par l'utilisateur:

Code ci-dessous:

 import java.util.*;
 import java.util.Collections;
 import java.util.Comparator; 


 class Checker implements Comparator<String>
 {
    public int compare(String str1, String str2)
    {
        if (str1.length() < str2.length()) return -1;
        else                               return 1;
    }
 }


class Main
{  
   public static void main(String args[])
    {  
      PriorityQueue<String> queue=new PriorityQueue<String>(5, new Checker());  
      queue.add("india");  
      queue.add("bangladesh");  
      queue.add("pakistan");  

      while (queue.size() != 0)
      {
         System.out.printf("%s\n",queue.remove());
      }
   }  
}  

Production :

   india                                               
   pakistan                                         
   bangladesh

Différence entre l'offre et les méthodes d'ajout: lien

Passez-le a Comparator. Remplissez votre type souhaité à la place deT

Utilisation de lambdas (Java 8+):

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, (e1, e2) -> { return e1.compareTo(e2); });

De façon classique, en utilisant une classe anonyme:

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, new Comparator<T> () {

    @Override
    public int compare(T e1, T e2) {
        return e1.compareTo(e2);
    }

});

Pour trier dans l'ordre inverse, échangez simplement e1, e2.

Je me posais également des questions sur la commande d'impression. Considérez ce cas, par exemple:

Pour une file d'attente prioritaire:

PriorityQueue<String> pq3 = new PriorityQueue<String>();

Ce code:

pq3.offer("a");
pq3.offer("A");

peut imprimer différemment de:

String[] sa = {"a", "A"}; 
for(String s : sa)   
   pq3.offer(s);

J'ai trouvé la réponse d'une discussion sur un autre forum , où un utilisateur a dit: "les méthodes offer () / add () n'insèrent que l'élément dans la file d'attente. Si vous voulez un ordre prévisible, vous devez utiliser peek / poll qui renvoie la tête de la file d'attente. "

Comme alternative à l'utilisation Comparator, vous pouvez également avoir la classe que vous utilisez dans votre PriorityQueue implémentationComparable (et remplacer en conséquence la compareTométhode).

Notez qu'il est généralement préférable d'utiliser uniquement Comparableau lieu de Comparatorsi cet ordre est l'ordre intuitif de l'objet - si, par exemple, vous avez un cas d'utilisation pour trier les Personobjets par âge, il est probablement préférable de simplement utiliser à la Comparatorplace.

import java.lang.Comparable;
import java.util.PriorityQueue;

class Test
{
    public static void main(String[] args)
    {
        PriorityQueue<MyClass> queue = new PriorityQueue<MyClass>();
        queue.add(new MyClass(2, "short"));
        queue.add(new MyClass(2, "very long indeed"));
        queue.add(new MyClass(1, "medium"));
        queue.add(new MyClass(1, "very long indeed"));
        queue.add(new MyClass(2, "medium"));
        queue.add(new MyClass(1, "short"));
        while (queue.size() != 0)
            System.out.println(queue.remove());
    }
}

class MyClass implements Comparable<MyClass>
{
    int sortFirst;
    String sortByLength;

    public MyClass(int sortFirst, String sortByLength)
    {
        this.sortFirst = sortFirst;
        this.sortByLength = sortByLength;
    }

    @Override
    public int compareTo(MyClass other)
    {
        if (sortFirst != other.sortFirst)
            return Integer.compare(sortFirst, other.sortFirst);
        else
            return Integer.compare(sortByLength.length(), other.sortByLength.length());
    }

    public String toString()
    {
        return sortFirst + ", " + sortByLength;
    }
}

Production:

1, short
1, medium
1, very long indeed
2, short
2, medium
2, very long indeed

La file d'attente prioritaire a une priorité assignée à chaque élément. L'élément avec la priorité la plus élevée apparaît en haut de la file d'attente. Maintenant, cela dépend de vous de la façon dont vous souhaitez attribuer la priorité à chacun des éléments. Sinon, Java le fera par défaut. L'élément avec la valeur la plus faible se voit attribuer la priorité la plus élevée et est donc supprimé en premier de la file d'attente. S'il y a plusieurs éléments avec la même priorité la plus élevée, le lien est rompu arbitrairement. Vous pouvez également spécifier une commande à l'aide de Comparator dans le constructeur PriorityQueue(initialCapacity, comparator)

Exemple de code:

PriorityQueue<String> queue1 = new PriorityQueue<>();
queue1.offer("Oklahoma");
queue1.offer("Indiana");
queue1.offer("Georgia");
queue1.offer("Texas");
System.out.println("Priority queue using Comparable:");
while (queue1.size() > 0) {
    System.out.print(queue1.remove() + " ");
}
PriorityQueue<String> queue2 = new PriorityQueue(4, Collections.reverseOrder());
queue2.offer("Oklahoma");
queue2.offer("Indiana");
queue2.offer("Georgia");
queue2.offer("Texas");
System.out.println("\nPriority queue using Comparator:");
while (queue2.size() > 0) {
    System.out.print(queue2.remove() + " ");
}

Production:

Priority queue using Comparable:
Georgia Indiana Oklahoma Texas 
Priority queue using Comparator:
Texas Oklahoma Indiana Georgia 

Sinon, vous pouvez également définir un comparateur personnalisé:

import java.util.Comparator;

public class StringLengthComparator implements Comparator<String>
{
    @Override
    public int compare(String x, String y)
    {
        //Your Own Logic
    }
}

Voici l'exemple simple que vous pouvez utiliser pour l'apprentissage initial:

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

public class PQExample {

    public static void main(String[] args) {
        //PriorityQueue with Comparator
        Queue<Customer> cpq = new PriorityQueue<>(7, idComp);
        addToQueue(cpq);
        pollFromQueue(cpq);
    }

    public static Comparator<Customer> idComp = new Comparator<Customer>(){

        @Override
        public int compare(Customer o1, Customer o2) {
            return (int) (o1.getId() - o2.getId());
        }

    };

    //utility method to add random data to Queue
    private static void addToQueue(Queue<Customer> cq){
        Random rand = new Random();
        for(int i=0;i<7;i++){
            int id = rand.nextInt(100);
            cq.add(new Customer(id, "KV"+id));
        }
    }


    private static void pollFromQueue(Queue<Customer> cq){
        while(true){
            Customer c = cq.poll();
            if(c == null) break;
            System.out.println("Customer Polled : "+c.getId() + " "+ c.getName());
        }
    }

}