Kolejka priorytetowa w Javie: nie jest to klasyczna kolejka

W tym artykule poznamy kolejkę priorytetową, klasę Javy, która implementuje interfejs Queue. Co programista wie o zwykłym interfejsie kolejki (ang. Queue Interface)? Przede wszystkim interfejs ten opiera się na zasadzie FIFO czyli „pierwsze weszło, pierwsze wyszło”. Przypomina to zwykłą kolejkę w jej potocznym znaczeniu. Chcesz kawę z McDrive'a? Jeśli twój samochód jest bliżej okienka, dostaniesz kawę wcześniej niż następny kierowca.

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.

Kolejka priorytetowa w Javie deklarowana jest w następujący sposób:

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.

Można używać obu operacji dodawania, bo w większości przypadków nie ma między nimi różnic. Oto mały przykład inicjalizacji i dodawania elementów do kolejki priorytetowej.

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:

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

Kolejność elementów może wydawać się dziwna, ale wyjaśnimy to później.

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

Wyświetlone zostanie:

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)

Jak można zauważyć, próba wydruku pierwszego elementu pustej kolejki za pomocą metody element() prowadzi do NoSuchElementexception.

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

Wyświetlone zostanie:

the head of Queue = 5
5
4
3
2
1

Pierwszymkolejce nie jest teraz element minimalny, lecz maksymalny, a kolejność została zmieniona na odwróconą.

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

Wyświetlone zostanie:

1 2 4 5 3 

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.

Oto przykład:

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

Wyświetlone zostanie:

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

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("LinkedList Queue (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:

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

Cóż, kolejność na linkedlist jest przewidywalna i zrozumiała. Jest uporządkowana zgodnie z zasadą FIFO. Zaczęliśmy od 5, więc ten element jest pierwszy w kolejce, następnie 4 i tak dalej. Co można powiedzieć o kolejności w kolejce priorytetowej? Według dokumentacji elementy kolejki priorytetowej są uporządkowane zgodnie z ich naturalną kolejnością lub za pomocą komparatora podanego w czasie konstruowania kolejki. Jednak ta kolejność nie wydaje się być „naturalna” w sensie sortowania liniowego. Raczej spodziewalibyśmy się [1, 2, 3, 4, 5], a nie [1, 2, 4, 5, 3]. Aby zrozumieć, dlaczego kolejność pobierania jest taka, jaka jest, powinniśmy przypomnieć sobie, że kolejka priorytetowa bazuje na stercie. Co to jest sterta? Jest to struktura danych oparta na drzewie binarnym. Główna właściwość sterty: priorytet każdego rodzica jest większy niż priorytety jego dzieci. Przypomnę, że drzewo nazywa się kompletnie binarnym, jeśli każdy rodzic ma nie więcej niż dwoje dzieci, a wypełnienie poziomów przebiega od góry do dołu (z tego samego poziomu — od lewej do prawej). Sterta binarna reorganizuje się za każdym razem, gdy elementy są do niej dodawane lub usuwane z niej. W przypadku sterty min najmniejszy element trafia do korzenia niezależnie od kolejności jego wstawiania. Kolejka priorytetowa na podstawie tej sterty min. Oznacza to, że w przypadku elementów kolejki liczb, pierwszym elementem kolejki będzie najmniejsza z tych liczb. Jeśli usuniesz korzeń, następny najmniejszy staje się korzeniem.

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] Proces usuwania rozpoczyna się od korzenia i wywołuje procedury odwrotne. Zatem najpierw mamy 1 jako korzeń, potem 2, 3, 4 i wreszcie 5. Dlatego właśnie używamy operacji usuwania poll()

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

mamy „posortowane” dane wyjściowe w sensie liniowym:

1
2
3
4
5

Dlatego kolejka priorytetowa może być skuteczna w przypadku niektórych operacji. Wstawianie i usuwanie każdego elementu zajmuje czas O(log N), a minimalny element można uzyskać w czasie O(1). Oto pełny przykład:

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

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.