Java Academy · Oppitunti

PriorityQueue järjestettyyn käsittelyyn

Käytä PriorityQueuea luonnollisen järjestyksen ja mukautettujen vertailijoiden kanssa tehtävien ajoitukseen.

Oppitunti 4/413 vaihetta

PriorityQueue järjestettyyn käsittelyyn on ilmainen Java Academy-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Java Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Java Academy-kurssilla on yhteensä 4 oppituntia.

Mikä on PriorityQueue?

PriorityQueue on oletusarvoisesti minimikeko: luonnollisessa järjestyksessä pienin alkio on aina keon ensimmäisenä. Alkioita ei lajitella sisäisesti – ainoastaan pienimmän alkion sijainti ensimmäisenä taataan.

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

Keko sisäisesti

PriorityQueue käyttää taulukkoon tallennettua binääristä minimikekoa. Indeksissä i oleva isäntä on aina ≤ indekseissä 2i+1 ja 2i+2 olevia lapsia. Tämä takaa offer- ja poll-operaatioille ajan O(log n) sekä peek-operaatiolle ajan O(1).

Maksimikeko käänteisellä vertailijalla

Luodaksenne maksimikeon, jossa suurin alkio tulee ensin, välittäkää sille 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 mukautetuilla olioilla

Käyttäkää vertailijaa mukautettujen tietueiden tai luokkien järjestämiseen:

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 ja poll

peek() palauttaa ensimmäisen alkion poistamatta sitä. poll() poistaa alkion ja palauttaa sen. Molemmat palauttavat tyhjässä jonossa arvon null (toisin kuin element() ja remove(), jotka heittävät poikkeuksen).

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

Tehtävien ajoituksen esimerkki

PriorityQueue sopii erinomaisesti suorittimen ajoituksen simulointiin, kun tehtävillä on eri prioriteetit:

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 pienintä alkiota

PriorityQueue on perinteinen työkalu K pienimmän alkion etsimiseen ilman taulukon täydellistä lajittelua:

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 suurinta alkiota maksimikeolla

Vaihtoehtoisesti voitte ylläpitää K:n kokoista minimikekoa iteraation aikana löytääksenne K suurinta alkiota:

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

Dijkstran algoritmin malli

Dijkstran lyhimmän polun algoritmi käyttää minimikekoa laajentaakseen aina ensin edullisimman käymättömän solmun:

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...
}

Iterointijärjestystä ei taata

PriorityQueuen iterointi EI palauta alkioita prioriteettijärjestyksessä – vain poll() tekee niin. Jos tarvitsette lajitellun tulosteen, kutsukaa poll-operaatiota toistuvasti for-each-silmukan sijaan.

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

Suorituskyvyn yhteenveto

PriorityQueuen operaatioiden aikavaativuudet:

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

PriorityQueue ei ole säieturvallinen – käyttäkää samanaikaiseen käyttöön PriorityBlockingQueue-tietorakennetta.

Pikatarkistus

Mitä alkioiden järjestyksestä taataan, kun PriorityQueue käydään läpi for-each-silmukalla?

Vastaa interaktiivisessa oppitunnissa

Kertaus: PriorityQueue

Tärkeimmät opit:

PriorityQueue on minimikeko: pienin alkio poistetaan ensin
Käyttäkää maksimikekoon Comparator.reverseOrder()-vertailijaa
offer- ja poll-operaatiot ovat O(log n), peek-operaatio on O(1)
Tyypillisiä käyttötapauksia ovat K:nnen suurimman tai pienimmän alkion etsiminen, Dijkstra ja tehtävien ajoitus
for-each ei tuota prioriteettijärjestystä – käyttäkää poll()-operaatiota

Aloita maksutta

Opi Java tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 104
Oppitunnit: 374

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”PriorityQueue järjestettyyn käsittelyyn” ilmainen?

Kyllä – oppitunnin ”PriorityQueue järjestettyyn käsittelyyn” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Java Academy-kurssin, päivitä CoddyKit PROhon. Java Academy-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”PriorityQueue järjestettyyn käsittelyyn”?

Käytä PriorityQueuea luonnollisen järjestyksen ja mukautettujen vertailijoiden kanssa tehtävien ajoitukseen. Harjoittelet Java Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Java Academy-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Java Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.

Kuinka kauan ”PriorityQueue järjestettyyn käsittelyyn”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Java Academy-oppitunnilla?

Kyllä. Jokainen Java Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

LinkedListin sisäinen rakenne
Deque-toiminnot: pino ja jono
LinkedListin ja ArrayListin kompromissit
PriorityQueue järjestettyyn käsittelyyn

← Takaisin: Java Academy