A PriorityQueue używa się, gdy obiekty mają być przetwarzane na podstawie priorytetu. Wiadomo, że A Kolejka działa zgodnie z algorytmem First-In-First-Out, ale czasami elementy kolejki muszą zostać przetworzone zgodnie z priorytetem, wtedy do gry wchodzi PriorityQueue.
PriorityQueue opiera się na stercie priorytetów. Elementy kolejki priorytetowej uporządkowane są według kolejności naturalnej lub według komparatora podawanego w czasie budowy kolejki, w zależności od użytego konstruktora.
W poniższej kolejce priorytetów najwyższy priorytet będzie miał element o maksymalnej wartości ASCII.
Deklaracja:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
Klasa implementuje Możliwość serializacji , Iterowalne , Kolekcja , Kolejka interfejsy.
Kilka ważne punkty w kolejce priorytetowej są następujące:
- PriorityQueue nie zezwala na wartość null.
- Nie możemy utworzyć kolejki priorytetów obiektów, które są nieporównywalne
- PriorityQueue to kolejki niezwiązane.
- Nagłówek tej kolejki jest najmniejszym elementem w odniesieniu do określonej kolejności. Jeśli wiele elementów ma najmniejszą wartość, reszka jest jednym z tych elementów — remisy są przerywane arbitralnie.
- Ponieważ PriorityQueue nie jest bezpieczny dla wątków, Java udostępnia klasę PriorityBlockingQueue, która implementuje interfejs BlockingQueue do użycia w wielowątkowym środowisku Java.
- Operacje pobierania kolejki odpytują, usuwają, podglądają i uzyskują dostęp do elementu na początku kolejki.
- Zapewnia czas O(log(n)) dla metod dodawania i odpytywania.
- Dziedziczy metody z StreszczenieKolejka , Kolekcja abstrakcyjna , Kolekcja, I Obiekt klasa.
Konstruktorzy:
1. Kolejka priorytetów(): Tworzy PriorityQueue z domyślną początkową pojemnością (11), która porządkuje swoje elementy zgodnie z ich naturalną kolejnością.
Kolejka Priorytetów pq = nowa Kolejka Priorytetów();
2. Kolejka priorytetów (kolekcja c): Tworzy PriorityQueue zawierającą elementy w określonej kolekcji.
Kolejka Priorytetów pq = nowa Kolejka Priorytetów (Kolekcja c);
3. Kolejka priorytetów (int początkowa pojemność) : Tworzy kolejkę PriorityQueue o określonej początkowej pojemności, która porządkuje elementy zgodnie z ich naturalnym porządkiem.
Kolejka Priorytetów pq = nowa Kolejka Priorytetów(int początkowyPojemność);
4. PriorityQueue(int początkowyPojemność, komparator komparatora): Tworzy PriorityQueue o określonej pojemności początkowej, która porządkuje swoje elementy zgodnie z określonym komparatorem.
PriorityQueue pq = new PriorityQueue(int początkowyCapacity, komparator komparatora);
5. Kolejka priorytetów(Kolejka priorytetów c) : Tworzy PriorityQueue zawierającą elementy w określonej kolejce priorytetowej.
Kolejka Priorytetów pq = nowa Kolejka Priorytetów(Kolejka Priorytetów c);
6. Kolejka priorytetów (SortedSet c) : Tworzy kolejkę PriorityQueue zawierającą elementy w określonym posortowanym zestawie.
PriorityQueue pq = nowa PriorityQueue(SortedSet c);
7. PriorityQueue(Komparator): Tworzy PriorityQueue z domyślną pojemnością początkową i której elementy są uporządkowane zgodnie z określonym komparatorem.
Kolejka Priorytetów pq = nowa Kolejka Priorytetów (Komparator c);
Przykład:
Poniższy przykład wyjaśnia następujące podstawowe operacje na kolejce priorytetowej.
wątek.zniszcz
- boolean add(E element): Ta metoda wstawia określony element do tej kolejki priorytetowej.
- public peek(): Ta metoda pobiera, ale nie usuwa, nagłówek tej kolejki lub zwraca wartość null, jeśli kolejka jest pusta.
- public poll(): Ta metoda pobiera i usuwa początek tej kolejki lub zwraca wartość null, jeśli kolejka jest pusta.
Jawa
// Java program to demonstrate the> // working of PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String args[])> >{> >// Creating empty priority queue> >PriorityQueue pQueue =>new> PriorityQueue();> >// Adding items to the pQueue using add()> >pQueue.add(>10>);> >pQueue.add(>20>);> >pQueue.add(>15>);> >// Printing the top element of PriorityQueue> >System.out.println(pQueue.peek());> >// Printing the top element and removing it> >// from the PriorityQueue container> >System.out.println(pQueue.poll());> >// Printing the top element again> >System.out.println(pQueue.peek());> >}> }> |
>
>Wyjście
10 10 15>
Operacje na PriorityQueue
Zobaczmy jak wykonać kilka często używanych operacji na klasie Priority Queue.
1. Dodawanie elementów: Aby dodać element do kolejki priorytetowej możemy skorzystać z metody add(). Zamówienie wstawiania nie jest zachowywane w kolejce PriorityQueue. Elementy są przechowywane w kolejności priorytetów, która domyślnie jest rosnąca.
Jawa
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >for>(>int> i=>0>;i<>3>;i++){> >pq.add(i);> >pq.add(>1>);> >}> >System.out.println(pq);> >}> }> |
>
>Wyjście
[0, 1, 1, 1, 2, 1]>
Nie otrzymamy posortowanych elementów poprzez wydruk PriorityQueue.
Jawa
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> > >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> > >System.out.println(pq);> >}> }> |
>
>Wyjście
[For, Geeks, Geeks]>
2. Usuwanie elementów: Aby usunąć element z kolejki priorytetowej, możemy skorzystać z metody usuwania(). Jeżeli takich obiektów jest wiele, to pierwsze wystąpienie obiektu jest usuwane. Oprócz tego metoda poll() służy również do usunięcia nagłówka i jego zwrotu.
Jawa
// Java program to remove elements> // from a PriorityQueue> import> java.util.*;> import> java.io.*;> public> class> PriorityQueueDemo {> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'Initial PriorityQueue '> + pq);> >// using the method> >pq.remove(>'Geeks'>);> >System.out.println(>'After Remove - '> + pq);> >System.out.println(>'Poll Method - '> + pq.poll());> >System.out.println(>'Final PriorityQueue - '> + pq);> >}> }> |
>
>Wyjście
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Dostęp do elementów: Ponieważ w kolejce obowiązuje zasada First In First Out, możemy uzyskać dostęp tylko do początku kolejki. Aby uzyskać dostęp do elementów z kolejki priorytetowej, możemy skorzystać z metody peek().
Jawa
// Java program to access elements> // from a PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String[] args)> >{> >// Creating a priority queue> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'PriorityQueue: '> + pq);> >// Using the peek() method> >String element = pq.peek();> >System.out.println(>'Accessed Element: '> + element);> >}> }> |
>
>Wyjście
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Iteracja kolejki priorytetowej: Istnieje wiele sposobów iteracji po PriorityQueue. Najbardziej znanym sposobem jest konwersja kolejki na tablicę i przechodzenie za pomocą pętli for. Jednakże kolejka ma również wbudowany iterator, którego można używać do iteracji po kolejce.
Jawa
// Java program to iterate elements> // to a PriorityQueue> import> java.util.*;> public> class> PriorityQueueDemo {> >// Main Method> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >Iterator iterator = pq.iterator();> >while> (iterator.hasNext()) {> >System.out.print(iterator.next() +>' '>);> >}> >}> }> |
>
>Wyjście
For Geeks Geeks>
Przykład:
Jawa
import> java.util.PriorityQueue;> public> class> PriorityQueueExample {> >public> static> void> main(String[] args) {> > >// Create a priority queue with initial capacity 10> >PriorityQueue pq =>new> PriorityQueue(>10>);> > >// Add elements to the queue> >pq.add(>3>);> >pq.add(>1>);> >pq.add(>2>);> >pq.add(>5>);> >pq.add(>4>);> > >// Print the queue> >System.out.println(>'Priority queue: '> + pq);> > >// Peek at the top element of the queue> >System.out.println(>'Peek: '> + pq.peek());> > >// Remove the top element of the queue> >pq.poll();> > >// Print the queue again> >System.out.println(>'Priority queue after removing top element: '> + pq);> > >// Check if the queue contains a specific element> >System.out.println(>'Does the queue contain 3? '> + pq.contains(>3>));> > >// Get the size of the queue> >System.out.println(>'Size of queue: '> + pq.size());> > >// Remove all elements from the queue> >pq.clear();> > >// Check if the queue is empty> >System.out.println(>'Is the queue empty? '> + pq.isEmpty());> >}> }> |
>
>Wyjście
Priority queue: [1, 3, 2, 5, 4] Peek: 1 Priority queue after removing top element: [2, 3, 4, 5] Does the queue contain 3? true Size of queue: 4 Is the queue empty? true>
Przykłady czasu rzeczywistego:
Kolejka priorytetowa to struktura danych, w której elementy są uporządkowane według priorytetu, przy czym elementy o najwyższym priorytecie pojawiają się na początku kolejki. Oto kilka rzeczywistych przykładów wykorzystania kolejek priorytetowych:
- Planowanie zadań: W systemach operacyjnych kolejki priorytetowe służą do planowania zadań na podstawie ich poziomów priorytetów. Na przykład zadanie o wysokim priorytecie, takie jak krytyczna aktualizacja systemu, może zostać zaplanowane przed zadaniem o niższym priorytecie, takim jak proces tworzenia kopii zapasowej w tle. Izba przyjęć: Na szpitalnej izbie przyjęć pacjenci są segregowani na podstawie ciężkości ich stanu, przy czym w pierwszej kolejności leczeni są pacjenci w stanie krytycznym. Kolejka priorytetowa może służyć do zarządzania kolejnością przyjmowania pacjentów przez lekarzy i pielęgniarki. Routing sieciowy: W sieciach komputerowych kolejki priorytetowe służą do zarządzania przepływem pakietów danych. Pakiety o wysokim priorytecie, takie jak dane głosowe i wideo, mogą mieć priorytet w stosunku do danych o niższym priorytecie, takich jak wiadomości e-mail i przesyłanie plików. Transport: W systemach zarządzania ruchem kolejki priorytetowe mogą służyć do zarządzania przepływem ruchu. Na przykład pojazdy uprzywilejowane, takie jak karetki pogotowia, mogą mieć pierwszeństwo przed innymi pojazdami, aby zapewnić im szybkie dotarcie do celu. Planowanie zadań: W systemach planowania zadań kolejki priorytetowe mogą służyć do zarządzania kolejnością wykonywania zadań. Zadania o wysokim priorytecie, takie jak krytyczne aktualizacje systemu, mogą być zaplanowane przed zadaniami o niższym priorytecie, takimi jak tworzenie kopii zapasowych danych. Rynki internetowe: na rynkach internetowych kolejki priorytetowe mogą służyć do zarządzania dostawą produktów do klientów. Zamówienia o wysokim priorytecie, takie jak wysyłka ekspresowa, mogą mieć pierwszeństwo przed standardowymi zamówieniami wysyłkowymi.
Ogólnie rzecz biorąc, kolejki priorytetowe są użyteczną strukturą danych do zarządzania zadaniami i zasobami w oparciu o ich poziomy priorytetów w różnych rzeczywistych scenariuszach.
Metody w klasie PriorityQueue
| METODA | OPIS |
|---|---|
| dodaj (i i) | Wstawia określony element do tej kolejki priorytetowej. |
| jasne() | Usuwa wszystkie elementy z tej kolejki priorytetowej. |
| komparator() | Zwraca komparator używany do porządkowania elementów w tej kolejce lub wartość null, jeśli kolejka jest posortowana zgodnie z naturalną kolejnością jej elementów. |
| zawiera?(Obiekt o) | Zwraca wartość true, jeśli ta kolejka zawiera określony element. |
| forEach? (Działanie konsumenckie) | Wykonuje daną akcję dla każdego elementu Iterable, dopóki wszystkie elementy nie zostaną przetworzone lub akcja nie zgłosi wyjątku. |
| iterator() | Zwraca iterator po elementach w tej kolejce. |
| oferta? (E e) | Wstawia określony element do tej kolejki priorytetowej. |
| usunąć?(Obiekt o) | Usuwa pojedyncze wystąpienie określonego elementu z tej kolejki, jeśli jest obecne. |
| usunąćWszystko?(Kolekcja c) | Usuwa wszystkie elementy tej kolekcji, które są również zawarte w określonej kolekcji (operacja opcjonalna). |
| usunąćIf?(Filtr predykatów) | Usuwa wszystkie elementy tej kolekcji, które spełniają podany predykat. |
| zachować wszystko? (Kolekcja c) | Zachowuje tylko elementy w tej kolekcji, które znajdują się w określonej kolekcji (operacja opcjonalna). |
| rozdzielacz() | Tworzy późno wiążący i niezawodny Spliterator dla elementów w tej kolejce. |
| do tablicy() | Zwraca tablicę zawierającą wszystkie elementy w tej kolejce. |
| do tablicy?(T[]a) | Zwraca tablicę zawierającą wszystkie elementy w tej kolejce; typem środowiska wykonawczego zwróconej tablicy jest typ określonej tablicy. |
Metody Zadeklarowane w klasie java.util.AbstractQueue
| METODA | OPIS |
|---|---|
| addAll(kolekcja c) | Dodaje do tej kolejki wszystkie elementy z określonej kolekcji. |
| element() | Pobiera, ale nie usuwa, początek tej kolejki. |
| usunąć() | Pobiera i usuwa początek tej kolejki. |
Metody Zadeklarowane w klasie java.util.AbstractCollection
| METODA | OPIS |
|---|---|
| zawieraWszystko (kolekcja c) | Zwraca wartość true, jeśli ta kolekcja zawiera wszystkie elementy określonej kolekcji. |
| jest pusty() | Zwraca wartość true, jeśli ta kolekcja nie zawiera żadnych elementów. |
| doString() | Zwraca ciąg znaków reprezentujący tę kolekcję. |
Metody Zadeklarowane w interfejsie java.util.Collection
| METODA | OPIS |
|---|---|
| zawieraWszystko (kolekcja c) | Zwraca wartość true, jeśli ta kolekcja zawiera wszystkie elementy określonej kolekcji. |
| równa się (obiekt o) | Porównuje określony obiekt z tą kolekcją pod kątem równości. |
| hashCode() | Zwraca wartość kodu skrótu dla tej kolekcji. |
| jest pusty() | Zwraca wartość true, jeśli ta kolekcja nie zawiera żadnych elementów. |
| strumień równoległy() | Zwraca prawdopodobnie równoległy Stream z tą kolekcją jako źródłem. |
| rozmiar() | Zwraca liczbę elementów w tej kolekcji. |
| strumień() | Zwraca sekwencyjny Stream z tą kolekcją jako źródłem. |
| toArray(generator funkcji Int) | Zwraca tablicę zawierającą wszystkie elementy w tej kolekcji, korzystając z dostarczonej funkcji generatora w celu alokacji zwróconej tablicy. |
Metody Zadeklarowane w interfejsie java.util.Queue
| METODA | OPIS |
|---|---|
| zerkać() | Pobiera, ale nie usuwa, nagłówek tej kolejki lub zwraca wartość null, jeśli ta kolejka jest pusta. |
| głosowanie() | Pobiera i usuwa nagłówek tej kolejki lub zwraca wartość null, jeśli ta kolejka jest pusta. |
Aplikacje :
- Implementacja algorytmów Dijkstry i Prima.
- Maksymalizuj sumę tablicy po K negacjach
Powiązane artykuły :
zastosowań systemu operacyjnego
- Klasa Java.util.PriorityQueue w Javie
- Zaimplementuj PriorityQueue poprzez komparator w Javie