Mi az a halom?

Yük (heap) egy speciális fastruktúra, amely megfelel a halom tulajdonságának. Ez a tulajdonság kimondja, hogy bármely csúcs esetén, kivéve a gyökeret, ennek a csúcsnak a kulcsértéke bizonyos összefüggésben kell legyen a szülő kulcsértékével. Két fő típusú halom létezik:

• Max-halom (Max-heap): Minden csúcs kulcsértéke nem kisebb, mint gyermekei kulcsértéke. A legnagyobb elem a gyökérben található.
• Min-halom (Min-heap): Minden csúcs kulcsértéke nem nagyobb, mint gyermekei kulcsértéke. A legkisebb elem a gyökérben található.

A halom általában tömbként van megvalósítva, ami hatékony hozzáférést tesz lehetővé az elemekhez és műveletek végrehajtását. A szülő és gyermek közötti kapcsolat a tömbben a következő:

• Egy i indexű elem esetén (0-tól kezdve), bal gyermek az 2i + 1 indexen található.
• Jobb gyermek az 2i + 2 indexen található.
• Szülő az floor((i - 1) / 2) indexen található.

A halom fő műveletei:

• Beszúrás (Insert): Új elem hozzáadása. Végrehajtási idő O(log n), ahol n az elemek száma.
• Max- vagy Min-kivonás (Extract-Max / Extract-Min): A legnagyobb (max-halomban) vagy legkisebb (min-halomban) elem eltávolítása és visszaadása. Végrehajtási idő O(log n).
• Heapify (Halomépítés): Bármilyen tömb átalakítása halommá. Végrehajtási idő O(n).

A halmok használata algoritmusokban, például rendezésben (pl. heapsort), prioritási sorokban és legrövidebb út kereső algoritmusokban (pl. Dijkstra algoritmus) történik.