Üdvözlöm, Ön a
Fibonacci heap szó jelentését keresi. A DICTIOUS-ban nem csak a
Fibonacci heap 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
Fibonacci heap szót egyes és többes számban mondani. Minden, amit a
Fibonacci heap szóról tudni kell, itt található. A
Fibonacci heap szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
Fibonacci heap é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
Fibonacci heap (tsz. Fibonacci heaps)
- (informatika) Fibonacci-kupac
A Fibonacci heap egy fejlett és hatékony prioritási sor adatszerkezet, amely több fontos műveletet képes amortizáltan gyorsabban végrehajtani, mint a bináris vagy binomiális heapek. Nevét a Fibonacci-számok alapján működő szerkezeti tulajdonságairól kapta.
🎯 Alapötlet
A Fibonacci heap:
- Több fából álló erdőt tartalmaz (nem egyetlen bináris fa),
- Az elemek nem teljesen rendezettek, de elég jól, hogy hatékonyan működjön,
- A legkisebb elem mindig gyorsan elérhető,
- Néhány művelet halasztott (lazy) módon történik, így bizonyos műveletek gyorsabbak lesznek, és az időigény eloszlik több művelet között (→ amortizált idő).
🧱 Felépítés
- Tartalmaz egy gyökérlistát: fák gyűjteményét, ahol minden fa egy minimálisan rendezett fa.
- Minden elemnek van:
- értéke
- szülő és gyerek mutató
- fivér mutatók (circular doubly-linked list)
- fok (gyerekei száma)
- jelző (mark), hogy visszarakás történt-e
🔢 Fontos műveletek és időigényük
| Művelet
|
Időkomplexitás
|
insert
|
O(1) amortizált
|
getMin
|
O(1)
|
extractMin
|
O(log n) amortizált
|
decreaseKey
|
O(1) amortizált
|
delete
|
O(log n) amortizált
|
merge (union)
|
O(1)
|
👉 A decreaseKey és merge miatt Fibonacci heap az egyik leggyorsabb adatstruktúra Dijkstra algoritmusban.
🔄 Működés röviden
insert(x)
- Új csúcsot adunk a gyökérlistához.
- Frissítjük a minimum mutatót, ha szükséges.
merge(H1, H2)
- Két gyökérlistát összefűzünk (→ O(1))
- Minimum frissítése
getMin()
- Csak visszaadjuk a
min mutatót
- Kivesszük a minimális értékű gyökeret.
- Gyerekeit átrakjuk a gyökérlistába.
- Konszolidáció:
- Az azonos fokszámú fákat összefésüljük, míg minden fokhoz csak egy fa lesz.
- Így logaritmikus számú fa marad (Fibonacci-számok határozzák meg a maximumot).
decreaseKey(x, newKey)
- Csökkenti egy csúcs értékét.
- Ha kisebb lesz a szülőjénél → cut és a gyökérlistához adjuk.
- Ha a szülő már jelölve van (azaz egyszer már elvesztett gyereket), őt is kivágjuk (cascading cut).
- Ez biztosítja a strukturális egyensúlyt.
📊 Miért „Fibonacci”?
- A konszolidáció során egy fa fokát Fibonacci-számok határozzák meg.
- Ez garantálja, hogy egy fa magassága logaritmikusan nő az elemek számával:
size(x) ≥ F_{degree(x)+2} ≥ φ^{degree(x)}, ahol φ ≈ 1.618 (aranymetszés).
📈 Előnyök
- Kiemelkedő amortizált teljesítmény:
- Gyors
insert, decreaseKey, merge
- Leggyorsabb ismert struktúra Dijkstra, Prim algoritmusokhoz.
- Hatékony tömeges feldolgozás esetén.
❗ Hátrányok
- Nehéz implementáció (összehasonlítva bináris kupaccal).
- A valóságban ritkán gyorsabb, hacsak nem sok
decreaseKey van.
- Magas konstansok miatt sok esetben bináris heap is megfelelőbb.
🧠 Alkalmazások
- Dijkstra algoritmus (sok
decreaseKey)
- Prim algoritmus
- MST és shortest path algoritmusok
- Dinamikus prioritási sorok
🧪 C++ kódvázlat (egyszerűsített)
struct Node {
int key;
int degree;
Node* parent;
Node* child;
Node* left;
Node* right;
bool mark;
Node(int k) : key(k), degree(0), parent(nullptr), child(nullptr),
left(this), right(this), mark(false) {}
};
// Csomópontokat körkörös láncolt listába fűzzük, gyökérlista itt van
// A teljes implementáció bonyolult, ~500 soros is lehet.
✅ Összefoglalás
| Tulajdonság
|
Fibonacci Heap
|
| Elérési idő minimumra
|
O(1)
|
| Törlés minimum
|
O(log n) amortizált
|
decreaseKey
|
O(1) amortizált
|
| Egyesítés (merge)
|
O(1)
|
| Használat
|
Haladó algoritmusoknál optimális
|
| Nehézség
|
Magas implementációs komplexitás
|