Heap

[Jakub Slajs]

> Mohl by mi nekdo osvezit pamet? Potrebuji naprogramovat heap-sort.

Proc proboha potrebujete zrovna heap-sort? Mozna to neni Vas pripad
ale spousta lidi napriklad nevi ze v C-cku je standardni knihovni
funkce qsort (tedy quick sort - stejne jako heap sort je nestabilni
tj. nelze radit podle vice klicu)

> pamatuju z prednasek, ze nad heapem jsou definovany operace Insert a
> ExtractMinimum...  jak je heap organizovany...

Neni treba nic kreslit - je to obycejny binarni strom ktery ma minimum
vzdy na vrcholu a kazdy uzel ma hodnotu mensi nebo rovnu nez jeho
nasledovnici. Novy uzel se vklada na konec (nejhlubsi a nejpravejsi).
Pokud ma hodnotu mensi nez jeho rodic tak se s nim prohodi a to se
opakuje
dokud rodic nema mensi (nebo rovnou) hodnotu.

Minimalni prvek je vzdy vrchol a po jeho vyjmuti se nahradi poslednim
uzlem.
Ten se naopak zamenuje s nasledovnikem ktery mam mensi hodnotu.

S pozdravem,

Jakub Slajs

_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com