Hoe gebruik ik een PriorityQueue?

Hoe krijg ik een PriorityQueueom te sorteren op waar ik op wil sorteren?

Is er ook een verschil tussen de offeren add?

Antwoord 1, autoriteit 100%

Gebruik de constructoroverbelasting waarvoor een Comparator<? super E> comparatoren geef een comparator door die op de juiste manier vergelijkt voor uw sorteervolgorde. Als u een voorbeeld geeft van hoe u wilt sorteren, kunnen we een voorbeeldcode geven om de comparator te implementeren als u het niet zeker weet. (Het is echter vrij eenvoudig.)

Zoals elders is gezegd: offeren addzijn gewoon verschillende implementaties van interfacemethoden. In de JDK-bron die ik heb, roept addofferaan. Hoewel adden offerin het algemeen potentieelverschillend gedrag vertonen vanwege de mogelijkheid voor offerom aan te geven dat de waarde kan kan niet worden toegevoegd vanwege de groottebeperkingen, dit verschil is niet relevant in PriorityQueuedat onbeperkt is.

Hier is een voorbeeld van een prioriteitswachtrij sorteren op tekenreekslengte:

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

Hier is de uitvoer:

kort

gemiddeld

heel lang inderdaad

Antwoord 2, autoriteit 17%

Java 8-oplossing

We kunnen lambda expressionof method referencegebruiken die in Java 8 is geïntroduceerd. Als we enkele tekenreekswaarden hebben opgeslagen in de prioriteitswachtrij (met capaciteit 5), kunnen we inline comparator (gebaseerd op lengte van String):

Lambda-expressie gebruiken

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

Methodereferentie gebruiken

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

Dan kunnen we ze allemaal gebruiken als:

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

Hiermee wordt afgedrukt:

Apple
PineApple
Custard Apple

Als u de volgorde wilt omkeren (om deze te wijzigen in wachtrij met maximale prioriteit), wijzigt u eenvoudig de volgorde in de inline-vergelijker of gebruikt u reversedals:

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

We kunnen ook Collections.reverseOrdergebruiken:

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

We kunnen dus zien dat Collections.reverseOrderoverbelast is om een comparator te gebruiken, wat handig kan zijn voor aangepaste objecten. De reversedgebruikt eigenlijk Collections.reverseOrder:

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

offer() vs add()

Volgens de doc

De aanbiedingsmethode voegt indien mogelijk een element in, anders wordt geretourneerd
vals. Dit verschilt van de methode Collection.add, die mogelijk niet werkt:
voeg alleen een element toe door een ongecontroleerde uitzondering te genereren. Het aanbod
methode is ontworpen voor gebruik wanneer falen normaal is, in plaats van
uitzonderlijke gebeurtenis, bijvoorbeeld in vaste capaciteit (of “begrensd”)
wachtrijen.

Bij gebruik van een wachtrij met beperkte capaciteit, heeft offer() over het algemeen de voorkeur boven add(), die een element niet kan invoegen door alleen een uitzondering te maken. En PriorityQueueis een onbeperkte prioriteitswachtrij op basis van een prioriteitshoop.

Antwoord 3, autoriteit 5%

Geef gewoon de juiste Comparatornaar de constructor:

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

Het enige verschil tussen offeren addis de interface waartoe ze behoren. offeris van Queue<E>, terwijl addoorspronkelijk wordt gezien in Collection<E>-interface. Afgezien daarvan doen beide methoden precies hetzelfde – het opgegeven element invoegen in de prioriteitswachtrij.

Antwoord 4, autoriteit 4%

van Wachtrij-API:

De offer-methode voegt indien mogelijk een element in, anders wordt false geretourneerd. Dit verschilt van de methode Collection.add, die een element alleen niet kan toevoegen door een ongecontroleerde uitzondering te genereren. De aanbiedingsmethode is ontworpen voor gebruik wanneer een storing normaal is in plaats van een uitzonderlijke gebeurtenis, bijvoorbeeld in wachtrijen met een vaste capaciteit (of “begrensde”).

Antwoord 5, autoriteit 3%

niet anders, zoals declareren in javadoc:

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

Antwoord 6, autoriteit 3%

Geef het een Comparatordoor. Vul uw gewenste type in in plaats van T

Lambda’s gebruiken (Java 8+):

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

Klassieke manier, met anonieme klas:

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, new Comparator<T> () {
    @Override
    public int compare(T e1, T e2) {
        return e1.compareTo(e2);
    }
});

Om in omgekeerde volgorde te sorteren, verwissel je gewoon e1, e2.

Antwoord 7

Gewoon om de add()vs offer()vraag te beantwoorden (aangezien de andere perfect beantwoord is, en dit misschien niet):

Volgens JavaDoc op interfacewachtrij, “De offer-methode voegt indien mogelijk een element in, anders wordt false geretourneerd. Dit verschilt van de Collection.add-methode, die er niet in kan slagen een element toe te voegen door alleen een niet-aangevinkte uitzondering te genereren. , in plaats van een uitzonderlijke gebeurtenis, bijvoorbeeld in wachtrijen met een vaste capaciteit (of “begrensde”).”

Dat betekent dat als je het element kunt toevoegen (wat altijd het geval zou moeten zijn in een PriorityQueue), ze precies hetzelfde werken. Maar als je het element niet kunt toevoegen, geeft offer()je een mooie en mooie falsereturn, terwijl add()een vervelende ongecontroleerde uitzondering die u niet in uw code wilt. Als het niet toevoegen betekent dat de code werkt zoals bedoeld en/of iets is dat u normaal zult controleren, gebruikt u offer(). Als het niet toevoegen betekent dat er iets kapot is, gebruik dan add()en handel de resulterende uitzondering af volgens specificaties van de collectie-interface.

Ze zijn beide op deze manier geïmplementeerd om het contract te vervullen in de wachtrij-interface die aangeeft dat offer()mislukt door een falsete retourneren (methode die de voorkeur heeft in wachtrijen met beperkte capaciteit) en ook onderhoud het contract op de collectie-interface dat specificeert add()altijd mislukt door een uitzondering te genereren.

Hoe dan ook, ik hoop dat dit in ieder geval dat deel van de vraag verduidelijkt.

Antwoord 8

Hier kunnen we een door de gebruiker gedefinieerde comparator definiëren:

Hieronder code:

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

Uitvoer:

  india                                               
   pakistan                                         
   bangladesh

Verschil tussen de aanbiedings- en add-methoden: link

Antwoord 9

Als alternatief voor het gebruik van Comparator, je kunt de klasse die je gebruikt ook in je PriorityQueueimplementeren Comparable(en dienovereenkomstig de compareTooverschrijven methode).

Merk op dat het over het algemeen het beste is om alleen Comparablete gebruiken in plaats van Comparatorals die volgorde de intuïtieve volgorde van het object is – als je bijvoorbeeld een use case hebt om Person-objecten op leeftijd te sorteren, is het waarschijnlijk het beste om gewoon Comparatorte gebruiken.

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

Uitvoer:

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

Antwoord 10

Ik vroeg me ook af hoe het zit met de printopdracht. Beschouw dit geval bijvoorbeeld:

Voor een wachtrij met prioriteit:

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

Deze code:

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

kan anders worden afgedrukt dan:

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

Ik vond het antwoord van een discussie Op een ander forum , waar een gebruiker zei: “De methoden van de aanbieding () / add () Steek alleen het element in de wachtrij. Als u een voorspelbare volgorde wilt, moet u PEEK / POLL gebruiken die het hoofd van de wachtrij. “

Antwoord 11

Prioriteitswachtrij heeft enige prioriteit die aan elk element is toegewezen, het element met de hoogste prioriteit verschijnt aan de bovenkant van de wachtrij. Nu is het afhankelijk van u hoe u prioriteit wilt die aan elk van de elementen is toegewezen. Als je dat niet doet, zal de Java het de standaard manier doen. Het element met de minste waarde heeft de hoogste prioriteit toegewezen en wordt dus eerst uit de wachtrij verwijderd. Als er verschillende elementen zijn met dezelfde hoogste prioriteit, is de stropdas willekeurig gebroken. U kunt ook een bestelling specificeren met behulp van comparator in de constructor PriorityQueue(initialCapacity, comparator)

Voorbeeldcode:

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

Uitvoer:

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

Anders kunt u ook een Custom Comparator definiëren:

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

Antwoord 12

Hier is het eenvoudige voorbeeld dat u kunt gebruiken voor het eerste leerproces:

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