Hromada
Obsah
Hromada
Hromada (Halda) je stromová dátová štruktúra, ktorá spĺňa dve podmienky[1]:
- 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
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]
Reprezentácia hromady pomocou jednorozmerného poľa:
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.
Pomocné funkcie pre prácu s hromadou:
- BubbleUp
- Zabezpečí prebublanie ľahkých prvkov smerom hore
- BubbleDown
- Zabezpečí prebublanie ťažkých prvkov smerom dole
Prebublávanie funguje podobne ako pri bublinkovom triedení. Na rozdiel od Bubblesort, prebublávame pozdĺž cesty vedúcej od uzlu v po koreň stromu
Pseudokódy
Poznámka ku pseudokódom: výraz k/2 (n/2) je celočíselné delenie.
1 BubbleUp(k)
2 pokiaľ k>1 a x(k/2)>x(k) rob
3 zamen(k, k/2)
4 k= k/2
5
6 BubbleDown(k)
7 pokiaľ k<=n/2 rob
8 min=2k // inicializacia
9 ak 2k+1 <= n a x(2k)> x(2k+1) tak
10 min=2k+1
11 ak x(min) < x(k) tak
12 zamen(k,min)
13 inak
14 break
15 k=min
16
17 Min
18 return x[1]
19
20 Delete_min
21 x[1]=x[n]
22 n=n-1
23 BubbleDown(n)
24
25 Insert(h)
26 n=n+1
27 x[n]=h
28 BubbleUp(n)
29
30 Delete(k)
31 tmp=x[k]
32 x[k]=x[n]
33 n=n-1
34 ak tmp<=x[k]
35 BubbleDown(k)
36 inak
37 BubbleUp(k)
Vymazanie prvku s minimálnou hodnotou - Delete_min
Vieme, že v hromade je prvok s minimálnou hodnotou vždy na indexe 1. Tento prvok vymažeme a na jeho miesto umiestnime posledný prvok v poli (riadok 21). Tým pádom sa nám zmenší počet prvkov v poli o 1 (riadok 22). Na indexe 1 je prvok z konca poľa. Tento prvok musíme umiestniť na správne miesto pomocou procedúry BubbleDown (riadok 23).
Vloženie nového prvku na hromadu - Insert(n)
Pole zväčšíme o 1 prvok (riadok 26). Do tohoto nového prvku, ktorý je na konci poľa vložíme daný prvok (riadok 27). Tento prvok umiestnime na správen miesto pomocou procedúry BubbleUp (riadok 28)
Vymazanie prvku s na určitim indexe k - Delete
Mažeme prvok na indexe k. Na jeho miesto môžeme umiestniť prvok z konca poľa (riadok 32). Tým sa nám zmenší počet prvkov hromady o 1 (riadok 33). Podľa toho či prvok, ktorý sme vymazali (tmp - riadok 31) bol väčší alebo menší ako poslendý prvok (aktuálne na pozícii k - riadok 34) použijeme procedúru BubbleDown (riadok 35) alebo BubbleUp (riadok 37)
Implementácia v jazyku C
1 #include <iostream.h>
2 #define MAX_HEAP 100
3
4 struct Hromada
5 { int data[ MAX_HEAP];
6 int n;
7 };
8
9 void zamen(Hromada &H,int k, int k2)
10 {
11 int tmp=H.data[k];
12 H.data[k]=H.data[k2];
13 H.data[k2]=tmp;
14 }
15
16 void BubbleUp(Hromada &H, int k)
17 {
18 while(k>1 && H.data[k/2]>H.data[k])
19 {
20 zamen(H,k,k/2);
21 k/=2;
22 }
23 }
24
25 void BubbleDown(Hromada &H, int k)
26 {
27 int min;
28 while(k<= H.n/2) // ak je k potomok lub. uzla
29 {
30 min=2*k; // zitim ktory z dvoch potomkov uzla k je mensi
31 if( (2*k+1)<=H.n && H.data[2*k]>H.data[2*k+1])
32 min=2*k+1;
33 if(H.data[min]<H.data[k]) // prebublavanie dole
34 zamen(H,k,min);
35 else
36 break;
37 k=min;
38 }
39 }
40 void push(Hromada &H, int hodnota)
41 {
42 H.n++;
43 H.data[H.n]=hodnota;
44 BubbleUp(H,H.n);
45 }
46
47 int pop(Hromada &H)
48 {
49 int x=H.data[1];
50 H.data[1]=H.data[H.n];
51 H.n--;
52 BubbleDown(H,1);
53 return x;
54 }
55
56 int Delete(Hromada &H, int k)
57 {
58 int val=H.data[k];
59 H.data[k]=H.data[H.n];
60 H.n--;
61 if( val < H.data[k])
62 BubbleDown(H,k);
63 else
64 BubbleUp(H,k);
65 return val;
66 }
67 void vypis(Hromada H)
68 {
69 for(int i=1;i<=H.n;i++)
70 cout<<H.data[i]<<" ";
71 cout<<endl;
72 }
73 int main()
74 {
75 Hromada heap;
76 heap.n=0;
77 push(heap,10);
78 push(heap,9);
79 push(heap,8);
80 push(heap,7);
81 push(heap,6);
82 push(heap,3);
83
84 vypis(heap);
85
86 int x=pop(heap);
87 cout<<"Vybral som min: "<<x<<endl;
88 vypis(heap);
89
90 cout<<"Mazem prvok s indexom 3: "<<endl;
91 Delete(heap,3);
92 vypis(heap);
93 }
