66
измена
нема резимеа измене
Нема описа измене |
|||
|
</pre>
<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 ==
end
</pre>
▲== 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.
== Reference ==
| |||