Java Academy · Lektion

PriorityQueue til ordnet behandling

Brug PriorityQueue med naturlig sorteringsrækkefølge og brugerdefinerede comparatorer i scenarier med opgaveplanlægning.

Lektion 4 af 413 trin

PriorityQueue til ordnet behandling er en gratis Java Academy-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Java Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Java Academy-kurset indeholder 4 lektioner i alt.

Hvad er en PriorityQueue?

En PriorityQueue er som standard en min-heap: Elementet med den laveste naturlige rækkefølge står altid forrest. Elementerne sorteres ikke internt — kun minimumselementet er garanteret at stå forrest.

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

Intern heap-struktur

PriorityQueue bruger en binær min-heap, der er gemt i et array. Forælderen ved indeks i er altid ≤ sine børn ved 2i+1 og 2i+2. Det garanterer offer/poll på O(log n) og peek på O(1).

Max-heap med omvendt Comparator

Opret en max-heap, hvor det største element kommer først, ved at angive 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 med brugerdefinerede objekter

Brug en comparator til at ordne brugerdefinerede poster eller klasser:

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 kontra Poll

peek() returnerer det forreste element uden at fjerne det. poll() fjerner og returnerer det. Begge returnerer null for en tom kø, i modsætning til element()/remove(), som kaster en undtagelse.

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

Eksempel på opgaveplanlægning

PriorityQueue er ideel til simuleringer af CPU-planlægning, hvor opgaver har forskellige prioriteter:

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 mindste elementer

PriorityQueue er et klassisk værktøj til at finde de K mindste elementer uden at sortere hele arrayet:

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 største elementer med en max-heap

Du kan også vedligeholde en min-heap med størrelsen K under gennemløbet for at finde de K største elementer:

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

Mønster for Dijkstras algoritme

Dijkstras algoritme til korteste vej bruger en min-heap til altid først at udvide den billigste ubesøgte node:

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

Gennemløb har ingen bestemt rækkefølge

Gennemløb af en PriorityQueue returnerer IKKE elementerne i prioritetsrækkefølge — det gør kun poll(). Hvis du vil have sorteret output, skal du gentagne gange kalde poll i stedet for at bruge 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

Oversigt over ydeevne

Kompleksiteten af PriorityQueue-operationer:

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

Er ikke trådsikker — brug PriorityBlockingQueue ved samtidig adgang.

Hurtigt tjek

Hvad garanterer det om elementernes rækkefølge, når du gennemløber en PriorityQueue med en for-each-løkke?

Besvar den i den interaktive lektion

Opsamling: PriorityQueue

Vigtigste pointer:

PriorityQueue er en min-heap: Det mindste element hentes først med poll
Brug Comparator.reverseOrder() til en max-heap
offer/poll på O(log n), peek på O(1)
Klassiske anvendelser: det K-te største eller mindste element, Dijkstra og opgaveplanlægning
for-each giver ikke prioritetsrækkefølge — brug poll()

Gratis at komme i gang

Lær Java med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 104
Lektioner: 374

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “PriorityQueue til ordnet behandling” gratis?

Ja — hele teksten til “PriorityQueue til ordnet behandling” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Java Academy-kurset, skal du opgradere til CoddyKit PRO. Java Academy-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “PriorityQueue til ordnet behandling”?

Brug PriorityQueue med naturlig sorteringsrækkefølge og brugerdefinerede comparatorer i scenarier med opgaveplanlægning. Du øver dig i Java Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Java Academy?

Der kræves ingen tidligere erfaring. Java Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.

Hvor lang tid tager lektionen “PriorityQueue til ordnet behandling”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Java Academy-lektion?

Ja. Alle Java Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til Java Academy