Hipsort — разлика између измена
Садржај обрисан Садржај додат
Ред 32:
Algoritam hipsort izvršava se na isti način kao i sortiranje izborom,
razlika je u upotrebljenoj strukturi podataka za smeštanje niza. Ovde ćemo implementirati metodu koja uklanja maksimum iz hipa. Najpre se
elementi niza preuređuju tako da čine hip, Ako je hip u nizu A, onda je A[
Zamenom A[
Zatim
se razmatra niz A[
nizom rekurzivno ponavlja postupak primenjen na niz A[
u svemu, algoritam se sastoji od
u kojima se vrši po jedna zamena i preuređivanje hipa. Preuređivanje hipa
je u osnovi isti postupak kao algoritam za uklanjanje najvećeg elementa iz
Ред 51:
for i := n downto 2 do
zameni (X[1]; X [n]);
end
Algoritam Skini max sa hipa(A; n);
Ulaz: A (
Izlaz:
begin
if n = 0 then print "hip je prazan"
else
Vrh hipa := A[
A[
n := n
Otac := 1;
if n > 1 then
Sin := 2;
while Sin
if Sin + 1
Sin := Sin + 1;
if A[Sin] > A[Otac] then
zameni (A[Otac]; A[Sin]);
Otac := Sin;
Sin := 2
else
Sin := n + 1
end
Algoritam Upis u hip(A; n; x);
Ulaz: A (vektor veliqine n za smexta�e hipa), x (broj).
Izlaz: A (novi hip), n (nova veliqina hipa).
begin
n := n + 1; /*pretpostavka je da novo n nije ve�će od veličine A*/
A[n] := x;
Sin := n;
Otac := n div 2;
while Otac >= 1 do
if A[Otac] < A[Sin] then
zameni (A[Otac]; A[Sin]);
Sin := Otac;
Otac := Otac div 2;
else
Otac := 0 fza iskaka�e iz pet eg
end
</pre>
|