double-ended priority queue (tsz. double-ended priority queues)
✅ 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.
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 |
getMin, getMax, O(log n) beszúrás és törlé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) |
5 ← min (root)
/ \
100 20 ← max-szint
/ \ / \
8 200 15 25 ← min-szint
getMin() → 5getMax() → 100 (vagy másik gyerek szint csúcsa)
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(); }
};
std::priority_queue-t akarsz használni: az nem támogat dupla végűséget natívan.
| 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 |