Java Academy · Lektion

PriorityQueue för ordnad bearbetning

Använd PriorityQueue med naturlig ordning och egna komparatorer i scenarier för schemaläggning av uppgifter.

Lektion 4 av 413 steg

PriorityQueue för ordnad bearbetning är en gratis lektion i Java Academy på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Java Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Java Academy innehåller totalt 4 lektioner.

Vad är en PriorityQueue?

En PriorityQueue är som standard en min-heap: elementet med den lägsta naturliga ordningen finns alltid först. Elementen är inte sorterade internt – endast det minsta elementet garanteras ligga först.

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 heapstruktur

PriorityQueue använder en binär min-heap som lagras i en array. Föräldern på index i är alltid ≤ sina barn på 2i+1 och 2i+2. Detta garanterar O(log n) för offer/poll och O(1) för peek.

Max-heap med omvänd comparator

Skapa en max-heap, där det största elementet kommer först, genom att skicka med 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 anpassade objekt

Använd en comparator för att ordna anpassade 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 jämfört med poll

peek() returnerar det första elementet utan att ta bort det. poll() tar bort och returnerar det. Båda returnerar null för en tom kö, till skillnad från element()/remove() som kastar ett undantag.

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

Exempel på schemaläggning av uppgifter

PriorityQueue passar utmärkt för simuleringar av CPU-schemaläggning där uppgifter har olika prioritet:

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 minsta element

PriorityQueue är ett klassiskt verktyg för att hitta de K minsta elementen utan att sortera hela arrayen:

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örsta element med max-heap

Alternativt kan Ni under iterationen upprätthålla en min-heap med storleken K för att hitta de K största elementen:

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 för Dijkstras algoritm

Dijkstras algoritm för kortaste vägen använder en min-heap för att alltid först expandera den billigaste obesökta noden:

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

Iteration sker i osorterad ordning

Iteration över en PriorityQueue returnerar INTE elementen i prioritetsordning – det gör endast poll(). Använd upprepade anrop av poll i stället för en for-each-loop om Ni vill få sorterade resultat.

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

Prestandasammanfattning

Komplexiteten för PriorityQueue-operationer:

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

Trådsäkerhet saknas – använd PriorityBlockingQueue för samtidig åtkomst.

Snabb kontroll

Vad garanteras om elementens ordning när Ni itererar över en PriorityQueue med en for-each-loop?

Besvara frågan i den interaktiva lektionen

Sammanfattning: PriorityQueue

Viktiga slutsatser:

PriorityQueue är en min-heap: det minsta elementet hämtas först med poll
Använd Comparator.reverseOrder() för en max-heap
O(log n) för offer/poll och O(1) för peek
Klassiska användningsområden: det K:e största/minsta elementet, Dijkstra och schemaläggning av uppgifter
for-each ger inte prioritetsordning – använd poll()

Gratis att börja

Lär dig Java med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 104
Lektioner: 374

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”PriorityQueue för ordnad bearbetning” gratis?

Ja – hela texten till ”PriorityQueue för ordnad bearbetning” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Java Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Java Academy innehåller totalt 4 lektioner.

Vad lär jag mig i ”PriorityQueue för ordnad bearbetning”?

Använd PriorityQueue med naturlig ordning och egna komparatorer i scenarier för schemaläggning av uppgifter. Ni övar på Java Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Java Academy?

Du behöver inga förkunskaper. Utbildningen i Java Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.

Hur lång tid tar lektionen ”PriorityQueue för ordnad bearbetning”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Java Academy-lektionen?

Ja. Varje Java Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till Java Academy