Comment utiliser une PriorityQueue?

Solution Java 8

, Nous pouvons utiliser lambda expression ou method reference introduit dans Java 8. Dans le cas où nous avons des valeurs de chaîne stockées dans la file d'attente prioritaire (ayant la 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));

Alors nous pouvons utiliser n'importe lequel d'entre 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());
        }
    }

Ceci imprimera:

Apple
PineApple
Custard Apple

Pour inverser l'ordre (pour le changer en priorité maximale file d'attente) modifiez simplement l'ordre dans le comparateur en ligne ou utilisez reversed comme:

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

On peut aussi 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 que Collections.reverseOrder est surchargé pour prendre un comparateur qui peut être utile pour les objets personnalisés. Le reversed utilise en fait Collections.reverseOrder:

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

Offre() vs ajouter()

, Comme par le doc

La méthode offer insère un élément si possible, sinon retournant faux. Cela diffère de la Collection.ajouter une méthode, qui peut ne parviennent pas à ajoutez un élément uniquement en lançant une exception non cochée. Offre la méthode est conçue pour être utilisée lorsque l'échec est normal, plutôt que cas exceptionnel, par exemple, à capacité fixe (ou " bornée") file.

Lors de l'utilisation d'une file d'attente restreinte à la capacité, offer() est généralement préférable à add(), qui ne peut pas insérer un élément qu'en lançant une exception. Et PriorityQueue est une file d'attente prioritaire illimitée basée sur un tas prioritaire.

Il suffit de passer au approprié Comparator le constructeur:

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

La seule différence entre offer et add est l'interface à laquelle ils appartiennent. offer appartient à Queue<E>, alors que add est vu à l'origine dans Collection<E> de l'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 de file d'attente :

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

Pas différent, comme déclaré dans javadoc:

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

Passez-lui un Comparator. Remplissez le type souhaité à la place de T

Utilisation de lambdas (Java 8+):

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

De manière 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, il suffit d'échanger e1, e2.

Juste pour répondre à la question add() vs offer() (puisque l'autre est parfaitement répondu à l'omi, et ce n'est peut-être pas le cas):

Selon JavaDoc sur la file d'attente d'interface, "La méthode offer insère un élément si possible, sinon elle renvoie false. Cela diffère de la Collection.méthode add, qui peut échouer à ajouter un élément uniquement en lançant une exception non cochée. La méthode d'offre est conçue pour être utilisée lorsque la défaillance est un événement normal plutôt qu'exceptionnel, par exemple, dans les files d'attente à capacité fixe (ou "délimitées")."

Cela signifie que si vous pouvez ajouter l'élément (ce qui devrait toujours être le cas dans une PriorityQueue), ils fonctionnent exactement de la même manière. Mais si vous ne pouvez pas ajouter l'élément, offer() vous donnera un joli et joli retour false, tandis que add() lève une exception non cochée désagréable 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 vous le vérifierez normalement, utilisez offer(). Si échec de l'ajout signifie que quelque chose est cassé, utilisez add()et gérez l'exception résultante levée selon les spécifications de l'interface de collection.

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

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

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

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

Sortie :

   india                                               
   pakistan                                         
   bangladesh

Différence entre l'offre et ajouter des méthodes : lien

, Comme une alternative à l'utilisation de Comparator, vous pouvez aussi avoir la classe que vous utilisez dans votre PriorityQueue mettre en œuvre Comparable (et, en conséquence de remplacer les compareTo méthode).

Notez qu'il est généralement préférable d'utiliser seulement Comparable au lieu de Comparator si cette commande est la commande intuitive de l'objet - par exemple, si vous avez un cas d'utilisation de tri Person objets par l'âge, il est probablement préférable d'utiliser Comparator à la place.

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

Sortie:

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

Je me posais aussi des questions sur l'ordre d'impression. Considérons 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() insèrent uniquement 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."

La file d'attente prioritaire a une certaine 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 comment vous voulez que la priorité soit attribuée à chacun des éléments. Si vous ne le faites pas, Java le fera de la manière par défaut. L'élément avec la valeur la moins élevée est la priorité la plus élevée et est donc retiré de la file d'attente. S'il y a plusieurs éléments avec la même priorité la plus élevée, l'égalité est rompue arbitrairement. Vous pouvez également spécifier une commande utilisation du comparateur 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() + " ");
}

Sortie:

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

}