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