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).
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ű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) |
Tegyük fel, hogy a prioritás = szám értéke:
insert(4), insert(1), insert(7), insert(2)
getMax() → 7extractMax() → 7, marad:
getMin() → 1extractMin() → 1, marad:
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();
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
| 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) |
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).