Mis on virn (andmestruktuuride kontekstis)?

Häll (heap) — see spetsialiseeritud puu struktuur, mida kasutatakse andmestruktuurina. Hälli peamine omadus on osaline järjepidevus: iga tipu puhul kehtib tingimus, et vanema tipu väärtus on suurem või võrdne tema laste väärtustega (max-heap) või väiksem või võrdne (min-heap).

Peamised omadused:

Binaarne puu: Enamasti rakendatakse seda binaarse puuna, kus igal tipul on mitte rohkem kui kaks last.
Täielik binaarne puu: Kõigil tasemetel, välja arvatud võib-olla viimasel, on puu täielikult täidetud. Viimase taseme tipud täidetakse vasakult paremale. See võimaldab tõhusalt hoida hälli massiivina.
Hälli omadus:
- Max-heap: Iga tipu väärtus on suurem või võrdne tema laste väärtustega. Kõige suurem element asub alati juurel.
- Min-heap: Iga tipu väärtus on väiksem või võrdne tema laste väärtustega. Kõige väiksem element asub alati juurel.

Hälli operatsioonid:

Elementi lisamine: Uue elemendi lisamine ja hälli omaduse säilitamine.
Elementi eemaldamine: Juureelemendi (kõige suurema või väiksema — sõltuvalt hälli tüübist) eemaldamine ja hälli omaduse säilitamine.
Hälli loomine: Loob massiivist.

Hälli kasutus:

Sortimine: Heapsort algoritm.
Prioriteedijärjekorrad: Efektiivne rakendus, kus elemendid töödeldakse prioriteedi järgi.
Otsingualgoritmid: Näiteks k-nda suurima elemendi otsimine.
Graafialgoritmid: Näiteks Dijkstra algoritm.

Hälli esitamine massiivina:

Kuna häll on täielik binaarne puu, saab seda tõhusalt hoida massiivina ilma viiteta.

Kui tip on indeksil i, asub tema vasak laps indeksil 2*i + 1.
Tema parem laps indeksil 2*i + 2.
Tema vanem indeksil (i - 1) / 2.

# Min-heap näide massiivina
heap_array = [10, 15, 20, 17, 25, 30]

# Juure: heap_array[0] = 10
# Vasak laps: heap_array[2*0 + 1] = heap_array[1] = 15
# Parem laps: heap_array[2*0 + 2] = heap_array[2] = 20
# Vanem elemendil indeksil 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15