Java Priority Queue: inte en klassisk kö

I den här artikeln lär vi oss en prioritetskö, Java-klass, som implementerar Queue-gränssnitt. Vad kan en programmerare om vanligt kögränssnitt? Först och främst är detta gränssnitt baserat på FIFO-principen eller "först in först ut". Det påminner om en vanlig kö i dess vanliga betydelse. Vill du få kaffe från McDrive? Om din bil är den första nära fönstret, får du ditt kaffe före chauffören som är nästa.

Kögränssnittsdeklaration

public interface Queue<E> extends Collection<E>

Vad är en prioriterad kö

Vad är en prioriterad kö? Först och främst är det en klass som implementerar Queue-gränssnittet i händelse av att man infogar ett element från baksidan och tar bort ett element från huvudet. Det är dock ingen vanlig kö där inne. Ordningen på Java-prioritetsköelement beror på elementens prioritet. Elementet med högst prioritet kommer att flyttas till huvudet i kön. Om du tar bort (serverar) det högst rankade elementet, går det andra till huvudet för att hämta sitt kaffe. Hur bestäms prioritet? Enligt dokumentationen ordnas elementen i prioritetskön enligt deras naturliga ordning, eller av en komparator som tillhandahålls vid kökonstruktionstiden, beroende på vilken konstruktör som används. En prioritetskö baserad på en prioritetsminhög. Det betyder att i fallet med nummerköelement, det första elementet i kön kommer att vara det minimala av dessa nummer. Ganska ofta efter att ha läst den här definitionen börjar rookiestudenter att tro att prioritetskön är sorterad i linjär mening. Det vill säga, om vi använder en kö vars element är naturliga tal, så kommer det första elementet att vara det minsta och det sista - det största. Detta är inte helt sant. För att förstå hur prioritetskön faktiskt fungerar och vad den ger måste du ta reda på hur högen fungerar. Vi överväger den interna strukturen för prioritetskön med ett exempel lite senare. Låt oss nu uppehålla oss vid dess yttre attribut. då kommer det första elementet att vara det minsta, och det sista - det största. Detta är inte helt sant. För att förstå hur prioritetskön faktiskt fungerar och vad den ger måste du ta reda på hur högen fungerar. Vi överväger den interna strukturen för prioritetskön med ett exempel lite senare. Låt oss nu uppehålla oss vid dess yttre attribut. då kommer det första elementet att vara det minsta, och det sista - det största. Detta är inte helt sant. För att förstå hur prioritetskön faktiskt fungerar och vad den ger måste du ta reda på hur högen fungerar. Vi överväger den interna strukturen för prioritetskön med ett exempel lite senare. Låt oss nu uppehålla oss vid dess yttre attribut.

PriorityQueue-klasskonstruktörer och deklaration

PriorityQueue-klassen tillhandahåller 6 olika sätt att konstruera en prioritetskö i Java.

• PriorityQueue() - tom kö med standardinledande kapacitet (11) som ordnar dess element enligt deras naturliga ordning.
• PriorityQueue(Collection c) - tom kö som innehåller elementen i den angivna samlingen.
• PriorityQueue(int initialCapacity) - tom kö med den specificerade initiala kapaciteten som ordnar dess element enligt deras naturliga ordning.
• PriorityQueue(int initialCapacity, Comparator comparator) - tom kö med den specificerade initiala kapaciteten som ordnar sina element enligt den specificerade komparatorn.
• PriorityQueue(PriorityQueue c) - tom kö som innehåller elementen i den angivna prioritetskön.
• PriorityQueue(SortedSet c) - tom kö som innehåller elementen i den angivna sorterade uppsättningen.

Prioritetskö i Java deklareras på följande sätt:

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

Skapar PriorityQueue

Låt oss skapa en prioriterad kö av heltal. Implementering av prioriterad kö, Java-kod:

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

Vi har skapat en prioriterad kö utan argument. I det här fallet är huvudet för prioritetskön det minsta antalet av kön. Om du tar bort huvudet kommer nästa minsta element att ta denna plats. Så du kan ta bort element från kön i stigande ordning. Om det behövs kan du ändra principen för beställning med hjälp av Comparator-gränssnittet.

Java PriorityQueue-metoder

PriorityQueue Java-klassen har viktiga metoder för att lägga till, ta bort och kontrollera element.

Infoga element i Priority Queue

• boolean add(object) infogar det angivna elementet i prioritetskön. Returnerar sant vid framgång. Om kön är full, ger metoden ett undantag.
• boolean offer(object) infogar det angivna elementet i denna prioritetskö. Om kön är full returnerar metoden false.

Du kan använda båda tilläggsoperationerna, det finns inga skillnader för de flesta fall. Här är ett litet exempel på att initiera och lägga till element i prioritetskön.

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

Utgången är:

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

Ordningen på elementen verkar vara konstig, vi ska förklara det senare.

Hämta och ta bort element från Priority Queue

• boolean remove(object) tar bort en enda instans av det angivna elementet från den här kön, om det finns.
• Object poll() hämtar och tar bort huvudet på denna kö. Returnerar null om kön är tom.
• void clear() tar bort alla element från prioritetskön.
• Object element() hämtar huvudet på denna kö utan att ta bort det. Kastar NoSuchElementException om kön är tom.
• Object peek() hämtar huvudet i kön utan att ta bort det. Returnerar null om kön är 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());
    }
}

Utgången:

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 kanske ser leder ett försök att skriva ut huvudet på den tomma kön med metoden element() till NoSuchElementexception .

PriorityQueue Comparator

• Comparator comparator() returnerar komparatorn som använde för att beställa elementen i kön. Returnerar null om kön är sorterad enligt den naturliga ordningen av dess element.

Java-prioritetskö, exempel med komparator

Vi använde naturlig (stigande) ordning i kodexemplen ovan, men ibland borde vi ändra det. Här är ett exempel på Java priority queue, där vi skapar vår egen interna komparatorklass som implementerar Comparator-gränssnittet. Vår komparator kommer att sortera element från de största till de minsta.

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

Utgången:

the head of Queue = 5
5
4
3
2
1

Köhuvudet är nu inte det minimala, utan det maximala elementet, och ordningen ändrades till omvänd.

Itererar över PriorityQueue med iterator

ProrityQueue är en del av samlingsramverket och implementerar Iterable<>- gränssnittet. För att iterera över element i en prioritetskö kan du använda metoden iterator() . Här är ett exempel:

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

Utgången:

1 2 4 5 3 

Fler PriorityQueue-metoder

• boolean innehåller(Objekt o) returnerar sant om kön innehåller o-elementet.
• int size() returnerar antalet element i denna kö.
• Object[] toArray() returnerar en array som innehåller alla elementen i den här kön.

Här är ett exempel:

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

Utgången:

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

Om du öppnar priorityqueue java 8-dokumentationen, hittar du där nästa definition: En obegränsad prioritetskö baserad på en prioritetshög. Elementen i prioritetskön är ordnade enligt deras naturliga ordning, eller av en komparator som tillhandahålls vid kökonstruktionstiden, beroende på vilken konstruktör som används. En prioritetskö tillåter inte null-element. En prioritetskö som förlitar sig på naturlig ordning tillåter inte heller infogning av icke-jämförbara objekt (att göra det kan resultera i ClassCastException). Hög är ett mycket viktigt ord här. Den förklarar egenskaperna för beställning av Priority Queue-element.

Principen för PriorityQueue-arbete: Binary Heap

Låt oss börja med ett exempel. Låt oss skapa två objekt som implementerar Queue-gränssnittet. En av dem LinkedList, den andra — PriorityQueue. Båda har 5 element av heltal (1,2,3,4 och 5) och vi börjar lägga in elementen i våra köer från det största till det minsta. Så, den första kommer 5, sedan 4, 3, 2 och den sista blir 1. Skriv sedan ut båda listorna för att kolla beställningen.

   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 att dessa kod fungerar är följande:

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

Tja, länkad listordning är förutsägbar och begriplig. Den är beställd enligt FIFO-principen. Vi började med 5, så detta element är det allra första i raden, går sedan 4 och så vidare. Vad kan vi berätta om prioriterad köordning? Docs sa att elementen i prioritetskön är ordnade enligt deras naturliga ordning, eller av en komparator som tillhandahålls vid kökonstruktionstiden. Denna ordning verkar dock inte vara "naturlig" i linjär sorteringsbetydelse. Vi förväntar oss hellre [1, 2, 3, 4, 5], inte [1, 2, 4, 5, 3]. För att förstå varför ordningen för hämtning är som den är, bör vi komma ihåg den prioriterade kön baserad på en hög. Vad är högen? Det är en datastruktur baserad på binärt träd. Högens huvudsakliga egenskap: varje förälders prioritet är större än dess barns prioriteringar. Låt mig påminna dig om att ett träd kallas en fullständig binär om varje förälder inte har fler än två barn, och fyllningen av nivåerna går från topp till botten (från samma nivå - från vänster till höger). Binary heap omorganiserar sig själv varje gång element läggs till eller tas bort från den. Vid min-hög går det minsta elementet till roten oavsett i vilken ordning det infogas. Prioriterad kö baserat på denna min-hög. Det betyder att i fallet med nummerköelement kommer det första elementet i kön att vara det minimala av dessa nummer. Om du tar bort roten blir den näst minsta en rot.

Låt oss vända oss till vårt exempel.

Steg 1. Vi lägger "5" i prioritetskön. Det blir en rot. Steg 2. Vi lägger till "4" i prioritetskön. 4 <5, så det nya elementet bör vara högre än det äldre. 4:an blir en rot, 5:an är dess vänstra barn. Nu är datastrukturen i Java [4, 5] Steg 3. Vi lägger till '3'. Tillfälligt blir det ett rätt barn till en rot (4). Dock 3 < 4, så vi borde lyfta upp det. Byt 3 och 4. Nu har vi en struktur som [3, 5, 4] Steg 4. Vi lägger till '2'. Det blir ett vänsterbarn på 5. 2<5, så byt ut dem. 2 blir ett vänsterbarn på 3, 2 < 3, så ytterligare en utbytesprocess. Nu har vi en struktur [2,3,4,5] Steg 5.Vi lägger till "1". Det kommer från höger barn av 3 till vänster barn av 2, och går sedan till roten. Resultatdatastrukturen: [1,2,4,5,3] Borttagningsprocessen startar från en rot och provocerar de omvända procedurerna. Så först har vi 1 som en rot, sedan 2, 3, 4 och till sist 5. Det är därför vi använder removing operation poll()

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

vi har "sorterat" i linjär meningsutgång:

1
2
3
4
5

Så prioriterad kö kan vara effektiv för vissa operationer. Det tar O(log N) tid att infoga och ta bort varje element, och du kan få det minimala elementet i O(1). Här är det fullständiga exemplet:

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 är viktigt att förstå att prioriterade köer är baserade på binära högar, så de håller inte element i linjär sorterad ordning. Varje väg från roten till bladet är ordnad, men olika vägar från roten är det inte. Det betyder att du kan få den minimala delen av kön mycket snabbt.

Vad du bör veta om prioriterad kö. Kort lista

• Prioritetskö tillåter inte NULL-objekt.
• Du kan bara lägga till jämförbara objekt i PriorityQueue.
• Prioritetskö är byggd som en minhög, ett slags binärt träd. Det minimala elementet är en rot. Objekten i prioritetskön är ordnade som standard i naturlig ordning.
• Du kan använda Comparator om du behöver anpassad beställning.
• PriorityQueue är inte trådsäker, så det är bättre att använda PriorityBlockingQueue för att arbeta i en samtidig miljö.
• PriorityQueue ger O(log(n))-tid för add- och pollmetoder och O(1) för att få minimala element.