priority queue
Főnév
priority queue (tsz. priority queues)
A priority queue (prioritási sor) egy olyan adatstruktúra, ahol minden elemhez tartozik egy prioritás, és mindig a legnagyobb (vagy legkisebb) prioritású elem kerül elsőként kiválasztásra — nem feltétlenül a legrégebben beszúrt elem (mint egy sima sorban, azaz FIFO esetén).
🧠 Alapelvek
A prioritási sor egy absztrakt adatstruktúra, amit különböző konkrét struktúrákkal lehet megvalósítani:
| Alapstruktúra | Megvalósítási példa |
|---|---|
| Bináris heap | 🔼 Leggyakoribb (pl. C++ STL) |
| Fibonacci heap | 🔁 Dijkstra, Prim, haladó use case |
| Rendezett lista | 🐌 Lassan épül, gyors kivétel |
| Rendezett tömb | 🐌 Gyors keresés, lassú betét |
⚙️ Műveletek
| Művelet | Leírás | Bináris heap ideje |
|---|---|---|
insert(x) |
Elem hozzáadása a sorhoz | O(log n) |
getMax()/getMin() |
Legnagyobb/kisebb prioritású lekérdezése | O(1) |
extractMax()/extractMin() |
Legnagyobb/kisebb eltávolítása | O(log n) |
isEmpty() |
Ellenőrzi, hogy üres-e | O(1) |
📊 Példa
Tegyük fel, hogy a prioritás = szám értéke:
Insert sorrendben:
insert(4), insert(1), insert(7), insert(2)
Max-priority queue:
getMax()→ 7extractMax()→ 7, marad: [4, 2, 1]
Min-priority queue:
getMin()→ 1extractMin()→ 1, marad: [2, 4, 7]
📦 C++ STL példák
🧱 priority_queue (alapértelmezett: max-heap)
#include <queue>
#include <vector>
#include <functional>
std::priority_queue<int> maxPQ;
maxPQ.push(5);
maxPQ.push(2);
maxPQ.push(8);
std::cout << maxPQ.top(); // 8
maxPQ.pop();
🔽 Min-heap: trükk negatívval vagy komparátorral
std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;
minPQ.push(5);
minPQ.push(2);
minPQ.push(8);
std::cout << minPQ.top(); // 2
🧠 Alkalmazások
- Graf algoritmusok: Dijkstra, Prim (útvonal, MST)
- CPU ütemezés
- Üzenetprioritás kezelése (pl. hálózatokban)
- Online eseményfeldolgozás (pl. játékmotorok)
- Heapsort
- Kétkupacos medián-számítás
🔍 Megvalósítási lehetőségek összehasonlítása
| Megvalósítás | insert | extractMin/Max | getMin/Max | merge |
|---|---|---|---|---|
| Bináris heap | O(log n) | O(log n) | O(1) | O(n) |
| Binomiális heap | O(log n) | O(log n) | O(1) | O(log n) |
| Fibonacci heap | O(1)* | O(log n)* | O(1) | O(1) |
| Rendezett lista | O(n) | O(1) | O(1) | O(n) |
| Rendezett tömb | O(log n) | O(1) | O(1) | O(n) |
✅ Összefoglalás
A prioritási sor nem feltétlenül időrend alapján, hanem prioritás alapján dolgozza fel az elemeket. Ezért hatékony, ha a legfontosabb vagy legnagyobb értékű elemet gyorsan akarjuk elérni.
A bináris heap az alapértelmezett háttérszerkezet, de bizonyos esetekben a Fibonacci heap jobb teljesítményt nyújthat (pl. sok decreaseKey esetén).
- priority queue - Szótár.net (en-hu)
- priority queue - Sztaki (en-hu)
- priority queue - Merriam–Webster
- priority queue - Cambridge
- priority queue - WordNet
- priority queue - Яндекс (en-ru)
- priority queue - Google (en-hu)
- priority queue - Wikidata
- priority queue - Wikipédia (angol)