Deklaracja interfejsu kolejki
public interface Queue<E> extends Collection<E>
Czym jest kolejka priorytetowa (ang. Priority Queue)?

Czym jest kolejka priorytetowa? Przede wszystkim jest to klasa, która implementuje interfejs kolejki w przypadku wstawiania elementu z tyłu i usuwania elementu z przodu. Jednak w rzeczywistości nie jest to zwykła kolejka. Kolejność elementów kolejki priorytetowej Java zależy od priorytetu elementów. Element o najwyższym priorytecie zostanie przeniesiony na początek kolejki. Jeśli usuniesz (obsłużysz) element o najwyższej randze, drugi pójdzie do przodu po swoją kawę. Jak określany jest priorytet? Zgodnie z dokumentacją elementy kolejki priorytetowej uporządkowane są według ich naturalnej kolejności lub za pomocą komparatora dostarczonego w czasie tworzenia kolejki, w zależności od użytego konstruktora. Kolejka priorytetowa oparta na stercie o priorytecie min. Oznacza to, że w przypadku elementów kolejki liczb, pierwszym elementem kolejki będzie najmniejsza z tych liczb. Dość często po przeczytaniu tej definicji nowicjusze zaczynają myśleć, że kolejka priorytetowa jest sortowana liniowo. Powiedzmy, iż oznacza to, że jeśli używamy kolejki, której elementami są liczby naturalne to pierwszy element będzie najmniejszy, a ostatni — największy. Nie jest to do końca prawdą. Aby zrozumieć, jak działa kolejka priorytetowa i co ona daje, trzeba zrozumieć, jak działa sterta. Wewnętrzną strukturę kolejki priorytetowej omówimy na przykładzie nieco później. Teraz skupmy się na jej atrybutach zewnętrznych.
Konstruktory i deklaracja klasy PriorityQueue
Klasa PriorityQueue udostępnia 6 różnych sposobów konstruowania kolejek priorytetowych w Javie.- PriorityQueue() — pusta kolejka o domyślnej początkowej pojemności (11), która sortuje swoje elementy zgodnie z ich naturalnym uporządkowaniem.
- PriorityQueue(Collection c) — pusta kolejka zawierająca elementy z podanej kolekcji.
- PriorityQueue(int initialCapacity) — pusta kolejka o podanej pojemności początkowej, która sortuje swoje elementy zgodnie z ich naturalnym uporządkowaniem.
- PriorityQueue(int initialCapacity, Comparator comparator) — pusta kolejka o podanej pojemności początkowej, porządkująca swoje elementy według podanego komparatora.
- PriorityQueue(PriorityQueue c) — pusta kolejka zawierająca elementy z podanej kolejki priorytetowej.
- PriorityQueue(SortedSet c) — pusta kolejka zawierająca elementy z podanego posortowanego zbioru.
public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable
Tworzenie kolejki PriorityQueue
Utwórzmy kolejkę priorytetową złożoną z liczb całkowitych. Implementacja kolejki priorytetowej, kod Java:
PriorityQueue<Integer> numbers = new PriorityQueue<>();
Utworzyliśmy kolejkę priorytetową bez argumentów. W tym przypadku pierwszeństwo w kolejce priorytetowej ma minimalny numer kolejki. Jeśli usuniesz pierwszą liczbę, jej miejsce zajmie kolejny najmniejszy element. W ten sposób można usuwać elementy z kolejki w kolejności rosnącej. W razie potrzeby można zmienić zasadę porządkowania za pomocą interfejsu Comparator.
Metody Java PriorityQueue
Klasa PriorityQueue Java zawiera ważne metody służące do dodawania, usuwania i sprawdzania elementów.Wstawianie elementów do kolejki priorytetowej
- boolean add(object) wstawia określony element do kolejki priorytetowej. Zwraca wartość true w przypadku powodzenia. Jeśli kolejka jest pełna, metoda wyrzuca wyjątek.
- boolean offer(object) wstawia określony element do tej kolejki priorytetowej. Jeśli kolejka jest pełna, metoda zwraca false.
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);
}
}
Wyświetlone zostanie:
Pobieranie i usuwanie elementów z kolejki priorytetowej
- boolean remove(object) usuwa pojedynczą instancję określonego elementu z tej kolejki, jeśli jest ona obecna.
- Object poll() pobiera i usuwa pierwszy element tej kolejki. Zwraca wartość null, jeśli kolejka jest pusta.
- void clear() usuwa wszystkie elementy z kolejki priorytetowej.
- Object element() pobiera pierwszy element tej kolejki, nie usuwając go. Wyrzuca wyjątek NoSuchElementException, jeśli kolejka jest pusta.
- Object peek() pobiera pierwszy element tej kolejki, nie usuwając go. Zwraca wartość null, jeśli kolejka jest pusta.
import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
public static void main(String[] args) {
Queue<Integer> priorityQueue = new PriorityQueue<>();
//wstawianie 5 elementów do kolejki za pomocą add
for (int i = 5; i > 0; i--) {
priorityQueue.add(i);
}
System.out.println("pierwszy element kolejki = " + priorityQueue.peek());
//usuwanie elementu po elemencie z kolejki za pomocą metody poll i wyświetlanie
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
//wstawianie 5 nowych elementów do pustej kolejki przy użyciu offer
for (int i = 10; i > 5; i--) {
priorityQueue.offer(i);
}
System.out.println("aktualny pierwszy element kolejki = " + priorityQueue.peek());
System.out.println("kolejka przed usunięciem 9:");
System.out.println(priorityQueue);
priorityQueue.remove(9);
System.out.println("kolejka po usunięciu 9:");
System.out.println(priorityQueue);
//usunięcie wszystkich elementów z kolejki
priorityQueue.clear();
System.out.println(priorityQueue);
//przy próbie wyświetlenia pierwszego elementu pustej kolejki za pomocą peek otrzymamy null
System.out.println(priorityQueue.peek());
//przy próbie wyświetlenia pierwszego elementu pustej kolejki za pomocą elementu otrzymamy wyjątek
System.out.println(priorityQueue.element());
}
}
Wyświetlone zostanie:
Komparator PriorityQueue
- Comparator comparator() zwraca komparator, który został użyty do uporządkowania elementów w kolejce. Zwraca wartość null, jeśli kolejka jest posortowana zgodnie z naturalną kolejnością jej elementów.
Kolejka priorytetowa w Javie, przykład z komparatorem
W powyższych przykładach zastosowaliśmy kolejność naturalną (rosnącą), ale czasami należy ją zmienić. Oto przykład kolejki priorytetowej w Javie, w którym tworzymy własną wewnętrzną klasę komparatora, implementującą interfejs Comparator. Nasz komparator posortuje elementy od największego do najmniejszego.
import java.util.PriorityQueue;
import java.util.Comparator;
class Priority3 {
public static void main(String[] args) {
// Tworzenie kolejki priorytetowej za pomocą myComparator
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
for (int i = 5; i > 0; i--) {
priorityQueue.add(i);
}
System.out.println("pierwszy element kolejki = " + 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);
//sortowanie elementów od największego do najmniejszego
if (value > 0) {
return -1;
} else if (value < 0) {
return 1;
} else {
return 0;
}
}
}
Wyświetlone zostanie:

Iterowanie po PriorityQueue przy użyciu iteratora
ProrityQueue jest częścią frameworka Collection i implementuje interfejs Iterable<>. Aby iterować po elementach kolejki priorytetowej, można użyć metody iterator(). Oto przykład:
import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
class Priority4 {
public static void main(String[] args) {
// Tworzenie kolejki priorytetowej
Queue<Integer> priorityQueue = new PriorityQueue<>();
//wstawianie 5 elementów do kolejki za pomocą add
for (int i = 5; i > 0; i--) {
priorityQueue.add(i);
}
//Iterowanie za pomocą metody iterator()
Iterator<Integer> iterator = priorityQueue.iterator();
while (iterate.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
}
Wyświetlone zostanie:
Więcej metod PriorityQueue
- boolean contains(Object o) zwraca wartość true, jeśli kolejka zawiera element o.
- int size() zwraca liczbę elementów w tej kolejce.
- Object[] toArray() zwraca tablicę zawierającą wszystkie elementy w tej kolejce.
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("nasza kolejka: " + priorityQueue);
System.out.println("Czy nasza kolejka zawiera 8? " + priorityQueue.contains(8));
System.out.println("Czy nasza kolejka zawiera 5? " + priorityQueue.contains(5));
System.out.println("Ilość elementów kolejki: " + priorityQueue.size());
Object[] myArray = priorityQueue.toArray();
System.out.println("wydruk naszej tablicy:");
for (Object name : myArray) {
System.out.println(name);
}
}
}
Wyświetlone zostanie:
Definicja PriorityQueue Java 8
Jeśli otworzysz dokumentację priorityqueue java 8, znajdziesz w niej następującą definicję: Nieograniczona kolejka priorytetowa oparta na stercie priorytetów. Elementy kolejki priorytetowej są uporządkowane zgodnie z ich naturalnym uporządkowaniem lub za pomocą komparatora podanego w czasie konstruowania kolejki, w zależności od tego, który konstruktor zostanie użyty. Kolejka priorytetowa nie dopuszcza elementów null. Kolejka priorytetowa oparta na naturalnej kolejności również nie pozwala na wstawianie nieporównywalnych obiektów (może to spowodować wystąpienie wyjątku ClassCastException). Sterta jest tu bardzo ważnym słowem. Objaśnia właściwości porządkowania elementów kolejki priorytetowej.Zasada działania PriorityQueue: Sterta binarna
Zacznijmy od przykładu. Utwórzmy dwa obiekty implementujące interfejs kolejki. Jeden z nich to LinkedList, drugi - PriorityQueue. Obie mają po 5 elementów tnteger (1,2,3,4 i 5) i zaczynamy umieszczać elementy w naszych kolejkach od największego do najmniejszego. Tak więc pierwszy to 5, potem 4, 3, 2, natomiast ostatni to 1. Następnie wyświetlić obie listy, aby sprawdzić kolejność.
Queue<Integer> queueL = new LinkedList<>();
for (int i = 5; i > 0; i--) {
queueL.add(i);
}
System.out.println("Kolejka LinkedList (FIFO): " + queueL);
Queue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 5; i > 0; i--) {
priorityQueue.offer(i);
}
System.out.println("PriorityQueue: " + priorityQueue)
Wynikiem działania tych kodów jest:
Przejdźmy do naszego przykładu.
Krok 1. Umieszczamy „5” w kolejce priorytetowej. Staje się korzeniem. Krok 2. Dodajemy „4” do kolejki priorytetowej. 4 <5, więc nowy element powinien być wyżej od starszego. 4 staje się korzeniem, a 5 jest jego lewym dzieckiem. Obecnie struktura danych w Javie to [4, 5]. Krok 3. Dodajemy „3”. Tymczasowo staje się prawym dzieckiem korzenia (4). Jednak 3 < 4, więc należy je podnieść. Wymiana 3 i 4. Teraz mamy strukturę taką jak [3, 5, 4]. Krok 4. Dodajemy „2”. Staje się lewym dzieckiem liczby 5. 2<5, więc zamień je miejscami. 2 staje się lewym dzieckiem 3, 2 < 3, więc jeszcze jeden proces wymiany. Teraz mamy strukturę [2,3,4,5] Krok 5. Dodajemy „1”. Pochodzi od prawego dziecka 3 do lewego dziecka 2, a następnie przechodzi do korzenia. Struktura danych wynikowych: [1,2,4,5,3]
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
mamy „posortowane” dane wyjściowe w sensie liniowym:
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("Drukuje naszą kolejkę LinkedList (FIFO): " + queueL);
Queue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 5; i > 0; i--) {
priorityQueue.offer(i);
}
System.out.println("Drukowanie PriorityQueue (poprzez iterację, bez usuwania elementów): " + priorityQueue);
System.out.println("Drukuje PriorityQueue za pomocą poll() (przez pobranie): " );
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
}
}
Drukuje naszą kolejkę LinkedList (FIFO): [5, 4, 3, 2, 1]
drukowanie PriorityQueue (poprzez iterację, bez usuwania elementów): [1, 2, 4, 5, 3]
Drukuje naszą PriorityQueue za pomocą poll() (przez pobranie):
1
2
3
4
5
Ważne jest, aby zrozumieć, że kolejki priorytetowe są oparte na stertach binarnych, a więc nie przechowują elementów w porządku liniowym. Każda droga od korzenia do liścia jest uporządkowana, natomiast różne drogi wyrastające z korzenia nie. Oznacza to, że można bardzo szybko uzyskać minimalny element kolejki.
Co należy wiedzieć o kolejce priorytetowej. Skrócona lista
- Kolejka priorytetowa nie dopuszcza obiektów NULL.
- Do kolejki PriorityQueue można dodawać tylko porównywalne obiekty.
- Kolejka priorytetowa jest zbudowana jako sterta min, rodzaj drzewa binarnego. Elementem minimalnym jest korzeń. Obiekty kolejki priorytetowej są domyślnie uporządkowane w naturalnej kolejności.
- W razie potrzeby utworzenia uporządkowania niestandardowego, można użyć komparatora.
- PriorityQueue nie jest bezpieczny dla wątków, więc do pracy w środowisku współbieżnym lepiej użyć PriorityBlockingQueue.
- PriorityQueue zapewnia czas O(log(n)) dla metod add i poll oraz O(1) na uzyskanie minimalnych elementów.
GO TO FULL VERSION