Obsah:
Definice - Co znamená Heap?
Halda v kontextu datové struktury je stromová datová struktura, která splňuje vlastnost haldy, kde je každému prvku přiřazena klíčová hodnota nebo váha. Klíč s nižší hodnotou má vždy nadřazený uzel s klíčem s vyšší hodnotou. Tomu se říká struktura maximální haldy a mezi všemi uzly má kořenový uzel nejvyšší klíč.
Struktura založená na stromech má někdy pravidlo obrácené struktury, kde prvek s klíčem s vyšší hodnotou má vždy jako klíčový uzel klíč s nižší hodnotou. Tomu se říká struktura min. Haldy a mezi všemi uzly má kořenový uzel nejnižší klíč.
Techopedia vysvětluje Heap
Neexistují žádná praktická omezení, pokud jde o počet dětí, které může mít každý uzel v haldě, i když každý uzel má obvykle maximálně dva. Halda je považována za nejúčinnější implementaci abstraktního datového typu, známého jako fronta priorit. Implementace haldy je nezbytná v různých grafových algoritmech (včetně Dijkstraho algoritmu) a také v algoritmu třídění haldy.
Hromady mají několik variací, které fungují jako implementace prioritní fronty datového typu s vysokou účinností. Mnoho aplikací, například grafové algoritmy, vyžaduje implementaci prioritních front.
Pole je nejběžnější implementační formou haldy, kde není potřeba žádná ukazatele pro propojení mezi jejími prvky.
Hromady provádějí více operací, včetně:
- Find-max: Vyhledá nejvyšší klíčový uzel ve skupině uzlů
- Find-min: Vyhledá nejnižší klíčový uzel ve skupině uzlů
- Delete-max: Odstraní nejvyšší klíčový uzel ze skupiny uzlů
- Delete-min: Vymaže nejnižší klíčový uzel ze skupiny uzlů
Hromady také obsahují funkce, které provádějí slučování, vkládání a změny klíčů.
Tato definice byla napsána v souvislosti se strukturou dat