Hromada - História úprav

Juraj na 20:10, 16. august 2010

2010-08-16T20:10:49Z

Juraj: /* Pseudokódy */

2010-03-15T20:12:04Z

Pseudokódy

Juraj na 21:57, 14. marec 2010

2010-03-14T21:57:45Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} ==Hromada== Hromada (Halda) je stromová d…“

2010-03-14T21:13:17Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} ==Hromada== Hromada (Halda) je stromová d…“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
{{Draft}}
{{Skripta programovanie}}

==Hromada==
Hromada (Halda) je stromová dátová štruktúra, ktorá spĺňa dve podmienky<ref>Wiki - halda http://sk.wikipedia.org/wiki/Halda_%28d%C3%A1tov%C3%A1_%C5%A1trukt%C3%BAra%29</ref>:
* 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'''

[[Triedenie výberom|'''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!!!

<source lang="c">
#define MAX_HEAP 100

struct Hromada{
int data[MAX_HEAP];
int n;
};
</source>

Opis štruktúry Hromada
* ''data'' - jednorozmerné pole prvkov hromady (v našom prípade celých čísel)
* ''n'' - aktuálna veľkosť hromady.

==Zdroje==
<references/>

@@ Riadok 67: / Riadok 67: @@
 ====Pseudokódy====
 Poznámka ku pseudokódom: výraz k/2 (n/2) je celočíselné delenie.
 <source lang="pascal" line>
 BubbleUp(k)
@@ Riadok 75: / Riadok 82: @@
 BubbleDown(k)
     pokiaľ k<=n/2 rob
-       min=2k // inicializacia
+       min=2k
        ak 2k+1 <= n a x(2k)> x(2k+1) tak
           min=2k+1
@@ Riadok 83: / Riadok 90: @@
           break
        k=min
 Min
     return x[1]
@@ Riadok 91: / Riadok 102: @@
     n=n-1
     BubbleDown(n)
 Insert(h)
     n=n+1
     x[n]=h
     BubbleUp(n)
 Delete(k)
     tmp=x[k]
@@ Riadok 105: / Riadok 124: @@
     inak
        BubbleUp(k)
 </source>
 ====Implementácia v jazyku C====

@@ Riadok 1: / Riadok 1: @@
 [[Kategória:Študijné materiály]]
-[[Kategória:Programovanie]]
+[[Kategória:Algoritmy a programovanie]]
 [[Kategória:Informatika]]
 {{Draft}}

@@ Riadok 38: / Riadok 38: @@
 *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!!!
@@ Riadok 54: / Riadok 58: @@
 * ''n'' - aktuálna veľkosť hromady.
 ==Zdroje==
 <references/>