Hipsort — разлика између измена
Садржај обрисан Садржај додат
Ред 102:
<br />
'''Induktivna hipoteza (odozgo nadole)
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).
'''Induktivna hipoteza (odozdo nagore)
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
| |||