Java Priority Queue: ikke en klassisk kø

I denne artikel lærer vi en prioritetskø, Java-klasse, der implementerer Queue-interface. Hvad ved en programmør om almindelig kø-grænseflade? Først og fremmest er denne grænseflade baseret på FIFO-princippet eller "først ind først ud". Det minder om en almindelig kø i sin almindelige betydning. Vil du have kaffe fra McDrive? Hvis din bil er den første i nærheden af ​​vinduet, får du din kaffe før chaufføren, der er den næste.

Køgrænsefladeerklæring

public interface Queue<E> extends Collection<E>

Hvad er en prioriteret kø

Hvad er en prioriteret kø? Først og fremmest er det en klasse, der implementerer Queue-grænsefladen i tilfælde af at indsætte et element fra bagsiden og fjerne et element fra hovedet. Det er dog ikke en sædvanlig kø indenfor. Rækkefølgen af ​​Java-prioritetskøelementer afhænger af elementernes prioritet. Elementet med højest prioritet vil blive flyttet til toppen af ​​køen. Hvis du sletter (serverer) det højest rangerede element, går det andet til hovedet for at få sin kaffe. Hvordan bestemmes prioritet? I henhold til dokumentationen er elementerne i prioritetskøen ordnet efter deres naturlige rækkefølge, eller af en komparator, der stilles til rådighed ved køkonstruktionstidspunktet, afhængig af hvilken konstruktør der anvendes. En prioritetskø baseret på en prioritet min heap. Det betyder, at i tilfælde af talkøelementer, det første element i køen vil være det minimale af disse tal. Temmelig ofte efter at have læst denne definition begynder nybegyndere at tro, at prioritetskøen er sorteret i lineær forstand. Det vil sige, hvis vi f.eks. bruger en kø, hvis elementer er naturlige tal, så vil det første element være det mindste, og det sidste - det største. Dette er ikke helt rigtigt. For at forstå, hvordan prioritetskøen faktisk fungerer, og hvad den giver, skal du finde ud af, hvordan heapen fungerer. Vi overvejer den interne struktur af prioritetskøen ved at bruge et eksempel lidt senere. Lad os nu dvæle ved dets ydre egenskaber. så vil det første element være det mindste, og det sidste - det største. Dette er ikke helt rigtigt. For at forstå, hvordan prioritetskøen faktisk fungerer, og hvad den giver, skal du finde ud af, hvordan heapen fungerer. Vi overvejer den interne struktur af prioritetskøen ved at bruge et eksempel lidt senere. Lad os nu dvæle ved dets ydre egenskaber. så vil det første element være det mindste, og det sidste - det største. Dette er ikke helt rigtigt. For at forstå, hvordan prioritetskøen faktisk fungerer, og hvad den giver, skal du finde ud af, hvordan heapen fungerer. Vi overvejer den interne struktur af prioritetskøen ved at bruge et eksempel lidt senere. Lad os nu dvæle ved dets ydre egenskaber.

PriorityQueue klasse konstruktører og erklæring

PriorityQueue-klassen giver 6 forskellige måder at konstruere en prioritetskø i Java.

• PriorityQueue() - tom kø med standardindledende kapacitet (11), der bestiller sine elementer i henhold til deres naturlige rækkefølge.
• PriorityQueue(Collection c) - tom kø, der indeholder elementerne i den angivne samling.
• PriorityQueue(int initialCapacity) - tom kø med den angivne startkapacitet, der bestiller sine elementer i henhold til deres naturlige rækkefølge.
• PriorityQueue(int initialCapacity, Comparator comparator) - tom kø med den specificerede initiale kapacitet, der sorterer sine elementer i henhold til den specificerede komparator.
• PriorityQueue(PriorityQueue c) - tom kø, der indeholder elementerne i den angivne prioritetskø.
• PriorityQueue(SortedSet c) - tom kø, der indeholder elementerne i det angivne sorterede sæt.

Prioritetskø i Java erklæres på næste måde:

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

Oprettelse af PriorityQueue

Lad os oprette en prioriteret kø af heltal. Implementering af prioriteret kø, Java-kode:

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

Vi har oprettet en prioriteret kø uden argumenter. I dette tilfælde er hovedet af prioritetskøen det minimale antal af køen. Hvis du fjerner hovedet, vil det næstmindste element tage denne plads. Så du kan fjerne elementer fra køen i stigende rækkefølge. Om nødvendigt kan du ændre bestillingsprincippet ved hjælp af Comparator-grænsefladen.

Java PriorityQueue-metoder

PriorityQueue Java-klassen har vigtige metoder til at tilføje, fjerne og kontrollere elementer.

Indsæt elementer i prioriteret kø

• boolean add(object) indsætter det angivne element i prioritetskøen. Returnerer sandt i tilfælde af succes. Hvis køen er fuld, giver metoden en undtagelse.
• boolesk tilbud(objekt) indsætter det angivne element i denne prioritetskø. Hvis køen er fuld, returnerer metoden falsk.

Du kan bruge begge tilføjelsesoperationer, der er ingen forskelle for de fleste tilfælde. Her er et lille eksempel på initiering og tilføjelse af elementer i prioriteret 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);
    }
}

Udgangen er:

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

Rækkefølgen af ​​elementerne ser ud til at være underlig, vi forklarer det senere.

Hentning og fjernelse af elementer fra Prioritetskøen

• boolean remove(object) fjerner en enkelt forekomst af det angivne element fra denne kø, hvis det er til stede.
• Object poll() henter og fjerner hovedet af denne kø. Returnerer null, hvis køen er tom.
• void clear() fjerner alle elementer fra prioritetskøen.
• Object element() henter hovedet af denne kø uden at fjerne det. Kaster NoSuchElementException , hvis køen er tom.
• Object peek() henter hovedet i køen uden at fjerne det. 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());
    }
}

Udgangen:

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 måske kan se, fører et forsøg på at udskrive hovedet af den tomme kø ved hjælp af element() metoden til NoSuchElementexception .

PriorityQueue Comparator

• Comparator comparator() returnerer den komparator, der bruges til at bestille elementerne i køen. Returnerer null, hvis køen er sorteret efter den naturlige rækkefølge af dens elementer.

Java-prioritetskø, eksempel med komparator

Vi brugte naturlig (stigende) rækkefølge i kodeeksemplerne ovenfor, men nogle gange bør vi ændre det. Her er et eksempel på Java-prioritetskø, hvor vi opretter vores egen interne komparatorklasse, der implementerer Comparator-grænsefladen. Vores komparator vil sortere elementer fra de største til de mindste.

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

Output:

the head of Queue = 5
5
4
3
2
1

Head of Queue er nu ikke det minimale, men maksimale element, og rækkefølgen blev ændret til omvendt.

Itererer over PriorityQueue ved hjælp af iterator

ProrityQueue er en del af Collection frameworket og implementerer Iterable<>- grænsefladen. For at iterere over elementer i en prioritetskø kan du bruge 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() + " ");
       }
   }
}

Udgangen:

1 2 4 5 3 

Flere PriorityQueue-metoder

• boolean contains(Object o) returnerer sand, hvis køen indeholder o-elementet.
• int size() returnerer antallet af elementer i denne kø.
• Objekt[] toArray() returnerer et array, der indeholder alle elementerne i denne kø.

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

Udgangen:

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 definition

Hvis du åbner priorityqueue java 8-dokumentationen, vil du finde den næste definition der: En ubegrænset prioritetskø baseret på en prioritetsbunke. Elementerne i prioritetskøen er ordnet i henhold til deres naturlige rækkefølge, eller af en komparator, der leveres ved køens konstruktionstidspunkt, afhængigt af hvilken konstruktør der bruges. En prioritetskø tillader ikke null-elementer. En prioritetskø, der er afhængig af naturlig rækkefølge, tillader heller ikke indsættelse af ikke-sammenlignelige objekter (det kan resultere i ClassCastException). Heap er et meget vigtigt ord her. Det forklarer egenskaberne ved bestilling af Priority Queue-elementer.

Princippet om PriorityQueue-arbejde: Binary Heap

Lad os starte med et eksempel. Lad os oprette to objekter, der implementerer Kø-grænsefladen. En af dem LinkedList, den anden — PriorityQueue. Begge har 5 elementer af heltal (1,2,3,4 og 5), og vi begynder at sætte elementerne ind i vores køer fra den største til den mindste. Så den første kommer 5, derefter 4, 3, 2 og den sidste bliver 1. Udskriv derefter begge lister for at tjekke ordren ud.

   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 af disse kodearbejde er det næste:

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

Nå, linkedlist rækkefølgen er forudsigelig og forståelig. Den er bestilt efter FIFO-princippet. Vi startede med 5, så dette element er det allerførste i rækken, går derefter 4 og så videre. Hvad kan vi fortælle om prioriteret købestilling? Docs sagde, at elementerne i prioritetskøen er ordnet i overensstemmelse med deres naturlige rækkefølge eller af en komparator, der leveres ved køens opbygningstidspunkt. Denne rækkefølge ser dog ikke ud til at være "naturlig" i lineær sorteringsbetydning. Vi vil hellere forvente [1, 2, 3, 4, 5], ikke [1, 2, 4, 5, 3]. For at forstå, hvorfor rækkefølgen for hentning er, som den er, bør vi huske den prioriterede kø baseret på en heap. Hvad er dyngen? Det er en datastruktur baseret på binært træ. Hobens hovedegenskab: hver forælders prioritet er større end dens børns prioriteter. Lad mig minde dig om, at et træ kaldes en komplet binær, hvis hver forælder ikke har mere end to børn, og fyldningen af ​​niveauerne går fra top til bund (fra samme niveau - fra venstre mod højre). Binær heap reorganiserer sig selv, hver gang elementer tilføjes eller fjernes fra den. I tilfælde af min-heap går det mindste element til roden uanset rækkefølgen af ​​dets indsættelse. Prioritetskø baseret på denne min-heap. Det betyder, at i tilfælde af talkøelementer, vil det første element i køen være det minimale af disse tal. Hvis du sletter roden, bliver den næstmindste en rod.

Lad os vende tilbage til vores eksempel.

Trin 1. Vi sætter '5' i prioritetskøen. Det bliver en rod. Trin 2. Vi tilføjer '4' til prioriteret kø. 4 <5, så det nye element skal være højere end det ældre. 4'eren bliver til en rod, 5'eren er dens venstre barn. Nu er datastrukturen i Java [4, 5] Trin 3. Vi tilføjer '3'. Midlertidigt bliver det et ret barn af en rod (4). Dog 3 < 4, så vi bør løfte det op. Byt 3 og 4. Nu har vi en struktur som [3, 5, 4] Trin 4. Vi tilføjer '2'. Det bliver et venstrebarn på 5. 2<5, så byt dem. 2 bliver et venstre barn på 3, 2 < 3, så endnu en udvekslingsproces. Nu har vi en struktur [2,3,4,5] Trin 5.Vi tilføjer '1'. Det kommer fra højre barn af 3 til venstre barn af 2, og går så til roden. Resultatdatastrukturen: [1,2,4,5,3] Fjernelsesprocessen starter fra en rod, og den fremkalder de omvendte procedurer. Så først har vi 1 som rod, derefter 2, 3, 4 og til sidst 5. Det er derfor, at vi bruger fjernelse af operation poll()

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

vi har "sorteret" i lineær sanseoutput:

1
2
3
4
5

Så prioriteret kø kan være effektiv for nogle operationer. Det tager O(log N) tid at indsætte og slette hvert element, og du kan få det minimale element i O(1). Her er det fulde eksempel:

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 vigtigt at forstå, at prioritetskøer er baseret på binære heaps, så de holder ikke elementer i lineær sorteret rækkefølge. Hver vej fra roden til bladet er ordnet, men forskellige veje fra roden er det ikke. Det betyder, at du kan få det minimale element i køen meget hurtigt.

Hvad du bør vide om prioriteret kø. Kort liste

• Prioritetskø tillader ikke NULL-objekter.
• Du kan kun tilføje sammenlignelige objekter til PriorityQueue.
• Prioritetskø er bygget som en min hob, en slags binært træ. Det minimale element er en rod. Objekterne i prioritetskøen er som standard ordnet i naturlig rækkefølge.
• Du kan bruge Comparator, hvis du har brug for tilpasset bestilling.
• PriorityQueue er ikke trådsikker, så det er bedre at bruge PriorityBlockingQueue til at arbejde i et samtidig miljø.
• PriorityQueue giver O(log(n)) tid til tilføjelse og pollingsmetoder og O(1) for at få minimale elementer.