PriorityQueue (front): Dátová štruktúra priority queue v Jave
Prioritné fronty prinášajú poriadok tam, kde nestačí obyčajné FIFO – od real‑time simulácií až po plánovanie úloh. V tejto časti seriálu o dátových štruktúrach ti, ako môžeš efektívne použiť triedu PriorityQueue z balíka java.until. Prevedieme ťa konštruktormi, metódami aj úskaliami synchronizácie a chýbať nebude ani názorný príklad z nemocničnej praxe.
V článku sa dozvieš:
Zatiaľ čo priority queue označuje abstraktný dátový typ, ktorý spracúva prvky podľa priority, PriorityQueue je konkrétna trieda v Jave, ktorú použiješ na jeho implementáciu. Dátová štruktúra PriorityQueue, ktorá umožňuje efektívne spracovanie prvkov vo fronte podľa ich priority, resp. nami definovaného poradia.
PriorityQueue kolekcia – hierarchia dedičnosti (zdroj)
Java PriorityQueue je jednou z množstva dátových štruktúr na jednoduchšiu prácu s dátami. V našom seriáli si postupne predstavíme aj rôzne ďalšie dátové štruktúry. Ukážeme si, ako s nimi pracovať, aké operácie sa s nimi dajú robiť, aké sú najčastejšie používané metódy. Spomenieme výhody a nevýhody a kedy je vhodné konkrétnu dátovú štruktúru použiť.
PriorityQueue v Java – predstavenie dátovej štruktúry
Dátová kolekcia PriorityQueue (k dispozícii od Java 1.5) je implementáciou rozhrania Queue, ktorá predstavuje abstraktný dátový typ podobný fronte. Rozdiel spočíva v algoritme odstraňovania prvkov.
Zatiaľ čo klasická fronta pracuje na princípe FIFO (First In, First out) a prvky sa pridávajú na koniec fronty a odstraňujú na začiatku, v PriorityQueue sú prvky uložené podľa ako už názov dátovej štruktúry napovedá podľa priority. Najskôr sa vždy odstráni prvok s najvyššou prioritou, pred ostatnými s nižšou prioritou. Ak existuje viacero prvkov s najvyššou prioritou, jeden z týchto prvkov sa ľubovoľne vyberie ako najmenší prvok.
Interná štruktúra je binárna halda (binary heap), čo zabezpečuje, že prístup k prvku s najvyšším prioritou (metóda peek() alebo poll()) trvá O(1), zatiaľ čo vkladanie a odstraňovanie v čase O(log n). Podľa potreby môžeme použiť prirodzené poradie prvkov (ak implementujú Comparable), alebo vlastný Comparator, ktorý definuje prioritu.
Nulové prvky nie sú povolené, rovnako sa neumožňuje vkladanie prvkov neporovnateľných prvkov, takých, kde sa nedá určiť priorita.
Kolekcia PriorityQueue nie je synchronizovaná. To znamená, že nie bezpečná pre viacvláknové spracovanie. Na prácu s viacerými vláknami poskytuje Java triedu PriorityBlockingQueue, ktorá implementuje rozhranie BlockingQueue.
PriorityQueue – konštruktory
Pre vytvorenie inštancie PriorityQueue máme k dispozícii niekoľko konštruktorov:
- Prázdna PriorityQueue
Vytvorí PriorityQueue s predvolenou počiatočnou kapacitou (11), ktorá zoradí svoje prvky podľa ich prirodzeného usporiadania.PriorityQueue() - PriorityQueue s danou počiatočnou kapacitou
Vytvorí PriorityQueue so zadanou počiatočnou kapacitou, ktorá usporiada svoje prvky podľa ich prirodzeného usporiadania.PriorityQueue(int initialCapacity) - PriorityQueue s kapacitou a Comparatorom
Vytvorí PriorityQueue so zadanou počiatočnou kapacitou, ktorá usporiada svoje prvky podľa zadaného porovnávača.PriorityQueue(int initialCapacity, Comparator<? super E> comparator) - PriorityQueue skonštruovaná z existujúcej kolekcie
Vytvorí PriorityQueue obsahujúca prvky zo zadanej kolekcie.PriorityQueue(Collection<? extends E> c) - PriorityQueue s Comparatorom
Vytvorí PriorityQueue s predvolenou počiatočnou kapacitou, ktorej prvky sú zoradené podľa zadaného komparátora.PriorityQueue(Comparator<? super E> comparator) - PriorityQueue skonštruovaná z inej PriorityQueue
Vytvorí PriorityQueue, ktorá bude obsahovať prvky v zadanej prioritnej fronte.PriorityQueue(PriorityQueue<? extends E> c) - PriorityQueue skonštruovaná zo SortedSet
Vytvorí PriorityQueue, ktorá bude obsahovať prvky prvky v zadanej zoradenej množine.PriorityQueue(SortedSet<? extends E> c)
PriorityQueue – základné operácie
Medzi základné operácie, ktoré môžeme vykonávať s PriorityQueue, patria:
- Vkladanie prvkov
Pomocou metód add(E e) alebo offer(E e) sa vloží prvok s danou prioritou. Prvá metóda vyvolá výnimku, ak je front plný, druha vráti v rovnakom prípade false. - Získanie referencie prvku s najvyššou prioritou
Metóda peek() vráti prvok s najvyššou prioritou bez odstránenia, null ak prázdna. - Získanie a odstránenie prvku s najvyššou prioritou
Metóda poll() odstráni a vráti prvok s najvyššou prioritou, null ak prázdna. - Odstraňovanie prvkov
Metóda remove(Object o) sa používa na odstránenie konkrétneho prvku z PriorityQueue. - Vyprázdnenie kolekcie
Metóda clear() odstráni všetky prvky z PriorityQueue kolekcie. - Vyhľadávanie prvkov podľa kľúča alebo hodnoty
Metóda containsKey(Object o) zisťuje, či sa zadaný prvok nachádza v kolekcii. - Zistenie veľkosti kolekcie
Metóda size() vráti počet záznamov (objektov) danej PriorityQueue. - Iterácia cez prvky
Pri iterácii cez PriorityQueue poradie prvkov nie je garantované.
PriorityQueue – dokumentácia
Kompletný prehľad metód triedy PriorityQueue, nájdeš v oficiálnej dokumentácii
PriorityQueue – výhody a nevýhody
Výhody PriorityQueue
- Efektívny prístup k prvkom s najvyššou prioritou.
PriorityQueue umožňuje rýchly prístup k elementom s najvyššou prioritou – peek() v O(1). - Flexibilita pri stanovení priority
PriorityQueue nám dáva možnosť definovať vlastný Comparator, alebo použitie prirodzeného poradia. - Logaritmický čas operácií
Základné operácie s prvkami (pridávanie, odstraňovanie, vyhľadávanie) prebiehajú v čase O(log n).
Nevýhody PriorityQueue
- Poradie prvkov pri iterácii nie je garantované
Pri iterácii kvôli internej reprezentácii prvky nie sú zoradené. - Nie je synchronizovaná
A teda nie je vhodná pre multivláknové spracovanie. - Vyžaduje definovanie porovnateľnosti
Prvky v PriorityQueue musia implementovať rozhranie Comparable alebo musí byť zadaný vhodný Comparator.
PriorityQueue – kedy ho použiť a kedy nie?
PriorityQueue je ideálny v prípadoch, keď:
- Potrebujeme plánovať úlohy podľa priority (task scheduling).
- Pri simulovaní udalostí (event simulation).
- Hodia sa pre algoritmy grafov a real-time systémy
Príklad použitia PriorityQueue v Jave
Teraz si ukážeme, ako prakticky pracovať s kolekciou PriorityQueue v Java. Dátová štruktúra PriorityQueue sa vynikajúco hodí pre simulovanie udalostí, resp. programy, ktoré vyžadujú spracovanie prvkov podľa priority.
Dnes si naprogramujeme realistický simulátor nemocnice. Do nemocnice prichádzajú pacienti (alebo sú privezení sanitkou). Každý pacient sa najskôr v nemocnici rýchlo vyšetrí a určí sa závažnosť jeho stavu. Stav pacientov sa ohodnotí od 1 až 10, kde 10 je život ohrozujúci stav a 1, kde pacient je takmer zdravý.
Pacientov po vyšetrení umiestnime do PriorityQueue (prioritná fronta na liečbu), kde budú čakať, kým sa dostanú na rad. Lekári vždy začnú liečiť pacienta s najvyššou závažnosťou, takéhoto pacienta označíme na konci liečby ako vyliečeného. Aby sme simulátor nemocnice spravili trochu realistický, tak pacientom so stavom 5 až 10 sa v každom ťahu (liečba iného pacienta) zhorší stav o +1. Ak mal pacient kriticky stav 10 a nedostal sa prioritne na vyšetrenie, zomiera. Priebeh simulácie vypíšeme prehľadne na konzolu.
Patient.java
import java.util.Random;
public class Patient {
private final String name;
private int severity; // Severity from 1 (lowest) to 10 (highest)
public Patient(String name) {
this.name = name;
this.severity = examine();
}
// Simulate examination by assigning random severity between 1 and 10
private int examine() {
Random random = new Random();
return random.nextInt(10) + 1;
}
public String getName() {
return name;
}
public int getSeverity() {
return severity;
}
public void increaseSeverity() {
severity++;
}
@Override
public String toString() {
return name + " (severity: " + severity + ")";
}
}HospitalSimulation.java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class HospitalSimulation {
private final PriorityQueue<Patient> triageQueue;
public HospitalSimulation() {
// Create a PriorityQueue sorting patients from highest severity to lowest
this.triageQueue = new PriorityQueue<>(Comparator.comparingInt(Patient::getSeverity).reversed());
}
// Add patients to the queue
public void admitPatients(Patient[] patients) {
System.out.println("🚑 Admitting patients...");
for (Patient patient : patients) {
triageQueue.add(patient);
System.out.println("✅ Admitted: " + patient);
}
}
// Treat patients based on their severity
public void treatPatients() {
System.out.println("\n🏥 Starting treatment...");
while (!triageQueue.isEmpty()) {
Patient currentPatient = triageQueue.poll(); // Remove patient with the highest severity
System.out.println("👨⚕️ Treating: " + currentPatient);
simulateTreatment();
System.out.println("✅ " + currentPatient.getName() + " has been treated.\n");
// After treating a patient, increase the severity of waiting patients
worsenWaitingPatients();
}
System.out.println("🎉 All patients have been treated or deceased!");
}
// Increase severity for waiting patients, handle deaths
private void worsenWaitingPatients() {
if (triageQueue.isEmpty()) {
return;
}
List<Patient> updatedPatients = new ArrayList<>();
List<Patient> deceasedPatients = new ArrayList<>();
while (!triageQueue.isEmpty()) {
Patient patient = triageQueue.poll();
if (patient.getSeverity() >= 5) {
patient.increaseSeverity();
if (patient.getSeverity() > 10) {
deceasedPatients.add(patient); // Patient dies
continue;
}
}
updatedPatients.add(patient);
}
// Rebuild the queue with updated patients
triageQueue.addAll(updatedPatients);
// Report deaths
for (Patient deceased : deceasedPatients) {
System.out.println("⚰️ Patient " + deceased.getName() + " has died while waiting (severity exceeded 10).");
}
}
// Simulate the time taken to treat a patient
private void simulateTreatment() {
try {
Thread.sleep(500); // Simulate short delay (500ms)
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
// Entry point
public static void main(String[] args) {
// Create hospital simulation instance
HospitalSimulation hospital = new HospitalSimulation();
// Create 10 patients arriving at the hospital
Patient[] patients = {
new Patient("Alena"),
new Patient("Beáta"),
new Patient("Ctibor"),
new Patient("Daniel"),
new Patient("Elena"),
new Patient("František"),
new Patient("Gregor"),
new Patient("Helena"),
new Patient("Igor"),
new Patient("Jana")
};
// Simulate admitting and treating patients
hospital.admitPatients(patients);
hospital.treatPatients();
}
}Výstup z tohto príkladu môže vyzerať nasledovne:
Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave. Stiahni si Java kód pre PriorityQueue tu.
