double-ended priority queue
Főnév
double-ended priority queue (tsz. double-ended priority queues)
- (informatika) A double-ended priority queue (röviden DEPQ) egy speciális prioritási sor, amely egyszerre támogatja:
✅ A legnagyobb és a legkisebb prioritású elem hatékony lekérdezését és törlését.
Ez azt jelenti, hogy nemcsak a min vagy max elemet tudod kivenni, mint egy normál heap esetén, hanem mindkettőt, gyorsan.
🧠 Alapgondolat
A DEPQ egy olyan adatstruktúra, amely támogatja a következő műveleteket:
| Művelet | Leírás |
|---|---|
insert(x) |
Elem beszúrása |
getMin() |
Minimum érték lekérdezése |
getMax() |
Maximum érték lekérdezése |
deleteMin() |
Legkisebb érték törlése |
deleteMax() |
Legnagyobb érték törlése |
🔁 Megvalósítási lehetőségek
1. Min-max heap (leggyakoribb)
- Egy bináris fa, ahol páros szinteken a minimum, páratlanokon a maximum tulajdonság teljesül.
- O(1)
getMin,getMax, O(log n) beszúrás és törlés
2. Két heap használata (min-heap + max-heap)
- Egy min-heap és egy max-heap szinkronizált működése
- Duplikált tárolás miatt extra könyvelés kell
3. Balanced BST (pl. AVL tree, Treap, Red-Black Tree)
- Balról a minimum, jobbról a maximum könnyen elérhető
- Minden művelet: O(log n)
📈 Összehasonlítás
| Adatszerkezet | getMin |
getMax |
insert |
deleteMin |
deleteMax |
|---|---|---|---|---|---|
| Min-heap | O(1) | O(n) | O(log n) | O(log n) | O(n) |
| Max-heap | O(n) | O(1) | O(log n) | O(n) | O(log n) |
| Min-max heap | O(1) | O(1) | O(log n) | O(log n) | O(log n) |
| AVL tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
🔧 Példa – Min-max heap
5 ← min (root)
/ \
100 20 ← max-szint
/ \ / \
8 200 15 25 ← min-szint
getMin()→ 5getMax()→ 100 (vagy másik gyerek szint csúcsa)
🛠️ C++ struktúrával (alapötlet)
Egy C++ sablonos DEPQ (BST alapján):
#include <set>
template<typename T>
class DEPQ {
std::multiset<T> tree;
public:
void insert(const T& val) { tree.insert(val); }
T getMin() const { return *tree.begin(); }
T getMax() const { return *tree.rbegin(); }
void deleteMin() { tree.erase(tree.begin()); }
void deleteMax() { auto it = tree.end(); --it; tree.erase(it); }
bool isEmpty() const { return tree.empty(); }
};
- Egyszerű, de minden művelet O(log n).
- Ha
std::priority_queue-t akarsz használni: az nem támogat dupla végűséget natívan.
📚 Alkalmazások
- Intervallumok kezelése
- Legkisebb és legnagyobb elemek gyors elérése
- Scheduling (ütemezés) több szempont alapján
- Valós idejű rendszerek (például hang- vagy adatfolyamok szűrése, ahol mindkét vég érdekes)
✅ Összefoglalás
| Jellemző | DEPQ |
|---|---|
| FIFO? | ❌ nem, prioritásalapú |
| Mindkét vég kezelhető? | ✅ igen (min és max) |
| Leggyakoribb forma | Min-max heap |
| Sebesség | O(1) lekérdezés, O(log n) módosítás |
| Alternatíva | AVL tree, Red-Black Tree, két heap |
- double-ended priority queue - Szótár.net (en-hu)
- double-ended priority queue - Sztaki (en-hu)
- double-ended priority queue - Merriam–Webster
- double-ended priority queue - Cambridge
- double-ended priority queue - WordNet
- double-ended priority queue - Яндекс (en-ru)
- double-ended priority queue - Google (en-hu)
- double-ended priority queue - Wikidata
- double-ended priority queue - Wikipédia (angol)