PriorityQueue se používá, když se předpokládá, že objekty budou zpracovány na základě priority. Je známo, že a Fronta postupuje podle algoritmu First-In-First-Out, ale někdy je potřeba zpracovat prvky fronty podle priority, tehdy přichází do hry PriorityQueue.
PriorityQueue je založena na prioritní haldě. Prvky prioritní fronty jsou seřazeny podle přirozeného řazení nebo pomocí komparátoru poskytnutého v době vytváření fronty, v závislosti na použitém konstruktoru.
Ve frontě s prioritou níže bude mít prvek s maximální hodnotou ASCII nejvyšší prioritu.
Prohlášení:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
Třída implementuje Serializovatelné , Iterovatelné , Sbírka , Fronta rozhraní.
Trochu důležité body ve frontě priority jsou následující:
- PriorityQueue nepovoluje hodnotu null.
- Nemůžeme vytvořit prioritní frontu objektů, které nejsou srovnatelné
- PriorityQueue jsou nevázané fronty.
- Hlava této fronty je nejmenší prvek s ohledem na zadané řazení. Pokud je svázáno více prvků pro nejmenší hodnotu, je jedním z těchto prvků hlava – vazby se libovolně přeruší.
- Vzhledem k tomu, že PriorityQueue není bezpečná pro vlákna, Java poskytuje třídu PriorityBlockingQueue, která implementuje rozhraní BlockingQueue pro použití v prostředí Java s více vlákny.
- Operace načítání fronty dotazují, odebírají, nahlížejí a prvek přistupují k prvku v čele fronty.
- Poskytuje čas O(log(n)) pro metody přidávání a dotazování.
- Přebírá metody od AbstractQueue , Abstraktní kolekce , Sbírka, a Objekt třída.
Konstruktéři:
1. PriorityQueue(): Vytvoří PriorityQueue s výchozí počáteční kapacitou (11), která seřadí své prvky podle jejich přirozeného uspořádání.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue (kolekce c): Vytvoří PriorityQueue obsahující prvky v zadané kolekci.
PriorityQueue pq = new PriorityQueue(Kolekce c);
3. PriorityQueue (int initialCapacity) : Vytvoří PriorityQueue se zadanou počáteční kapacitou, která seřadí své prvky podle jejich přirozeného uspořádání.
PriorityQueue pq = new PriorityQueue(int initialCapacity);
4. PriorityQueue(int initialCapacity, Comparator Comparator): Vytvoří PriorityQueue se zadanou počáteční kapacitou, která seřadí své prvky podle zadaného komparátoru.
PriorityQueue pq = new PriorityQueue(int initialCapacity, Comparator comparator);
5. PriorityQueue (PriorityQueue c) : Vytvoří PriorityQueue obsahující prvky v zadané prioritní frontě.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. PriorityQueue (SortedSet c) : Vytvoří PriorityQueue obsahující prvky v zadané tříděné sadě.
PriorityQueue pq = new PriorityQueue(SortedSet c);
7. PriorityQueue (srovnávací komparátor): Vytvoří PriorityQueue s výchozí počáteční kapacitou a jejíž prvky jsou seřazeny podle zadaného komparátoru.
PriorityQueue pq = new PriorityQueue(Comparator c);
Příklad:
Níže uvedený příklad vysvětluje následující základní operace prioritní fronty.
porovnejte s řetězci v Javě
- boolean add(E element): Tato metoda vloží zadaný element do této prioritní fronty.
- public peek(): Tato metoda načte, ale neodstraní hlavičku této fronty, nebo vrátí hodnotu null, pokud je tato fronta prázdná.
- public poll(): Tato metoda načte a odstraní hlavičku této fronty, nebo vrátí hodnotu null, pokud je tato fronta prázdná.
Jáva
// Java program to demonstrate the> // working of PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String args[])> >{> >// Creating empty priority queue> >PriorityQueue pQueue =>new> PriorityQueue();> >// Adding items to the pQueue using add()> >pQueue.add(>10>);> >pQueue.add(>20>);> >pQueue.add(>15>);> >// Printing the top element of PriorityQueue> >System.out.println(pQueue.peek());> >// Printing the top element and removing it> >// from the PriorityQueue container> >System.out.println(pQueue.poll());> >// Printing the top element again> >System.out.println(pQueue.peek());> >}> }> |
>
>Výstup
10 10 15>
Operace na PriorityQueue
Podívejme se, jak provést několik často používaných operací ve třídě Priority Queue.
1. Přidání prvků: Abychom mohli přidat prvek do prioritní fronty, můžeme použít metodu add(). Objednávka vložení není zachována v PriorityQueue. Prvky jsou uloženy na základě pořadí priority, které je ve výchozím nastavení vzestupné.
Jáva
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >for>(>int> i=>0>;i<>3>;i++){> >pq.add(i);> >pq.add(>1>);> >}> >System.out.println(pq);> >}> }> |
>
>Výstup
[0, 1, 1, 1, 2, 1]>
Tiskem PriorityQueue nezískáme tříděné prvky.
Jáva
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> > >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> > >System.out.println(pq);> >}> }> |
>
>Výstup
[For, Geeks, Geeks]>
2. Odebrání prvků: Abychom odstranili prvek z prioritní fronty, můžeme použít metodu remove(). Pokud existuje více takových objektů, pak se první výskyt objektu odstraní. Kromě toho se k odstranění hlavy a jejímu vrácení používá také metoda poll().
Jáva
// Java program to remove elements> // from a PriorityQueue> import> java.util.*;> import> java.io.*;> public> class> PriorityQueueDemo {> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'Initial PriorityQueue '> + pq);> >// using the method> >pq.remove(>'Geeks'>);> >System.out.println(>'After Remove - '> + pq);> >System.out.println(>'Poll Method - '> + pq.poll());> >System.out.println(>'Final PriorityQueue - '> + pq);> >}> }> |
>
>Výstup
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Přístup k prvkům: Vzhledem k tomu, že Queue se řídí principem First In First Out, máme přístup pouze k hlavě fronty. Pro přístup k prvkům z prioritní fronty můžeme použít metodu peek().
gimp odstranit vodoznak
Jáva
// Java program to access elements> // from a PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String[] args)> >{> >// Creating a priority queue> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'PriorityQueue: '> + pq);> >// Using the peek() method> >String element = pq.peek();> >System.out.println(>'Accessed Element: '> + element);> >}> }> |
>
>Výstup
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Iterace fronty priority: Existuje několik způsobů, jak iterovat prostřednictvím PriorityQueue. Nejznámějším způsobem je převod fronty na pole a procházení pomocí cyklu for. Fronta má však také vestavěný iterátor, který lze použít k iteraci frontou.
Jáva
// Java program to iterate elements> // to a PriorityQueue> import> java.util.*;> public> class> PriorityQueueDemo {> >// Main Method> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >Iterator iterator = pq.iterator();> >while> (iterator.hasNext()) {> >System.out.print(iterator.next() +>);> >}> >}> }> |
>
>Výstup
For Geeks Geeks>
Příklad:
Jáva
import> java.util.PriorityQueue;> public> class> PriorityQueueExample {> >public> static> void> main(String[] args) {> > >// Create a priority queue with initial capacity 10> >PriorityQueue pq =>new> PriorityQueue(>10>);> > >// Add elements to the queue> >pq.add(>3>);> >pq.add(>1>);> >pq.add(>2>);> >pq.add(>5>);> >pq.add(>4>);> > >// Print the queue> >System.out.println(>'Priority queue: '> + pq);> > >// Peek at the top element of the queue> >System.out.println(>'Peek: '> + pq.peek());> > >// Remove the top element of the queue> >pq.poll();> > >// Print the queue again> >System.out.println(>'Priority queue after removing top element: '> + pq);> > >// Check if the queue contains a specific element> >System.out.println(>'Does the queue contain 3? '> + pq.contains(>3>));> > >// Get the size of the queue> >System.out.println(>'Size of queue: '> + pq.size());> > >// Remove all elements from the queue> >pq.clear();> > >// Check if the queue is empty> >System.out.println(>'Is the queue empty? '> + pq.isEmpty());> >}> }> |
>
>Výstup
Priority queue: [1, 3, 2, 5, 4] Peek: 1 Priority queue after removing top element: [2, 3, 4, 5] Does the queue contain 3? true Size of queue: 4 Is the queue empty? true>
Příklady v reálném čase:
Prioritní fronta je datová struktura, ve které jsou prvky seřazeny podle priority, přičemž prvky s nejvyšší prioritou se objevují na začátku fronty. Zde je několik příkladů ze skutečného světa, kde lze použít prioritní fronty:
- Plánování úloh: V operačních systémech se prioritní fronty používají k plánování úloh na základě jejich úrovní priority. Například úloha s vysokou prioritou, jako je kritická aktualizace systému, může být naplánována před úlohou s nižší prioritou, jako je proces zálohování na pozadí. Pohotovost: Na pohotovosti v nemocnici jsou pacienti tříděni podle závažnosti jejich stavu, přičemž jako první jsou ošetřeni ti v kritickém stavu. Prioritní frontu lze použít ke správě pořadí, ve kterém pacienty vidí lékaři a sestry. Síťové směrování: V počítačových sítích se pro řízení toku datových paketů používají prioritní fronty. Pakety s vysokou prioritou, jako jsou hlasová a video data, mohou mít prioritu před daty s nižší prioritou, jako jsou e-maily a přenosy souborů. Doprava: V systémech řízení provozu lze pro řízení toku provozu použít prioritní fronty. Například záchranná vozidla, jako jsou sanitky, mohou mít přednost před ostatními vozidly, aby bylo zajištěno, že se rychle dostanou do cíle. Plánování úloh: V systémech plánování úloh lze prioritní fronty používat ke správě pořadí, ve kterém jsou úlohy prováděny. Úlohy s vysokou prioritou, jako jsou důležité aktualizace systému, mohou být naplánovány před úlohami s nižší prioritou, jako je zálohování dat. Online tržiště: Na online tržištích lze ke správě dodávek produktů zákazníkům použít prioritní fronty. Objednávky s vysokou prioritou, jako je expresní doprava, mohou mít přednost před standardními zásilkovými objednávkami.
Celkově jsou prioritní fronty užitečnou datovou strukturou pro správu úkolů a zdrojů na základě jejich úrovní priority v různých scénářích reálného světa.
Metody ve třídě PriorityQueue
| METODA | POPIS |
|---|---|
| přidat (a a) | Vloží zadaný prvek do této prioritní fronty. |
| Průhledná() | Odebere všechny prvky z této prioritní fronty. |
| srovnávač() | Vrátí komparátor použitý k řazení prvků v této frontě nebo hodnotu null, pokud je tato fronta seřazena podle přirozeného uspořádání jejích prvků. |
| obsahuje? (Objekt o) | Vrátí hodnotu true, pokud tato fronta obsahuje zadaný prvek. |
| pro každého? (spotřebitelská akce) | Provede danou akci pro každý prvek Iterable, dokud nejsou zpracovány všechny prvky nebo akce nevyvolá výjimku. |
| iterátor() | Vrátí iterátor nad prvky v této frontě. |
| nabídnout? (E e) | Vloží zadaný prvek do této prioritní fronty. |
| odstranit? (Objekt o) | Odebere jednu instanci zadaného prvku z této fronty, pokud je přítomna. |
| odstranit vše? (kolekce c) | Odebere všechny prvky této kolekce, které jsou také obsaženy v zadané kolekci (volitelná operace). |
| removeIf? (Predikátový filtr) | Odebere všechny prvky této kolekce, které splňují daný predikát. |
| keepAll? (Kolekce c) | Zachová pouze prvky v této kolekci, které jsou obsaženy v zadané kolekci (volitelná operace). |
| rozdělovač() | Vytvoří spliterator s pozdní vazbou a rychlým selháním nad prvky v této frontě. |
| toArray() | Vrátí pole obsahující všechny prvky v této frontě. |
| toArray?(T[] a) | Vrátí pole obsahující všechny prvky v této frontě; typ runtime vráceného pole je typ zadaného pole. |
Metody Deklarované ve třídě java.util.AbstractQueue
| METODA | POPIS |
|---|---|
| addAll(kolekce c) | Přidá všechny prvky v zadané kolekci do této fronty. |
| živel() | Načte, ale neodstraní, hlavu této fronty. |
| odstranit() | Načte a odstraní hlavu této fronty. |
Metody Deklarované ve třídě java.util.AbstractCollection
| METODA | POPIS |
|---|---|
| obsahuje vše (kolekce c) | Vrátí hodnotu true, pokud tato kolekce obsahuje všechny prvky v zadané kolekci. |
| je prázdný() | Vrátí hodnotu true, pokud tato kolekce neobsahuje žádné prvky. |
| toString() | Vrátí řetězcovou reprezentaci této kolekce. |
Metody Deklarované v rozhraní java.util.Collection
| METODA | POPIS |
|---|---|
| obsahuje vše (kolekce c) | Vrátí hodnotu true, pokud tato kolekce obsahuje všechny prvky v zadané kolekci. |
| rovná se (objekt o) | Porovná zadaný objekt s touto kolekcí pro dosažení rovnosti. |
| hashCode() | Vrátí hodnotu hash kódu pro tuto kolekci. |
| je prázdný() | Vrátí hodnotu true, pokud tato kolekce neobsahuje žádné prvky. |
| paralelní proud() | Vrátí možná paralelní proud s touto sbírkou jako zdrojem. |
| velikost() | Vrátí počet prvků v této kolekci. |
| proud() | Vrátí sekvenční stream s touto sbírkou jako zdrojem. |
| toArray (generátor IntFunction) | Vrátí pole obsahující všechny prvky v této kolekci pomocí poskytnuté funkce generátoru k přidělení vráceného pole. |
Metody Deklarované v rozhraní java.util.Queue
| METODA | POPIS |
|---|---|
| nahlédnout () | Načte, ale neodstraní hlavičku této fronty, nebo vrátí hodnotu null, pokud je tato fronta prázdná. |
| hlasování() | Načte a odstraní hlavičku této fronty nebo vrátí hodnotu null, pokud je tato fronta prázdná. |
Aplikace :
- Implementace Dijkstrových a Primových algoritmů.
- Maximalizovat součet pole po K negacích
Související články :
- Třída Java.util.PriorityQueue v Javě
- Implementujte PriorityQueue prostřednictvím komparátoru v Javě