Mis on virn programmeerimise kontekstis ja millised virnade tüübid eksisteerivad?

Heap — see on mälu piirk operatiivmälus, mida kasutatakse dünaamiliseks mäe jaotamiseks programmi täitmise ajal.

Peamised omadused:

• Mälu eraldatakse ja vabastatakse selgelt programmeerija (või prügikoristaja) poolt.
• Mäe eraldamise/vabastamise järjekord ei ole rangelt määratletud.
• Mäe haldamine on keerulisem kui virnas, mis võib põhjustada fragmentatsiooni ja mäe lekkimist.

Kuhjade tüübid (andmestruktuuride kontekstis):

• Binaarne mägi (Binary Heap): puu, mis vastab mäe omadusele. Iga sõlm (välja arvatud juur) on väärtuselt väiksem või suurem kui selle vanema väärtus.
  • Min Heap: Vanema väärtus on alati väiksem või võrdne järeltulijate väärtustega. Väikseim element asub juurel.
  • Max Heap: Vanema väärtus on alati suurem või võrdne järeltulijate väärtustega. Suurim element asub juurel.
• Binomiaalne mägi (Binomial Heap): binomiaalsete puude kogu, mis vastab teatud omadustele. Toetab tõhusaid ühendamisoperatsioone.
• Fibonacci mägi (Fibonacci Heap): andmestruktuur, mida kasutatakse algoritmides, näiteks Dijkstra algoritmis. Tagab tõhusama amortiseeritud ajakulu teatud operatsioonidele võrreldes binaarse mäega.
• Paari mägi (Pairing Heap): lihtne realiseerida andmestruktuur, millel on head amortiseeritud ajakulu.
• Vasakpoolne mägi (Leftist Heap): andmestruktuur, mis hõlbustab tõhusat ühendamist. Oluline omadus on "rango" või "nulli tee pikkus", mida kasutatakse kiireks ühendamiseks.

Need kuhjade tüübid kasutatakse erinevates algoritmides, näiteks sorteerimisel (Heap Sort), prioriteedijärjekordade realiseerimisel, lühima tee otsimise algoritmides ja mujal. Konkreetse kuhja tüübi valik sõltub vajalike operatsioonide ja nende ajafunktsionaalsuse nõuetest.