Java Priority Queue: geen klassieke wachtrij

In dit artikel leren we een prioriteitswachtrij, Java-klasse, die de Queue-interface implementeert. Wat weet een programmeur van de reguliere wachtrij-interface? Allereerst is deze interface gebaseerd op het FIFO-principe of “first in first out”. Dat herinnert aan een gewone wachtrij in zijn gebruikelijke betekenis. Wil je koffie halen bij McDrive? Als uw auto als eerste bij het raam staat, krijgt u uw koffie eerder dan de chauffeur die ernaast zit.

Queue Interface-declaratie

public interface Queue<E> extends Collection<E>

Wat is een prioriteitswachtrij

Wat is een prioriteitswachtrij? Allereerst is het een klasse die de Queue-interface implementeert in het geval van het invoegen van een element vanaf de achterkant en het verwijderen van een element uit het hoofd. Het is echter geen gebruikelijke rij binnen. De volgorde van Java-prioriteitswachtrij-elementen is afhankelijk van de prioriteit van de elementen. Het element met de hoogste prioriteit wordt naar het hoofd van de wachtrij verplaatst. Als je het hoogst gerangschikte element verwijdert (serveert), gaat het tweede naar het hoofd om zijn koffie te halen. Hoe wordt prioriteit bepaald? Volgens de documentatie zijn de elementen van de prioriteitswachtrij geordend volgens hun natuurlijke ordening, of door een comparator die wordt geleverd tijdens de opbouw van de wachtrij, afhankelijk van welke constructor wordt gebruikt. Een prioriteitswachtrij op basis van een minimale prioriteitsheap. Dat betekent, in het geval van nummers wachtrij-elementen, het eerste element van de wachtrij is het minimum van deze nummers. Vrij vaak beginnen beginnende studenten na het lezen van deze definitie te denken dat de prioriteitswachtrij in lineaire zin is gesorteerd. Dat wil zeggen, als we bijvoorbeeld een wachtrij gebruiken waarvan de elementen natuurlijke getallen zijn, dan is het eerste element het kleinste en het laatste - het grootste. Dit is niet helemaal waar. Om te begrijpen hoe de prioriteitswachtrij werkelijk werkt en wat deze oplevert, moet u uitzoeken hoe de heap werkt. We beschouwen de interne structuur van de prioriteitswachtrij even later aan de hand van een voorbeeld. Laten we nu stilstaan ​​​​bij de externe kenmerken. dan is het eerste element het kleinste en het laatste - het grootste. Dit is niet helemaal waar. Om te begrijpen hoe de prioriteitswachtrij werkelijk werkt en wat deze oplevert, moet u uitzoeken hoe de heap werkt. We beschouwen de interne structuur van de prioriteitswachtrij even later aan de hand van een voorbeeld. Laten we nu stilstaan ​​​​bij de externe kenmerken. dan is het eerste element het kleinste en het laatste - het grootste. Dit is niet helemaal waar. Om te begrijpen hoe de prioriteitswachtrij werkelijk werkt en wat deze oplevert, moet u uitzoeken hoe de heap werkt. We beschouwen de interne structuur van de prioriteitswachtrij even later aan de hand van een voorbeeld. Laten we nu stilstaan ​​​​bij de externe kenmerken.

PriorityQueue klasse constructors en declaratie

De PriorityQueue-klasse biedt 6 verschillende manieren om een ​​prioriteitswachtrij in Java samen te stellen.

• PriorityQueue() - lege wachtrij met de standaard initiële capaciteit (11) die de elementen ordent volgens hun natuurlijke volgorde.
• PriorityQueue(Collection c) - lege wachtrij met de elementen in de gespecificeerde collectie.
• PriorityQueue(int initialCapacity) - lege wachtrij met de opgegeven initiële capaciteit die de elementen ordent volgens hun natuurlijke volgorde.
• PriorityQueue(int initialCapacity, Comparator comparator) - lege wachtrij met de opgegeven initiële capaciteit die de elementen ordent volgens de opgegeven comparator.
• PriorityQueue(PriorityQueue c) - lege wachtrij met de elementen in de opgegeven prioriteitswachtrij.
• PriorityQueue(SortedSet c) - lege wachtrij met de elementen in de gespecificeerde gesorteerde set.

Priority Queue in Java wordt op de volgende manier gedeclareerd:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

PriorityQueue maken

Laten we een prioriteitswachtrij van gehele getallen maken. Priority Queue-implementatie, Java-code:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

We hebben een prioriteitswachtrij gemaakt zonder argumenten. In dit geval is de kop van de wachtrij met prioriteit het minimale nummer van de wachtrij. Als je het hoofd verwijdert, zal het volgende kleinste element deze plaats innemen. U kunt dus in oplopende volgorde elementen uit de wachtrij verwijderen. Indien nodig kunt u het bestelprincipe wijzigen met behulp van de Comparator-interface.

Java PriorityQueue-methoden

PriorityQueue Java-klasse heeft belangrijke methoden om elementen toe te voegen, te verwijderen en te controleren.

Elementen invoegen in prioriteitswachtrij

• boolean add(object) voegt het opgegeven element in de prioriteitswachtrij in. Retourneert true in geval van succes. Als de wachtrij vol is, genereert de methode een uitzondering.
• boolean offer(object) voegt het gespecificeerde element in deze prioriteitswachtrij in. Als de wachtrij vol is, retourneert de methode false.

U kunt beide optelbewerkingen gebruiken, er zijn geen verschillen voor meerderheidsgevallen. Hier is een klein voorbeeld van initiatie en het toevoegen van elementen aan de prioriteitswachtrij.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

De uitvoer is:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

De volgorde van de elementen lijkt raar, we zullen het later uitleggen.

Ophalen en verwijderen van elementen uit de prioriteitswachtrij

• boolean remove(object) verwijdert een enkel exemplaar van het gespecificeerde element uit deze wachtrij, indien aanwezig.
• Object poll() haalt de kop van deze wachtrij op en verwijdert deze. Retourneert null als de wachtrij leeg is.
• void clear() verwijdert alle elementen uit de prioriteitswachtrij.
• Object element() haalt de kop van deze wachtrij op zonder deze te verwijderen. Gooit NoSuchElementException als de wachtrij leeg is.
• Object peek() haalt de kop van de wachtrij op zonder deze te verwijderen. Retourneert null als de wachtrij leeg is.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

Het resultaat:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

Zoals u wellicht ziet, leidt het proberen om de kop van de lege wachtrij af te drukken met behulp van de methode element() tot NoSuchElementexception .

PriorityQueue-vergelijker

• Comparator comparator() retourneert de comparator die gebruikt werd om de elementen in de wachtrij te ordenen. Retourneert null als de wachtrij is gesorteerd volgens de natuurlijke volgorde van de elementen.

Java-prioriteitswachtrij, voorbeeld met vergelijker

We gebruikten natuurlijke (oplopende) volgorde in de bovenstaande codevoorbeelden, maar soms moeten we deze wijzigen. Hier is een voorbeeld van een Java-prioriteitswachtrij, waar we onze eigen interne comparatorklasse maken die de Comparator-interface implementeert. Onze vergelijker sorteert elementen van groot naar klein.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

Het resultaat:

the head of Queue = 5
5
4
3
2
1

Het hoofd van de wachtrij is nu niet het minimale, maar het maximale element en de volgorde is gewijzigd in omgekeerd.

Itereren over PriorityQueue met behulp van iterator

ProrityQueue maakt deel uit van het Collection-framework en implementeert de Iterable<>- interface. Om elementen van een prioriteitswachtrij te herhalen, kunt u de methode iterator() gebruiken . Hier is een voorbeeld:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

Het resultaat:

1 2 4 5 3 

Meer PriorityQueue-methoden

• boolean bevat(Object o) retourneert true als de wachtrij het o-element bevat.
• int size() geeft het aantal elementen in deze wachtrij terug.
• Object[] toArray() retourneert een array die alle elementen in deze wachtrij bevat.

Hier is een voorbeeld:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

Het resultaat:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

PriorityQueue Java 8-definitie

Als u de java 8-documentatie van de prioriteitswachtrij opent, vindt u daar de volgende definitie: Een onbeperkte prioriteitswachtrij op basis van een prioriteitsheap. De elementen van de prioriteitswachtrij worden geordend volgens hun natuurlijke ordening, of door een comparator die wordt geleverd tijdens de opbouw van de wachtrij, afhankelijk van welke constructor wordt gebruikt. Een prioriteitswachtrij staat geen null-elementen toe. Een prioriteitswachtrij die vertrouwt op natuurlijke ordening staat ook het invoegen van niet-vergelijkbare objecten niet toe (dit kan resulteren in ClassCastException). Heap is hier een heel belangrijk woord. Het verklaart de eigenschappen van het bestellen van Priority Queue-elementen.

Het principe van PriorityQueue-werk: binaire heap

Laten we beginnen met een voorbeeld. Laten we twee objecten maken die de Queue-interface implementeren. Een van hen LinkedList, de tweede - PriorityQueue. Beiden hebben 5 elementen van Integer (1,2,3,4 en 5) en we beginnen de elementen in onze wachtrijen te plaatsen van de grootste tot de kleinste. Dus de eerste is 5, dan 4, 3, 2 en de laatste is 1. Print vervolgens beide lijsten uit om de bestelling te controleren.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

Het resultaat van deze codewerking is het volgende:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Welnu, de volgorde van de gekoppelde lijsten is voorspelbaar en begrijpelijk. Het is besteld volgens het FIFO-principe. We zijn begonnen met 5, dus dit element is het allereerste in de rij, gaat dan 4 enzovoort. Wat kunnen we vertellen over de volgorde van prioriteitswachtrijen? Docs zei dat de elementen van de prioriteitswachtrij zijn geordend volgens hun natuurlijke volgorde, of door een comparator die wordt verstrekt tijdens de opbouw van de wachtrij. Deze volgorde lijkt echter niet "natuurlijk" in lineaire sorteerbetekenis. We verwachten liever [1, 2, 3, 4, 5], niet [1, 2, 4, 5, 3]. Om te begrijpen waarom de volgorde van ophalen is zoals deze is, moeten we ons die prioriteitswachtrij herinneren die is gebaseerd op een hoop. Wat is de hoop? Het is een gegevensstructuur gebaseerd op een binaire boom. De belangrijkste eigenschap van de heap: de prioriteit van elke ouder is groter dan de prioriteiten van zijn kinderen. Laat me je eraan herinneren dat een boom een ​​volledig binair getal wordt genoemd als elke ouder niet meer dan twee kinderen heeft en de niveaus van boven naar beneden worden gevuld (van hetzelfde niveau - van links naar rechts). Binaire heap reorganiseert zichzelf elke keer dat er elementen worden toegevoegd of verwijderd. In het geval van min-heap gaat het kleinste element naar de root, ongeacht de volgorde van invoeging. Prioriteitswachtrij op basis van deze min-heap. Dat betekent dat, in het geval van wachtrij-elementen, het eerste element van de wachtrij het minimum van deze nummers zal zijn. Als u de wortel verwijdert, wordt de volgende kleinste een wortel.

Laten we naar ons voorbeeld gaan.

Stap 1. We zetten '5' in de prioriteitswachtrij. Het wordt een wortel. Stap 2. We voegen '4' toe aan de prioriteitswachtrij. 4 <5, dus het nieuwe element moet hoger zijn dan het oude. De 4 wordt een wortel, 5 is het linkerkind. Nu is de datastructuur in Java [4, 5] Stap 3. We voegen '3' toe. Tijdelijk wordt het een rechterkind van een wortel (4). Echter, 3 < 4, dus we moeten het optillen. Verwissel 3 en 4. Nu hebben we een structuur zoals [3, 5, 4] Stap 4. We voegen '2' toe. Het wordt een linkerkind van 5. 2<5, dus verwissel ze. 2 wordt een linkerkind van 3, 2 < 3, dus nog een ruilproces. Nu hebben we een structuur [2,3,4,5] Stap 5.We voegen '1' toe. Het komt van het rechterkind van de 3 naar het linkerkind van de 2, en gaat dan naar de wortel. De resulterende gegevensstructuur: [1,2,4,5,3] Het verwijderingsproces begint vanaf een root en lokt de omgekeerde procedures uit. Dus eerst hebben we 1 als root, dan 2, 3, 4 en als laatste 5. Daarom gebruiken we de verwijderbewerking poll()

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

we hebben "gesorteerd" in lineaire sence-uitvoer:

1
2
3
4
5

De prioriteitswachtrij kan dus effectief zijn voor sommige bewerkingen. Het kost O(log N) tijd om elk element in te voegen en te verwijderen, en je kunt het minimale element in O(1) krijgen. Hier is het volledige voorbeeld:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Het is belangrijk om te begrijpen dat prioriteitswachtrijen gebaseerd zijn op binaire heaps, zodat ze de elementen niet in lineaire gesorteerde volgorde houden. Elke weg van de wortel naar het blad is geordend, maar de verschillende wegen van de wortel niet. Dat betekent dat je heel snel het minimale deel van de wachtrij kunt krijgen.

Wat u moet weten over prioriteitswachtrij. Korte lijst

• Priority Queue staat geen NULL-objecten toe.
• U kunt alleen vergelijkbare objecten toevoegen aan PriorityQueue.
• Prioriteitswachtrij is opgebouwd als een min-heap, een soort binaire boom. Het minimale element is een root. De objecten van de prioriteitswachtrij worden standaard in natuurlijke volgorde geordend.
• U kunt Comparator gebruiken als u op maat wilt bestellen.
• PriorityQueue is niet thread-safe, dus u kunt PriorityBlockingQueue beter gebruiken om in een gelijktijdige omgeving te werken.
• PriorityQueue biedt O(log(n)) tijd voor add- en poll-methoden en O(1) om minimale elementen te krijgen.