priority queue

Üdvözlöm, Ön a priority queue szó jelentését keresi. A DICTIOUS-ban nem csak a priority queue szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a priority queue szót egyes és többes számban mondani. Minden, amit a priority queue szóról tudni kell, itt található. A priority queue szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Apriority queue és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Főnév

priority queue (tsz. priority queues)

  1. (informatika) elsőbbségi sor

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() → 7
  • extractMax() → 7, marad:

Min-priority queue:

  • getMin() → 1
  • extractMin() → 1, marad:



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