Java Priority Queue: ikke en klassisk kø

I denne artikkelen lærer vi en prioritert kø, Java-klassen, som implementerer Queue-grensesnitt. Hva vet en programmerer om vanlig køgrensesnitt? For det første er dette grensesnittet basert på FIFO-prinsippet eller "først inn først ut". Det minner om en vanlig kø i sin vanlige betydning. Vil du ha kaffe fra McDrive? Hvis bilen din er den første i nærheten av vinduet, får du kaffen før sjåføren som er neste.

Deklarasjon for køgrensesnitt

public interface Queue<E> extends Collection<E>

Hva er en prioritert kø

Hva er en prioritert kø? Først av alt er det en klasse som implementerer Queue-grensesnittet i tilfelle å sette inn et element fra baksiden og fjerne et element fra hodet. Det er imidlertid ikke en vanlig kø inne. Rekkefølgen på Java-prioritetskøelementer avhenger av prioriteten til elementene. Elementet med høyest prioritet vil bli flyttet til toppen av køen. Hvis du sletter (serverer) det høyest rangerte elementet, går det andre til hodet for å få kaffen. Hvordan bestemmes prioritet? I følge dokumentasjonen er elementene i prioritetskøen ordnet i henhold til deres naturlige rekkefølge, eller av en komparator levert ved købyggingstid, avhengig av hvilken konstruktør som brukes. En prioritert kø basert på en prioritet min haug. Det betyr at i tilfelle av tallkøelementer, det første elementet i køen vil være det minste av disse tallene. Ganske ofte etter å ha lest denne definisjonen begynner nybegynnere å tenke at prioritert kø er sortert i en lineær forstand. Det vil si at hvis vi for eksempel bruker en kø hvis elementer er naturlige tall, vil det første elementet være det minste, og det siste - det største. Dette er ikke helt sant. For å forstå hvordan prioritetskøen faktisk fungerer og hva den gir, må du finne ut hvordan haugen fungerer. Vi vurderer den interne strukturen til prioritetskøen ved å bruke et eksempel litt senere. La oss nå dvele ved dens eksterne attributter. da vil det første elementet være det minste, og det siste - det største. Dette er ikke helt sant. For å forstå hvordan prioritetskøen faktisk fungerer og hva den gir, må du finne ut hvordan haugen fungerer. Vi vurderer den interne strukturen til prioritetskøen ved å bruke et eksempel litt senere. La oss nå dvele ved dens eksterne attributter. da vil det første elementet være det minste, og det siste - det største. Dette er ikke helt sant. For å forstå hvordan prioritetskøen faktisk fungerer og hva den gir, må du finne ut hvordan haugen fungerer. Vi vurderer den interne strukturen til prioritetskøen ved å bruke et eksempel litt senere. La oss nå dvele ved dens eksterne attributter.

PriorityQueue klasse konstruktører og erklæring

PriorityQueue-klassen gir 6 forskjellige måter å konstruere en prioritetskø i Java.

• PriorityQueue() - tom kø med standard innledende kapasitet (11) som bestiller elementene i henhold til deres naturlige rekkefølge.
• PriorityQueue(Samling c) - tom kø som inneholder elementene i den angitte samlingen.
• PriorityQueue(int initialCapacity) - tom kø med spesifisert startkapasitet som bestiller elementene i henhold til deres naturlige rekkefølge.
• PriorityQueue(int initialCapacity, Comparator comparator) - tom kø med den spesifiserte initialkapasiteten som bestiller elementene i henhold til den spesifiserte komparatoren.
• PriorityQueue(PriorityQueue c) - tom kø som inneholder elementene i den angitte prioritetskøen.
• PriorityQueue(SortedSet c) - tom kø som inneholder elementene i det spesifiserte sorterte settet.

Prioritetskø i Java erklæres på neste måte:

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

Oppretter PriorityQueue

La oss lage en prioritert kø med heltall. Implementering av prioritert kø, Java-kode:

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

Vi har laget en prioritert kø uten argumenter. I dette tilfellet er lederen av prioritetskøen det minimale antallet i køen. Hvis du fjerner hodet, vil det nest minste elementet ta denne plassen. Så du kan fjerne elementer fra køen i stigende rekkefølge. Om nødvendig kan du endre bestillingsprinsippet ved å bruke Comparator-grensesnittet.

Java PriorityQueue-metoder

PriorityQueue Java-klassen har viktige metoder for å legge til, fjerne og sjekke elementer.

Sett inn elementer i prioritert kø

• boolean add(object) setter inn det spesifiserte elementet i prioritetskøen. Returnerer sann ved suksess. Hvis køen er full, gir metoden et unntak.
• boolesk tilbud(objekt) setter inn det spesifiserte elementet i denne prioriterte køen. Hvis køen er full, returnerer metoden false.

Du kan bruke begge tilleggsoperasjonene, det er ingen forskjeller for de fleste tilfeller. Her er et lite eksempel på initiering og å legge til elementer i prioritert kø.

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

Utgangen er:

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

Rekkefølgen på elementene ser ut til å være rar, vi skal forklare det senere.

Henter og fjerner elementer fra prioritert kø

• boolean remove(object) fjerner en enkelt forekomst av det spesifiserte elementet fra denne køen, hvis den er til stede.
• Object poll() henter og fjerner hodet på denne køen. Returnerer null hvis køen er tom.
• void clear() fjerner alle elementer fra prioritetskøen.
• Object element() henter hodet til denne køen uten å fjerne den. Kaster NoSuchElementException hvis køen er tom.
• Object peek() henter lederen av køen uten å fjerne den. Returnerer null hvis køen er tom.

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

Utgangen:

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)

Som du kanskje ser, fører det til NoSuchElementexception å prøve å skrive ut hodet til den tomme køen ved å bruke element()-metoden .

PriorityQueue Comparator

• Comparator comparator() returnerer komparatoren som brukte til å bestille elementene i køen. Returnerer null hvis køen er sortert i henhold til den naturlige rekkefølgen av elementene.

Java-prioritetskø, eksempel med komparator

Vi brukte naturlig (stigende) rekkefølge i kodeeksemplene ovenfor, men noen ganger bør vi endre den. Her er et eksempel på Java-prioritetskø, der vi lager vår egen interne komparatorklasse som implementerer Comparator-grensesnittet. Vår komparator vil sortere elementer fra de største til de minste.

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

Utgangen:

the head of Queue = 5
5
4
3
2
1

Head of Queue nå er ikke det minimale, men maksimale elementet, og rekkefølgen ble endret til omvendt.

Itererer over PriorityQueue ved hjelp av iterator

ProrityQueue er en del av samlingsrammeverket og implementerer Iterable<>- grensesnittet. For å iterere over elementer i en prioritetskø kan du bruke iterator()- metoden. Her er et eksempel:

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

Utgangen:

1 2 4 5 3 

Flere PriorityQueue-metoder

• boolean contains(Object o) returnerer true hvis køen inneholder o-elementet.
• int size() returnerer antall elementer i denne køen.
• Objekt[] tilArray() returnerer en matrise som inneholder alle elementene i denne køen.

Her er et eksempel:

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

Utgangen:

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-definisjon

Hvis du åpner priorityqueue java 8-dokumentasjonen, vil du finne den neste definisjonen der: En ubegrenset prioritetskø basert på en prioritetshaug. Elementene i prioritetskøen er ordnet i henhold til deres naturlige rekkefølge, eller av en komparator som leveres ved købyggingstid, avhengig av hvilken konstruktør som brukes. En prioritert kø tillater ikke null-elementer. En prioritert kø som er avhengig av naturlig rekkefølge, tillater heller ikke innsetting av ikke-sammenlignbare objekter (det kan resultere i ClassCastException). Heap er et veldig viktig ord her. Den forklarer egenskapene til bestilling av Priority Queue-elementer.

Prinsippet for PriorityQueue-arbeid: Binary Heap

La oss starte med et eksempel. La oss lage to objekter som implementerer Queue-grensesnittet. En av dem LinkedList, den andre - PriorityQueue. Begge har 5 elementer av heltall (1,2,3,4 og 5), og vi begynner å sette elementene inn i køene våre fra det største til det minste. Så den første kommer 5, deretter 4, 3, 2 og den siste blir 1. Skriv deretter ut begge listene for å sjekke bestillingen.

   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)

Resultatet av at disse koden fungerer er det neste:

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

Vel, rekkefølgen på linkedlist er forutsigbar og forståelig. Den er bestilt etter FIFO-prinsippet. Vi startet med 5, så dette elementet er det aller første i rekken, så går det 4 og så videre. Hva kan vi fortelle om prioritert købestilling? Docs sa at elementene i prioritetskøen er ordnet i henhold til deres naturlige rekkefølge, eller av en komparator som leveres ved købygging. Denne rekkefølgen ser imidlertid ikke ut til å være "naturlig" i lineær sorteringsbetydning. Vi forventer heller [1, 2, 3, 4, 5], ikke [1, 2, 4, 5, 3]. For å forstå hvorfor rekkefølgen for henting er som den er, bør vi huske den prioriterte køen basert på en haug. Hva er haugen? Det er en datastruktur basert på binært tre. Den viktigste egenskapen til haugen: prioriteringen til hver forelder er større enn prioriteringene til barna. La meg minne deg på at et tre kalles en komplett binær hvis hver forelder ikke har mer enn to barn, og fyllingen av nivåene går fra topp til bunn (fra samme nivå - fra venstre til høyre). Binær haug omorganiserer seg selv hver gang elementer legges til eller fjernes fra den. I tilfelle av min-heap, går det minste elementet til roten uavhengig av rekkefølgen på innsettingen. Prioritetskø basert på denne min-heapen. Det betyr at i tilfelle tallkøelementer, vil det første elementet i køen være det minste av disse tallene. Hvis du sletter roten, blir den nest minste en rot.

La oss gå til vårt eksempel.

Trinn 1. Vi setter '5' inn i prioritetskøen. Det blir en rot. Trinn 2. Vi legger til '4' i prioritert kø. 4 <5, så det nye elementet bør være høyere enn det eldre. 4 blir en rot, 5 er dets venstre barn. Nå er datastrukturen i Java [4, 5] Trinn 3. Vi legger til '3'. Midlertidig blir det et rett barn av en rot (4). Men 3 < 4, så vi bør løfte det opp. Bytt 3 og 4. Nå har vi en struktur som [3, 5, 4] Trinn 4. Vi legger til '2'. Det blir et venstrebarn på 5. 2<5, så bytt dem. 2 blir et venstrebarn på 3, 2 < 3, så enda en bytteprosess. Nå har vi en struktur [2,3,4,5] Trinn 5.Vi legger til '1'. Det kommer fra høyre barn av 3 til venstre barn av 2, og går så til roten. Resultatdatastrukturen: [1,2,4,5,3] Fjerningsprosessen starter fra en rot, og den provoserer frem de omvendte prosedyrene. Så først har vi 1 som rot, deretter 2, 3, 4 og til slutt 5. Det er derfor vi bruker fjerning av operasjon poll()

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

vi har "sortert" i lineær sanseutgang:

1
2
3
4
5

Så prioritert kø kan være effektiv for enkelte operasjoner. Det tar O(log N) tid å sette inn og slette hvert element, og du kan få minimalelementet i O(1). Her er hele eksemplet:

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

Det er viktig å forstå at prioriterte køer er basert på binære hauger, så de holder ikke elementer i lineær sortert rekkefølge. Hver vei fra roten til bladet er ordnet, men forskjellige veier fra roten er det ikke. Det betyr at du kan få det minimale elementet i køen veldig raskt.

Hva du bør vite om prioritert kø. Kort liste

• Prioritetskø tillater ikke NULL-objekter.
• Du kan bare legge til sammenlignbare objekter i PriorityQueue.
• Prioritetskø er bygget som en min haug, et slags binært tre. Det minimale elementet er en rot. Objektene i prioritetskøen er sortert som standard i naturlig rekkefølge.
• Du kan bruke Comparator hvis du trenger tilpasset bestilling.
• PriorityQueue er ikke trådsikker, så det er bedre å bruke PriorityBlockingQueue til å jobbe i et samtidig miljø.
• PriorityQueue gir O(log(n))-tid for add- og pollingmetoder og O(1) for å få minimale elementer.