Hipsort — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
|||
Ред 42:
<br/>
== Varijacije ==
[[Датотека:Formiranje hipa|мини|десно|Formiranje hipa odozgo-nadole i odozgo nadole.]]
Postoje dva prirodna pristupa formiranju hipa: odozgo-nadole i odozdo-nagore. Oni odgovaraju prolasku kroz niz A udesno, odnosno zdesna ulevo. Oni će biti predstavljeni primenom matematičke indukcije.
<br />
'''Induktivna hipoteza (odozgo nadole).'''<br />
Niz A[0], A[1],..., A[i] predstavlja hip.
Bazni slučaj je trivijalan, jer A[0] jeste hip. Osnovni deo algoritma je
ugradnja elementa A[i + 1] u hip A[0], A[1],..., A[i]. Element A[i + 1] upoređuje se sa svojim ocem, i zamenjuje se sa njim ako je veći od
njega. Novi element se premešta naviše, sve dok ne postane manji ili jednak
od oca, ili dok ne dospe u koren hipa. Broj upoređivanja je u najgorem slučaju
log<sub>2</sub>(i+1).
<br />
'''Induktivna hipoteza (odozdo nagore).''' <br />
Sva stabla predstavljena nizom
A[i + 1]; A[i + 2],..., A[n] zadovoljavaju uslov hipa.
Indukcija je po i, ali obrnutim redosledom, i = n; n ¡ 1,..., 1. Element
A[n] očigledno predstavlja hip, što predstavlja bazu indukcije. Može se zaključiti i nešto više. Elementi vektora A sa indeksima od n/2+1 do n
su listovi stabla. Zbog toga se stabla koja odgovaraju tom nizu sastoje samo
od korena, pa trivijalno zadovoljavaju uslov hipa. Dovoljno je dakle da sa
indukcijom krenemo od i = n/2. To već ukazuje da bi pristup odozdo nagore
mogao biti efikasniji, polovina posla je trivijalna, ovo je još jedan primer
važnosti pažljivog izbora baze indukcije.
Razmotrimo sada elemenat A[i]. On ima najviše dva sina A[2i + 1] i A[2i],
koji su, prema induktivnoj hipotezi, koreni ispravnih hipova. Zbog toga je
jasan način uključivanja A[i] u hip: A[i] se upoređuje sa većim od sinova, i
zamenjuje se sa njim ako je potrebno. Sa zamenama se nastavlja naniže niz stablo, dok prethodna vrednost elementa A[i] ne dođe do mesta na kome je veća od oba sina.
== Pseudokod ==
[[Датотека:Sorting_heapsort_anim.gif|оквир|десно|Primer rada hipsort algoritma.<br />
| |||