Halda

Halda je datová struktura tvořená „uzly“, které obsahují hodnoty. Typická halda má nahoře uzel kořene, pod kterým mohou být přímo umístěny dva nebo více potomků. Každý uzel může mít dva nebo více potomků, takže halda se s každým dalším potomkem rozšiřuje. Při vizuálním zobrazení vypadá halda jako strom obrácený vzhůru nohama a její celkový tvar připomíná haldu.

Ačkoli každý uzel v haldě může mít dva nebo více potomků (také nazývaných „děti“), většina hald omezuje každý uzel na dva potomky. Tyto typy hald se také nazývají binární haldy a mohou se používat k ukládání seřazených dat. Například „binární halda maxima“ ukládá nejvyšší hodnotu do kořenového uzlu. Druhá a třetí nejvyšší hodnota jsou uloženy v potomcích kořenového uzlu. V celém stromu má každý uzel vyšší hodnotu než kterýkoli z jeho potomků. „Binární halda minima“ funguje opačně: kořenový uzel ukládá nejnižší hodnotu a každý uzel má nižší hodnotu než jeho potomci.

V informatice se haldy často znázorňují jako jednoduché diagramy. Ve skutečnosti je však ukládání dat do haldy složitější. K vytvoření haldy musí programátoři napsat jednotlivé algoritmy pro vkládání a mazání dat. Hodnoty vložené do haldy se obvykle ukládají do pole, na které může odkazovat program. Protože data v haldě jsou již seřazená, poskytuje halda efektivní způsob vyhledávání konkrétních hodnot.

NOTE: „Halda“ je také programátorský termín, který může označovat dynamicky přidělovanou paměť. K tomuto bloku paměti mohou přistupovat aktivní aplikace. Protože se paměť v haldě přiděluje dynamicky, může se zvětšovat nebo zmenšovat podle toho, kolik paměti se používá.