Halda (dátová štruktúra)
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]- d-regulárna halda, najznámejšia binárna
- Binomiálna halda
- Fibonacciho halda
- Leftist halda
|
Tento článok týkajúci sa počítačov je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš. |