Hromada

Algoritmy a programovanie

---

Dátový typ

>Zásobník
>Zoznam
>Fronta
>Množina
>Strom
>Hromada

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia

Lineárny zoznam

Binárny strom

Numerické algoritmy

Grafové algoritmy

Hromada

Hromada (Halda) je stromová dátová š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.

Problém pri reprezentácii haldy polom nastane vtedy, keď budeme chcieť z tohto pola mazať prvky, čo trvá príliš dlhý čas, teda je to neefektívne. Pre efektívnejšiu implementáciu bola vymyslená binárna halda. Príklad binárnej haldy:

Binárna hromada

Je to úplný binárny strom v ktorom priorita všetkých vrcholov je väčšia ako jeho potomkov. Úplný binárny strom znamená, že dĺžka cesty od koreňa do každého listu je rozdielna maximálne o 1. Preto v tomto type dátovej štruktúry trvá každá cesta najviac O(log n), kde n je počet prvkov. Jednoduché operácie na binárnej halde trvajú log n. Najčastejšie operácie na halde sú:

• DELETE-MAX - MAX vymaže prvok s najväčšou prioritou
• INCREASE-KEY - zvýši prioritu prvku buď o 1, alebo o určitú hodnotu, podľa toho, ako je to implementované.
• INSERT - vloží prvok do binárnej haldy
• MERGE - spojí dve haldy do jednej novej správne usporiadanej haldy obsahujúca všetky prvky oboch spájaných háld.

Využitie hromady

Prioritná fronta, inak povedané prioritný rad. Je to také usporiadanie prvkov či operácií, že prvky majú ohodnotenie svojej priority, najčastejšie číslom. Podstatné je, aby sme mali v tejto fronte najväčší prvok na začiatku fronty a usporiadanie ostatných prvkov nás ani tak veľmi nezaujíma. To je aj hlavný rozdiel prioritného radu od obyčajného radu. Z toho plynú najčastejšie operácie: pridanie nového prvku, odstránenie najväčšieho.

Dijkstrov algoritmus

Heap sort

Implementácia hromady v jazyku C

Návrh vhodnej dátovej štruktúry

Pre jednoduchosť budeme vytvárať hromadu z celých čísel (v praxi to budú štruktúry). Binárnu hromadu môžeme jednoducho reprezentovať v jednorozmernom poli celých čísel int x[].

Pre hromadu platí:

• Vrchol hromady – index 1
• Ľubovoľný uzol hromady – x[i]
• Ľavý potomok uzla – x[i*2]
• Pravý potomok uzla – x[i*2+1]
• Index otca vrholu i - [math] \left \lfloor i/2 \right \rfloor[/math]

Pri implementácie hromady pomocou jednorozmerného poľa pracujeme od indexu 1!!!

#define MAX_HEAP 100

struct Hromada{
	int data[MAX_HEAP];
	int n; 
};

Opis štruktúry Hromada

• data - jednorozmerné pole prvkov hromady (v našom prípade celých čísel)
• n - aktuálna veľkosť hromady.