java priority queue tutorial implementation examples
W tym samouczku wyjaśniono kolejkę priorytetów Java i pokrewne pojęcia, takie jak komparator, kolejka priorytetów min i maks., Wraz z jej implementacją i przykładami:
Struktura danych kolejki priorytetowej to specjalna kolejka, w której elementy są obecne nie zgodnie z kolejnością FIFO, ale według elementów naturalnych lub dowolnego niestandardowego komparatora używanego podczas tworzenia kolejki.
=> Zapoznaj się z podręcznikiem Java dla początkujących tutaj.
Czego się nauczysz:
Kolejka priorytetowa w Javie
W kolejce priorytetowej przód kolejki ma najmniej elementów zgodnie z naturalną kolejnością, a tył jest skierowany na największy element w kolejce.
Przykład kolejki priorytetowej składającej się z liczb pokazano poniżej.
pytania do rozmowy kwalifikacyjnej na temat testowania usług internetowych
Tak więc, gdy element zostanie usunięty z kolejki priorytetów pokazanej powyżej, będzie to element najmniejszy.
Podobnie, w przypadku alfabetycznej kolejki priorytetowej, wartości ASCII zostaną uwzględnione, a elementy kolejki zostaną uporządkowane zgodnie z wartościami ASCII.
Poniżej wymieniono niektóre z głównych cech PriorityQueue:
- PriorityQueue to niezwiązana kolejka.
- PriorityQueue nie zezwala na wartości null.
- W przypadku obiektów nieporównywalnych nie możemy utworzyć kolejki priorytetowej.
- PriorityQueue dziedziczy z klas takich jak AbstractQueue, AbstractCollection, Collection i Object.
- Początek lub przód kolejki zawiera najmniej elementów zgodnie z naturalnym porządkiem.
- Implementacja kolejki priorytetowej nie jest bezpieczna wątkowo. Dlatego jeśli chcemy dostępu zsynchronizowanego, powinniśmy użyć PriorityBlockingQueue.
Klasa PriorityQueue dziedziczy Java Queue Interface i jest częścią pakietu java.util.
Ogólna deklaracja klasy PriorityQueue jest podana poniżej:
public class PriorityQueue extends AbstractQueue implements SerializablePoniższy diagram przedstawia hierarchię klas dla klasy PriorityQueue.
Złożoność czasowa kolejki priorytetowej
- Złożoność czasowa kolejki priorytetowej dla metod wstawiania (umieszczania w kolejce) i usuwania (usuwania z kolejki) wynosi O (log (n)).
- Kolejka priorytetowa ma liniową złożoność czasową do usunięcia, a także zawiera metody.
- Metody pobierające elementy kolejki priorytetowej mają stałą złożoność czasową.
Przykład kolejki priorytetowej w języku Java
Poniższy program demonstruje prostą PriorityQueue w Javie. Tworzymy obiekt klasy PriorityQueue, dodajemy do niego wartości, a następnie wyświetlamy zawartość Queue za pomocą Iteratora.
import java.util.*; class Main{ public static void main(String args[]){ PriorityQueue cities_queue=new PriorityQueue(); //initialize the PriorityQueue with values cities_queue.add('Sydney'); cities_queue.add('Venice'); cities_queue.add('New York'); cities_queue.add('California'); cities_queue.add('Melbourne'); //print the head of the PriorityQueue System.out.println('PriorityQueue Head:'+cities_queue.element()); //Define the iterator for PriorityQueue and print its elements System.out.println('
PriorityQueue contents:'); Iterator iter=cities_queue.iterator(); while(iter.hasNext()){ System.out.print(iter.next() + ' '); } } } Wynik:
Metody Java Priority Queue API
Konstruktorzy:
| Prototyp konstruktora | Opis | |
|---|---|---|
| zerkać | E peek () | Zwraca nagłówek kolejki bez usuwania elementu. |
| Kolejka priorytetowa () | Domyślny konstruktor, który tworzy obiekt PriorityQueue o początkowej pojemności 1. | |
| PriorityQueue (kolekcja c) | Tworzy obiekt PriorityQueue z elementami początkowymi z danej kolekcji c. | |
| PriorityQueue (int initialCapacity) | Tworzy obiekt PriorityQueue z podaną wartością „initialCapacity”. Elementy zamawiane są według naturalnego zamówienia. | |
| PriorityQueue (int initialCapacity, komparator) | Tworzy obiekt PriorityQueue z podaną wartością „initialCapacity”. Elementy są uporządkowane zgodnie z podanym komparatorem. | |
| PriorityQueue (PriorityQueue c) | Tworzy obiekt PriorityQueue z innego obiektu PriorityQueue podanego przez c. | |
| PriorityQueue (SortedSet c) | Tworzy obiekt PriorityQueue z SortedSet podanego przez c. |
Metody
| metoda | Prototyp metody | Opis |
|---|---|---|
| Dodaj | add boolean (E e) | Dodaje element e do PriorityQueue. |
| jasny | void clear () | Czyści PriorityQueue, usuwając wszystkie elementy. |
| komparator | Komparator porównawczy () | Zwraca niestandardowy komparator używany do porządkowania elementów w kolejce. |
| zawiera | boolean zawiera (obiekt o) | Sprawdza, czy PriorityQueue zawiera dany element o. Zwraca wartość true, jeśli tak. |
| iterator | Iteratoriterator () | Metoda uzyskiwania iteratora dla danej PriorityQueue. |
| oferta | oferta logiczna (E e) | Wstaw dany element e do PriorityQueue. |
| głosowanie | E ankieta () | Usuwa i zwraca nagłówek kolejki. Zwraca wartość null, jeśli kolejka jest pusta. |
| usunąć | boolean remove (Object o) | Usuwa instancję danego elementu o jeśli jest obecny w kolejce. |
| rozmiar | rozmiar int () | Zwraca rozmiar lub liczbę elementów w tym PriorityQueue. |
| toArray | Obiekt [] toArray () | Zwraca tablicę reprezentującą podaną PriorityQueue. |
| toArray | T [] toArray (T [] a) | Zwraca reprezentację tablicy dla danej kolejki priorytetowej z tym samym typem środowiska uruchomieniowego co określona tablica a. |
Implementacja w Javie
Pokażmy powyższe metody PriorityQueue przy użyciu programu w języku Java.
import java.util.*; class Main { public static void main(String args[]) { // Creating empty priority queue PriorityQueue numQueue = new PriorityQueue(); // add elements to numQueue using add() numQueue.add('Five'); numQueue.add('One'); numQueue.add('Seven'); numQueue.add('Three'); numQueue.add('Eleven'); numQueue.add('Nine'); // Print the head element using Peek () method System.out.println('Head element using peek method:' + numQueue.peek()); // Printing all elements System.out.println('
The PriorityQueue elements:'); Iterator iter1 = numQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); // remove head with poll () numQueue.poll(); System.out.println('
After removing an element' + 'with poll function:'); Iterator iter2 = numQueue.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); // Remove 'Three' using remove () numQueue.remove('Three'); System.out.println('
Element 'Three' with' + ' remove function:'); Iterator iter3 = numQueue.iterator(); while (iter3.hasNext()) System.out.print(iter3.next() + ' '); // Check if an element is present in PriorityQueue using contains() boolean ret_val = numQueue.contains('Five'); System.out.println('
Priority queue contains 'Five' ' + 'or not?: ' + ret_val); // get array equivalent of PriorityQueue with toArray () Object[] numArr = numQueue.toArray(); System.out.println('
Array Contents: '); for (int i = 0; i Wynik:
najlepszy konwerter youtube na mp3 online
Kolejka priorytetowa w Javie 8
Java 8 dodaje jeszcze jedną metodę do klasy PriorityQueue, tj. „Spliterator ()”.
Szczegóły tej metody podano poniżej.
Nazwa metody: rozdzielacz
Prototyp metody: public final Spliterator spliterator ()
Opis metody: Ta metoda tworzy rozdzielacz dla elementów PriorityQueue. Ten spliterator wiąże się z opóźnieniem i jest szybki.
Komparator kolejek priorytetowych
Jak już wspomniano, elementy PriorityQueue są oczywiście uporządkowane. Jeśli chcemy zmienić kolejność, to powinniśmy określić komparator i użyć go podczas tworzenia obiektu PriorityQueue. Następnie PriorityQueue używa tego komparatora do porządkowania swoich elementów.
Poniższy program w języku Java demonstruje użycie niestandardowego komparatora do porządkowania elementów. W tym programie definiujemy nowy niestandardowy komparator, w którym zastępujemy metodę „porównania”. Metoda porównania służy do uporządkowania elementów PriorityQueue według długości.
import java.util.*; public class Main { public static void main(String[] args) { // A custom comparator that compares two Strings by their length. Comparator customComparator = new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } }; // Create a Priority Queue with a custom Comparator PriorityQueue colorsPriorityQueue = new PriorityQueue(customComparator); // Add items to a Priority Queue colorsPriorityQueue.add('Red'); colorsPriorityQueue.add('Green'); colorsPriorityQueue.add('Blue'); colorsPriorityQueue.add('Cyan'); colorsPriorityQueue.add('Magenta'); colorsPriorityQueue.add('Yellow'); // Printing all elements System.out.println('
The PriorityQueue elements with custom Comparator:'); Iterator iter1 = colorsPriorityQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); } } Wynik:
Min kolejka priorytetowa w Javie
Naturalna kolejność kolejki priorytetowej ma najmniejszy lub najmniejszy element na początku kolejki, a zatem kolejność jest rosnąca. Nazywa się to „kolejką o minimalnym priorytecie” z rosnącą kolejnością elementów.
Poniższy program Java przedstawia implementację Min Priority Queue w Javie.
import java.util.*; class Main{ public static void main(String args[]){ //declare a PriorityQueue object with default ordering PriorityQueue pq = new PriorityQueue(); //add element to the PriorityQueue pq.add(8); pq.add(6); pq.add(4); pq.add(2); pq.add(12); pq.add(10); //display the min PriorityQueue System.out.println('The min Priority Queue (natural ordering) contents:'); Integer val = null; while( (val = pq.poll()) != null) { System.out.print(val + ' '); } } } Wynik:
Maksymalna kolejka priorytetowa w Javie
Podczas gdy kolejka o minimalnym priorytecie ma elementy w kolejności rosnącej, kolejka o maksymalnym priorytecie ma elementy w porządku malejącym, tj. Nagłówek kolejki o maksymalnym priorytecie zwróci największy element w kolejce.
Poniższy program w języku Java demonstruje kolejkę maksymalnego priorytetu w języku Java.
import java.util.*; class Main{ public static void main(String args[]){ //declare a PriorityQueue object with custom comparator to generate max PQ PriorityQueue pq = new PriorityQueue(new Comparator() { public int compare(Integer lhs, Integer rhs) { if (lhs Wynik:
Jak pokazano w powyższym programie, aby zmienić naturalną kolejność elementów w kolejce priorytetowej, musimy zdefiniować własny komparator.
co to jest kod bezpieczeństwa sieci
Często Zadawane Pytania
Pytanie 1) Co to jest kolejka priorytetowa w Javie?
Odpowiedź: Specjalna kolejka, w której wszystkie elementy kolejki są uporządkowane zgodnie z naturalną kolejnością lub za pomocą niestandardowego komparatora, nazywana jest kolejką priorytetową. Nie jest zgodny z zamówieniem FIFO.
Pytanie 2) Jak ustawić kolejkę Max Priority w Javie?
Odpowiedź: Możemy ustawić kolejkę maksymalnego priorytetu w Javie za pomocą niestandardowego komparatora, aby nagłówek kolejki zwrócił największy element w kolejce.
Pytanie 3) Czy kolejka Priority zezwala na duplikaty Java?
Odpowiedź: Tak. Kolejka priorytetowa zezwala na zduplikowane wartości.
Pytanie 4) Czy kolejka Java Priority jest maksymalna czy minimalna?
Odpowiedź: Domyślnie kolejka priorytetowa w Javie to kolejka min Priority z naturalną kolejnością. Aby było to maksymalne, musimy użyć niestandardowego komparatora, aby głowa kolejki zwracała największy element w kolejce.
P # 5) Czy kolejka priorytetowa jest posortowana?
Odpowiedź: Domyślnie nagłówek kolejki jest sortowany, a kolejka Priority ma najmniejszy element jako jej nagłówek. Pozostałe elementy są zamawiane w razie potrzeby.
Wniosek
To kończy samouczek dotyczący kolejek priorytetowych w Javie. Priority Queue implementuje interfejs kolejki i jest specjalną kolejką, w której elementy są uporządkowane zgodnie z naturalną kolejnością. Nie jest zgodny z zamówieniem FIFO. Aby zmienić naturalną kolejność kolejki priorytetowej, możemy użyć komparatora niestandardowego.
Kolejki priorytetowe są używane głównie do planowania drukarek, planowania zadań procesora itp. Sterta (min lub max) jest również implementowana przy użyciu kolejek priorytetowych.
=> Przeczytaj serię szkoleń Easy Java.
rekomendowane lektury
- Struktura danych kolejki priorytetowej w C ++ z ilustracjami
- Kolejka priorytetowa w STL
- Kolejka Java - metody kolejki, implementacja kolejki z przykładami
- Struktura danych kolejek cyklicznych w C ++: wdrażanie i aplikacje
- Podwójnie zakończona kolejka (Deque) w C ++ z przykładami
- Struktura danych kolejki w C ++ z ilustracjami
- Stosy i kolejki w STL
- Samouczek JAVA dla początkujących: ponad 100 praktycznych samouczków wideo Java
