Halda (datová struktura)
Z Wikipedie, otevřené encyklopedie
Halda je stromová datová struktura, jež splňuje dvě podmínky:
- Lokální podmínku na uspořádání, která vyžaduje, aby pro každý uzel stromu platilo, že prvek, který reprezentuje, je menší než prvek reprezentovaný jeho potomky.
- Strukturální podmínku na to, jak strom vypadá - liší se podle jednotlivých typů hald.
Lokální podmínka může být položena i opačně: předek může reprezentovat prvky větší než potomci.
[editovat] Využití
- třídění (Heapsort)
- implementace Dijkstrova algoritmu
- všechny jiné aplikace, kde je často potřeba hledat minimální/maximální prvek z množiny prvků
[editovat] Varianty
- d-regulární halda, nejznámější binární
- Binomiální halda
- Fibonacciho halda
- Leftist halda

