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