Tartalomjegyzék:
Meghatározás - Mit jelent a halom?
A halom az adatszerkezet összefüggésében egy faalapú adatszerkezet, amely kielégíti a halom tulajdonságát, ahol minden elemhez kulcs értéket vagy súlyt rendelnek. Az alacsonyabb értékű kulcsnak mindig van egy szülőcsomópontja egy magasabb értékű kulcsmal. Ezt max-halom struktúrának nevezzük, és az összes csomópont közül a gyökércsomópont rendelkezik a legmagasabb kulcsmal.
Időnként a faalapú struktúrák fordított struktúrájú szabályt alkalmaznak, ahol egy magasabb értékű elemmel mindig alacsonyabb értékű kulcs van, mint szülőcsomópont. Ezt min-halom struktúrának nevezzük, és az összes csomópont közül a gyökércsomópontnak van a legalacsonyabb kulcsa.
A Techopedia magyarázza a Heap-ot
Nincs gyakorlati korlátozás az egyes csomópontokban lévő gyermekek számára egy halomban, annak ellenére, hogy általában minden csomópontnak kettő van. A halomot tekintik az absztrakt adattípus leghatékonyabb megvalósításának, amelyet prioritási sornak hívnak. A halom megvalósítása elengedhetetlen a különféle gráf algoritmusokban (ideértve a Dijkstra algoritmust is), valamint a halom sort rendezési algoritmusban.
A halmoknak számos variációja van, amelyek nagy hatékonyságú elvont adattípus prioritási sor megvalósításként működnek. Számos alkalmazás, például gráf algoritmusok, prioritási sorok végrehajtását igényli.
A tömb a halom leggyakoribb megvalósítási formája, ahol nincs szükség mutatóra az elemek közötti összekapcsoláshoz.
A halom több műveletet hajt végre, beleértve:
- Find-max: A legmagasabb kulcscsomópontot keresi a csomópontcsoportok között
- Find-min: A csomópontcsoportok között a legalacsonyabb kulcscsomópontot keresi
- Delete-max: Törli a legmagasabb kulcscsomópontot a csomópontcsoportok között
- Törlés perc: Törli a legalacsonyabb kulcscsomópontot a csomópontcsoportok között
A halmok olyan funkciókat is tartalmaznak, amelyek egyesítést, beszúrást és kulcsfontosságú változtatásokat hajtanak végre.
Ezt a meghatározást az adatszerkezet összefüggésében írták le
