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.
Procedúry prebublávania:
BubbleUp - parametrom procedúry je je index prvku, pre ktorý treba nájsť správne miesto. V cykle (pokiaľ) podmienka k>1 znamená - pokiaľ nie je prvok s indexom k vrcholom hromady. Výraz x(k/2)>x(k) zmamená : pokiaľ má rodič prvku s indexom k väčšiu hodnotu ako prvok k - toto usporiadanie nie je v súlade s definíciou hromady a prvky treba zameniť (riadok 3).
BubbleDown - parametrom procedúry je je index prvku, pre ktorý treba nájsť správne miesto. Podmienka cyklu (pokiaľ) k<=n/2 má význam: pokiaľ má prvok s indexom k potomka. Podľa definície hromady má prvok s indexom k potomkov na indexoch 2k a 2k+1. Vieme, že hromada má n prvkov. Ak potrebujeme zistiť, či má ľub. uzol k potomka, zistíme, či existuje prvok 2k, resp, či je 2k<n. Ak podmienka platí, tak prvok s indexom k má potomkov. Pri rozhodovaní na ktorú stranu posunieme prvok na indexe k, treba zisiť, ktorý z jeho dvoch potomkov má menšiu hodnotu. Predpokladáme je menší prvok je na indexe 2k (riadok 8). Na riadku 9 sa zistiť, či nie je minimum na indexe 2k+1 (x(2k)> x(2k+1)). Index minima máme uložený v premennej min. Ak platí (riadok 11) že prvok ktorý umiestňujeme (na indexe k) má väčšiu hodnotu ako jeho potomok (na indexe min) tak tieto 2 prvky vzájomne zameníme. Ak nájdeme také miesto, kde pre prvok s indexom k platí pravidlo usporiadania hromady (rodič má menšiu hodnotu ako jeho potomkovia), tak ďalej už neprebublávame (riadok 14).
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
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
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 5). Tým pádom sa nám zmenší počet prvkov v poli o 1 (riadok 6). Na indexe 1 je prvok z konca poľa. Tento prvok musíme umiestniť na správne miesto pomocou procedúry BubbleDown (riadok 7).
1 Min
2 return x[1]
3
4 Delete_min
5 x[1]=x[n]
6 n=n-1
7 BubbleDown(n)
Vloženie nového prvku na hromadu - Insert(n)
Pole zväčšíme o 1 prvok (riadok 2). Do tohoto nového prvku, ktorý je na konci poľa vložíme daný prvok (riadok 3). Tento prvok umiestnime na správne miesto pomocou procedúry BubbleUp (riadok 4)
1 Insert(h)
2 n=n+1
3 x[n]=h
4 BubbleUp(n)
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 4). 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 6) alebo BubbleUp (riadok 8)
1 Delete(k)
2 tmp=x[k]
3 x[k]=x[n]
4 n=n-1
5 ak tmp<=x[k]
6 BubbleDown(k)
7 inak
8 BubbleUp(k)
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 }
