Mi az a halom (adatszerkezetek kontextusában)?

Egy halom (heap) egy speciális fa, amely adatstruktúraként használható. A halom fő tulajdonsága a részleges rendezés: minden csúcs esetében a szülő csúcs értéke nagyobb vagy egyenlő, mint bármelyik gyermekének értéke (max-heap), vagy kisebb vagy egyenlő (min-heap).

Fő jellemzők:

• Kettős fa: Általában kettős faként valósítják meg, ahol minden csúcsnak legfeljebb két leszármazottja van.
• Teljes kettős fa: Minden szinten, kivéve esetleg az utolsót, a fa teljesen kitöltött. Az utolsó szinten lévő csúcsokat balról jobbra töltik ki. Ez lehetővé teszi a halom hatékony tárolását tömbként.
• A halom tulajdonsága:
  • Max-heap: Minden csúcs értéke nagyobb vagy egyenlő, mint leszármazottainak értékei. A legnagyobb elem mindig a gyökérben található.
  • Min-heap: Minden csúcs értéke kisebb vagy egyenlő, mint leszármazottainak értékei. A legkisebb elem mindig a gyökérben található.

Fő műveletek a halommal:

• Elem beszúrása: Új elem hozzáadása és a halom tulajdonságának fenntartása.
• Elem törlése: A gyökér elem törlése (legnagyobb vagy legkisebb, a halom típusától függően), és a halom tulajdonságának fenntartása.
• Halom építése: Halom építése tömbből.

A halom alkalmazásai:

• Rendezés: Halom rendezési algoritmus (Heapsort).
• Prioritási sorok: Hatékony megvalósítás olyan sorokhoz, ahol az elemek prioritás szerint kerülnek feldolgozásra.
• Keresési algoritmusok: Például a k-dik legnagyobb elem keresése.
• Graf algoritmusok: Például Dijkstra algoritmusa.

A halom tömbben való ábrázolása:

Mivel a halom teljes kettős fa, hatékonyan tárolható tömbben pointerek használata nélkül.

• Ha egy csúcs indexe i, akkor bal gyermekének indexe 2*i + 1.
• Jobb gyermekének indexe 2*i + 2.
• Szülője indexe (i - 1) / 2.

# Példa egy min-heap tömbben való ábrázolására
heap_array = [10, 15, 20, 17, 25, 30]

# Gyökér: heap_array[0] = 10
# A gyökér bal gyermek: heap_array[2*0 + 1] = heap_array[1] = 15
# A gyökér jobb gyermek: heap_array[2*0 + 2] = heap_array[2] = 20
# Az index 3 (17) elem szülője: heap_array[(3-1)//2] = heap_array[1] = 15