0Pricing
Java Academy · Lekcja

PriorityQueue do uporządkowanego przetwarzania

Używaj PriorityQueue z naturalnym porządkiem i własnymi komparatorami w scenariuszach planowania zadań.

PriorityQueue do uporządkowanego przetwarzania to bezpłatna lekcja Java Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Java Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Java Academy zawiera 4 lekcji w sumie.

Czym jest PriorityQueue?

PriorityQueue jest domyślnie kopcem minimum: element o najniższej kolejności naturalnej zawsze znajduje się na początku. Elementy nie są wewnętrznie posortowane — gwarantowane jest tylko to, że minimum znajduje się na początku.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll()); // 10 (min)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

Wewnętrzna struktura kopca

PriorityQueue używa binarnego kopca minimum przechowywanego w tablicy. Rodzic o indeksie i jest zawsze ≤ swoim dzieciom o indeksach 2i+1 i 2i+2. Gwarantuje to złożoność O(log n) dla operacji offer/poll oraz O(1) dla peek.

Kopiec maksimum z odwróconym komparatorem

Aby utworzyć kopiec maksimum (z największym elementem na początku), należy przekazać Comparator.reverseOrder():

PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
maxPQ.offer(10);
maxPQ.offer(50);
maxPQ.offer(30);

System.out.println(maxPQ.poll()); // 50 (max)
System.out.println(maxPQ.poll()); // 30

PriorityQueue z własnymi obiektami

Użyj komparatora, aby uporządkować własne rekordy lub klasy:

record Job(String name, int priority) {}

PriorityQueue<Job> queue = new PriorityQueue<>(
    Comparator.comparingInt(Job::priority) // ascending priority
);
queue.offer(new Job("Backup", 5));
queue.offer(new Job("Alert", 1));
queue.offer(new Job("Report", 3));

System.out.println(queue.poll().name()); // Alert (priority 1)

Peek a poll

peek() zwraca element z początku kolejki bez jego usuwania. poll() usuwa go i zwraca. Obie metody zwracają null dla pustej kolejki (w przeciwieństwie do element()/remove(), które zgłaszają wyjątek).

PriorityQueue<String> pq = new PriorityQueue<>();
pq.offer("banana");
pq.offer("apple");

System.out.println(pq.peek()); // apple (not removed)
System.out.println(pq.peek()); // apple (still there)
System.out.println(pq.poll()); // apple (removed)
System.out.println(pq.peek()); // banana

Przykład planowania zadań

PriorityQueue idealnie nadaje się do symulacji planowania zadań przez procesor, w których zadania mają różne priorytety:

record Task(String name, int priority) {}

PriorityQueue<Task> scheduler = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
scheduler.offer(new Task("Low", 1));
scheduler.offer(new Task("Critical", 10));
scheduler.offer(new Task("Normal", 5));

while (!scheduler.isEmpty()) {
    System.out.println("Processing: " + scheduler.poll().name());
}
// Critical, Normal, Low

K najmniejszych elementów

PriorityQueue to klasyczne narzędzie do znajdowania K najmniejszych elementów bez pełnego sortowania tablicy:

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : nums) pq.offer(n);

for (int i = 0; i < k; i++) {
    System.out.print(pq.poll() + " ");
}
// 1 2 3

K największych elementów z kopcem maksimum

Alternatywnie podczas iterowania można utrzymywać kopiec minimum o rozmiarze K, aby znaleźć K największych elementów:

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
    minHeap.offer(n);
    if (minHeap.size() > k) minHeap.poll(); // remove smallest
}
// minHeap now contains the 3 largest: [7, 8, 9]
System.out.println(minHeap); // order may vary

Schemat algorytmu Dijkstry

Algorytm najkrótszej ścieżki Dijkstry korzysta z kopca minimum, aby zawsze najpierw rozwijać najtańszy nieodwiedzony węzeł:

record Entry(int node, int cost) {}

PriorityQueue<Entry> pq = new PriorityQueue<>(
    Comparator.comparingInt(Entry::cost)
);
pq.offer(new Entry(0, 0)); // start node, cost 0

while (!pq.isEmpty()) {
    Entry curr = pq.poll();
    System.out.println("Visit node " + curr.node() + " cost=" + curr.cost());
    // expand neighbors...
}

Iterowanie nie zachowuje kolejności

Iterowanie po PriorityQueue NIE zwraca elementów w kolejności priorytetów — robi to tylko poll(). Aby uzyskać posortowany wynik, należy wielokrotnie wywoływać poll zamiast używać pętli for-each.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5,3,1,4,2));

// WRONG for sorted output:
for (int n : pq) System.out.print(n+" "); // unordered!

// CORRECT:
while (!pq.isEmpty()) System.out.print(pq.poll()+" "); // 1 2 3 4 5

Podsumowanie wydajności

Złożoność operacji PriorityQueue:

  • offer(e): O(log n)
  • poll(): O(log n)
  • peek(): O(1)
  • contains(e): O(n)
  • remove(e): O(n)

Klasa nie jest bezpieczna wątkowo — w przypadku dostępu współbieżnego należy użyć PriorityBlockingQueue.

Szybkie sprawdzenie

Co pętla for-each iterująca po PriorityQueue gwarantuje w odniesieniu do kolejności elementów?

Podsumowanie: PriorityQueue

Najważniejsze informacje:

  • PriorityQueue jest kopcem minimum: najmniejszy element jest pobierany jako pierwszy
  • Użyj Comparator.reverseOrder() dla kopca maksimum
  • O(log n) dla offer/poll, O(1) dla peek
  • Klasyczne zastosowania: K-ty największy/najmniejszy element, algorytm Dijkstry, planowanie zadań
  • Pętla for-each nie zwraca elementów w kolejności priorytetów — użyj poll()

Często zadawane pytania

Czy lekcja „PriorityQueue do uporządkowanego przetwarzania” jest bezpłatna?

Tak — pełny tekst „PriorityQueue do uporządkowanego przetwarzania” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Java Academy, przejdź na CoddyKit PRO. Kurs Java Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „PriorityQueue do uporządkowanego przetwarzania”?

Używaj PriorityQueue z naturalnym porządkiem i własnymi komparatorami w scenariuszach planowania zadań. Ćwiczysz Java Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Java Academy?

Nie wymagamy żadnego doświadczenia. Java Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „PriorityQueue do uporządkowanego przetwarzania”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Java Academy?

Tak. Każda lekcja Java Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Wewnętrzne działanie LinkedList
  2. Operacje Deque: stos i kolejka
  3. LinkedList a ArrayList — kompromisy
  4. PriorityQueue do uporządkowanego przetwarzania
← Powrót do Java Academy