Halda (dátová štruktúra)

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Halda je stromová datová štruktúra, ktorá spĺňa dve podmienky:

  • Lokálnu podmienku na usporiadanie, ktorá vyžaduje, aby pre každý uzol stromu platilo, že prvok, ktorý reprezentuje, je menší ako prvok reprezentovaný jeho potomkami.
  • Štrukturálnu podmienku na to, ako strom vyzerá - líši sa podľa jednotlivých typov háld.

Lokálna podmienka môže byť položená aj opačne: predok môže reprezentovať prvky väčšie ako potomkovia.

Využitie[upraviť | upraviť zdroj]

  • triedenie (Heapsort)
  • implementácia Dijkstrovho algoritmu
  • všetky iné aplikácie, kde je často potrebné hľadať minimálny/maximálny prvok z množiny prvkov

Varianty[upraviť | upraviť zdroj]