szó jelentését keresi. A DICTIOUS-ban nem csak a
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
szót egyes és többes számban mondani. Minden, amit a
szóról tudni kell, itt található. A
szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
é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
heap data structure (tsz. heap data structures)
- (informatika) A heap (magyarul: kupac) egy speciális fa-alapú adatszerkezet, amelyet általában prioritásos sorok megvalósítására használnak. A heapre jellemző, hogy:
- részben rendezett (nem teljesen sorba rendezett),
- gyorsan támogat beszúrási és legnagyobb/legkisebb elem kivételi műveleteket,
- speciális bináris fa, amely komplett bináris fa szerkezetű.
A heap nagyon hasznos olyan algoritmusokban, ahol a legnagyobb vagy legkisebb elemmel gyakran kell műveleteket végezni (pl. Dijkstra algoritmus, Huffman kódolás, ütemezés, sorrendezés).
Típusai
A heapnek két fő típusa van:
- Max-heap
- A szülő csomópont értéke nagyobb vagy egyenlő, mint a gyermekei értéke.
- A gyökércsomópont tartalmazza a legnagyobb elemet.
- Min-heap
- A szülő csomópont értéke kisebb vagy egyenlő, mint a gyermekei értéke.
- A gyökércsomópont tartalmazza a legkisebb elemet.
Szerkezeti tulajdonságok
- A heap komplett bináris fa:
- Minden szinten (kivéve esetleg az utolsót) az összes csomópont teljesen ki van töltve.
- Az utolsó szintet balról jobbra töltjük fel.
- Ez a tulajdonság lehetővé teszi, hogy a heapet tömbben tároljuk fa helyett, amely gyors és helytakarékos.
Memória reprezentáció (tömb)
A heapet általában tömbben valósítják meg (pl. C++ std::vector, Java ArrayList).
Ha a gyökér az index 0, akkor:
- bal gyermek indexe:
2 * i + 1
- jobb gyermek indexe:
2 * i + 2
- szülő indexe:
(i - 1) / 2
Ez a számítás lehetővé teszi a gyors navigációt a fa szerkezetében további pointerek nélkül.
Alapműveletek
1. Beszúrás (Insert)
- A beszúrás a heap utolsó szabad helyére történik (az utolsó szint bal oldalára).
- Ezután “felfelé perkoltatjuk” az új elemet (heapify up), amíg a heap tulajdonság meg nem marad.
- Időkomplexitás: O(log n) (a fa magassága miatt).
- A heap gyökerét (legnagyobb vagy legkisebb elem) kivesszük.
- A legutolsó elemet helyezzük a gyökér helyére.
- Ezután “lefuttatjuk lefelé” (heapify down vagy sift down), hogy visszaállítsuk a heap tulajdonságot.
- Időkomplexitás: O(log n).
3. Csúcselem lekérdezése (Peek / Top)
- A gyökérelem lekérdezése (de nem kivétele).
- Időkomplexitás: O(1).
4. Heapify (építés tömbből)
- Ha egy tömbből akarunk heapet építeni, megtehetjük O(n) időben bottom-up heapify módszerrel.
- Nagyon gyorsan lehet így heapet létrehozni.
Példa C++-ban (min-heap és max-heap)
#include <queue>
#include <vector>
#include <functional>
#include <iostream>
using namespace std;
int main() {
// Max-heap
priority_queue<int> maxHeap;
maxHeap.push(10);
maxHeap.push(30);
maxHeap.push(20);
cout << "Max-heap top: " << maxHeap.top() << endl; // 30
// Min-heap
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(10);
minHeap.push(30);
minHeap.push(20);
cout << "Min-heap top: " << minHeap.top() << endl; // 10
return 0;
}
- C++
priority_queue alapból max-heap, de a greater<int> predikátummal min-heap-ként is használható.
Használati területek
- Prioritásos sorok
- Leggyakoribb alkalmazási terület.
- Olyan sor, ahol a legfontosabb (legnagyobb prioritású) elem kerül előre.
- Dijkstra algoritmus (legrövidebb út)
- A következő minimális távolságú csúcs gyors kiválasztása heap segítségével.
- Huffman kódolás
- A legkisebb valószínűségű csomópontok kiválasztása heapből.
- Ütemező rendszerek
- Feladatok prioritás alapján sorba állítása.
- Heap sort
- A heap adatszerkezetre épülő hatékony O(n log n) időkomplexitású rendező algoritmus.
Heap Sort algoritmus
- Építs egy max-heapet a tömbből.
- Iteratív módon:
- A gyökeret (legnagyobb elem) helyezzük a tömb végére.
- Csökkentsük a heap méretét eggyel.
- Végezze el a heapify down lépést a gyökérre.
- Az eredmény rendezett tömb lesz.
Időkomplexitás:
- Építés: O(n)
- Rendezés: O(n log n)
Térkomplexitás: O(1) (in-place).
Előnyök és hátrányok
Előnyök
- Gyors csúcselem elérés: O(1).
- Gyors beszúrás és kivétel: O(log n).
- Egyszerű implementáció tömbbel.
- Hatékony prioritásos sor-ként.
Hátrányok
- Nincs teljes rendezés (csak a csúcs garantált).
- Lineáris keresés: Ha tetszőleges elemre keresünk, az O(n) idő.
- Nem támogat gyors véletlen elérést (mint pl. egy tömb vagy vektor).
Alternatívák
- Balanced BST (pl. AVL, Red-Black Tree):
- Teljesen rendezett.
- Gyors beszúrás, törlés, keresés (O(log n)).
- Binomiális heap, Fibonacci heap:
- További heap-változatok, jobb elméleti teljesítménnyel bizonyos műveleteknél.
Összefoglalás
A heap egy rendkívül hasznos, egyszerűen implementálható adatszerkezet, amely különösen alkalmas prioritásos sorokhoz és olyan algoritmusokhoz, ahol gyakran kell a legnagyobb vagy legkisebb elemet gyorsan elérni vagy kivenni.
Legfontosabb tulajdonságai:
| Művelet
|
Időkomplexitás
|
| csúcs lekérdezése
|
O(1)
|
| beszúrás
|
O(log n)
|
| legnagyobb/legkisebb kivétele
|
O(log n)
|
| heapify (építés tömbből)
|
O(n)
|
Példák használatra:
- prioritásos sor
- Dijkstra algoritmus
- Huffman kódolás
- heap sort
- ütemező rendszerek
A heap tehát egy nélkülözhetetlen eszköz a programozó eszköztárában, és a kombinált teljesítmény + egyszerűség miatt nagyon gyakran használják.
Variants