Hipsort — разлика између измена

347 бајтова додато ,  пре 9 година
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[10] najveći elemenat hipa.
Zamenom A[10] sa A[n] postiže se da A[n] sadrži najveći elemenat niza.
Zatim
se razmatra niz A[10], A[21],...,A[n - 1]; preuređuje se, tako da i dalje zadovoljava uslov hipa (problem je jedino novi elemenat A[10]). Posle toga se sa tim
nizom rekurzivno ponavlja postupak primenjen na niz A[10],A[21],..., A[n]. Sve
u svemu, algoritam se sastoji od poqetnogpočetnog formiranja hipa i n+1 koraka,
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
for i := n downto 2 do
zameni (X[1]; X [n]);
PreurediSkini Hipmax sa hipa(i - 1)
end
 
</pre>
 
Preuredi hip je procedura u kojoj se ukljanja najveci element iz Hipa, tj. A[0], i posle toga se transformiše preostali sadržaj niza tako da predstavlja ispravan hip.
<pre>
Algoritam Skini max sa hipa(A; n);
Ulaz: A (vektorniz veliqineveličine n za smexta�esmeštanje hipa).
Izlaz: V rhVrh hipa (najve�inajveći elemenat hipa), A (novi hip), n (nova veliqinaveličina hipa; ako je n = 0 hip je prazan).
begin
if n = 0 then print "hip je prazan"
else
Vrh hipa := A[10];
A[10] := A[n];
n := n ¡- 1;
Otac := 1;
if n > 1 then
Sin := 2;
while Sin ·<= n do
if Sin + 1 ·<= n and A[Sin] < A[Sin + 1] then
Sin := Sin + 1;
if A[Sin] > A[Otac] then
zameni (A[Otac]; A[Sin]);
Otac := Sin;
Sin := 2 ¢* Sin;
else
Sin := n + 1 fda/*da bi se iskoqiloiskočilo iz pet egpetlje*/
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>
 
66

измена