Hipsort
Hipsort (eng. Heapsort) je algoritam sortiranja koji sortira zadati niz (ili listu). Hipsort je još jedan primer brzog algoritma za sortiranje. U praksi on, za velike n, obično nije tako brz kao sortiranje razdvajanjem, ali nije ni mnogo sporiji. S druge strane, za razliku od sortiranja
razdvajanjem, njegova efikasnost je garantovana. Kao kod sortiranja objedinjavanjem, složenost hipsorta u najgorem slucaju je O(n log n). Za razliku od
sortiranja objedinjavanjem, hipsort je algoritam sortiranja u mestu.

Opis 
Hipsort algoritam može da se podeli u dva dela.
U prvom delu algoritma, formira se hip od zadatih podataka(niza ili liste).
U drugom delu, pravi se sortirani niz od elemenata koji su uklonjeni iz hipa. Kada se svi elementi uklone iz hipa, dobijen je sortiran niz. Rezultujući niz može biti sortiran u opadajućem ili u rastućem poretku, u zavisnosti od toga da li se uklanja maksimalan ili minimalan elemenat iz hipa.

Hipsort je algoritam koji radi u mestu. Niz se može podeliti u dva dela, u sortiran niz i hip.

Formiranje Hip-a 

U vezi sa hipsortom obratićemo posebno pažnju na početni deo algoritma, formiranje hipa. Hip je binarno stablo koje zadovoljava uslov hipa: ključ svakog čvora je
veći ili jednak od ključeva njegovih sinova. Pretpostavlja se
da se hip predstavlja implicitno, njegovi elementi smešteni su u niz A
dužine n, koji stablu odgovara na sledeći način:

 
 koren je smešten u A[1]

 sinovi čvora zapisanog u A[i] smešteni su u A[2i] i A[2i+1]

  Algoritam Upis u hip(A; n; x);
   Ulaz: A (niz veličine n za smeštanje hipa), x (broj).
   Izlaz: A (novi hip), n (nova veličina 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 /*za iskakanje iz petlje*/
   end

Pseudokod 

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[0] najveći elemenat hipa.
Zamenom A[0] sa A[n] postiže se da A[n] sadrži najveći elemenat niza.
Zatim
se razmatra niz A[0], A[1],...,A[n - 1]; preuređuje se, tako da i dalje zadovoljava uslov hipa (problem je jedino novi elemenat A[0]). Posle toga se sa tim
nizom rekurzivno ponavlja postupak primenjen na niz A[0],A[1],..., A[n]. Sve
u svemu, algoritam se sastoji od poč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
hipa. Vremenska složenost algoritma je dakle O(n log n)
(O(log n) po zameni) plus složenost formiranja hipa. Jasno je da je hipsort
sortiranje u mestu.

   Algoritam Hipsort(X; n);
   Ulaz: X (niz od n brojeva).
   Izlaz: X (sortirani niz).
      begin
       Preurediti X tako da bude hip; fvideti nastavak tekstag
       for i := n downto 2 do
       zameni (X[1]; X [n]);
       Skini max sa hipa(i - 1)
      end

   Algoritam Skini max sa hipa(A; n);
   Ulaz: A (niz veličine n za smeštanje hipa).
   Izlaz: Vrh hipa (najveći elemenat hipa), A (novi hip), n (nova veličina hipa; ako je n = 0 hip je prazan).
     begin
      if n = 0 then print "hip je prazan"
      else
          Vrh hipa := A[0];
          A[0] := 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 /*da bi se iskočilo iz petlje*/
     end

Varijacije formiranja hipa 

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.

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 log2(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
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.

Primer 
Neka { 6, 5, 3, 1, 8, 7, 2, 4 } bude niz koji želimo da sortiramo od najmanjeg do najvećeg.

1. Formiranje hipa(odozgo-nadole)

2. Sortiranje.

Literatura 
 
 
 
 
 
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. . Chapters 6 and 7 Respectively: Heapsort and Priority Queues
 -{A PDF of Dijkstra's original paper on Smoothsort}-
 -{Heaps and Heapsort Tutorial by David Carlson, St. Vincent College}-
 -{Heaps of Knowledge}-

Spoljašnje veze 
 -{Courseware on Heapsort from Univ. Oldenburg - With text, animations and interactive exercises}-
 -{NIST's Dictionary of Algorithms and Data Structures: Heapsort}-

Алгоритми сортирања
Hipsort ( eng . Heapsort ) je algoritam sortiranja koji sortira zadati niz ( ili listu ) . Hipsort je još jedan primer brzog algoritma za sortiranje . U praksi on , za velike n , obično nije tako brz kao sortiranje razdvajanjem , ali nije ni mnogo sporiji . S druge strane , za razliku od sortiranja razdvajanjem , njegova efikasnost je garantovana . Kao kod sortiranja objedinjavanjem , složenost hipsorta u najgorem slucaju je O( n log n ) . Za razliku od sortiranja objedinjavanjem , hipsort je algoritam sortiranja u mestu . Opis Hipsort algoritam može da se podeli u dva dela . U prvom delu algoritma , formira se hip od zadatih podataka( niza ili liste ) . U drugom delu , pravi se sortirani niz od elemenata koji su uklonjeni iz hipa . Kada se svi elementi uklone iz hipa , dobijen je sortiran niz . Rezultujući niz može biti sortiran u opadajućem ili u rastućem poretku , u zavisnosti od toga da li se uklanja maksimalan ili minimalan elemenat iz hipa . Hipsort je algoritam koji radi u mestu . Niz se može podeliti u dva dela , u sortiran niz i hip . Formiranje Hip-a U vezi sa hipsortom obratićemo posebno pažnju na početni deo algoritma , formiranje hipa . Hip je binarno stablo koje zadovoljava uslov hipa : ključ svakog čvora je veći ili jednak od ključeva njegovih sinova . Pretpostavlja se da se hip predstavlja implicitno , njegovi elementi smešteni su u niz A dužine n , koji stablu odgovara na sledeći način : koren je smešten u A[ 1 ] sinovi čvora zapisanog u A[ i ] smešteni su u A[ 2i ] i A[ 2i+1 ] Algoritam Upis u hip( A ; n ; x ) ; Ulaz : A ( niz veličine n za smeštanje hipa ) , x ( broj ) . Izlaz : A ( novi hip ) , n ( nova veličina hipa ). begin n \ := n + / *pretpostavka je da novo n nije veće od veličine A * / A[ n ] \ := x ; Sin \ := n ; Otac \ := n div while Otac >=do if A[ Otac ] < A[ Sin ] then zameni ( A[ Otac ] ; A[ Sin ] ) ; Sin \ := Otac ; Otac \ := Otac div else Otac \ := / *za iskakanje iz petlje * / end Pseudokod 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[ 0 ] najveći elemenat hipa . Zamenom A[ 0 ] sa A[ n ] postiže se da A[ n ] sadrži najveći elemenat niza . Zatim se razmatra niz A[ 0 ] , A[ 1 ] , ...,A[ n - ; preuređuje se , tako da i dalje zadovoljava uslov hipa ( problem je jedino novi elemenat A[ 0 ] ) . Posle toga se sa tim nizom rekurzivno ponavlja postupak primenjen na niz A[ 0 ] ,A[ 1 ] , . . . , A[ n ] . Sve u svemu , algoritam se sastoji od poč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 hipa . Vremenska složenost algoritma je dakle O( n log n ) ( O( log n ) po zameni ) plus složenost formiranja hipa . Jasno je da je hipsort sortiranje u mestu . Algoritam Hipsort( X ; n ) ; Ulaz : X ( niz od n brojeva ) . Izlaz : X ( sortirani niz ). begin Preurediti X tako da bude hip ; fvideti nastavak tekstag for i \ := n downtodo zameni ( X[ 1 ] ; X [ n ] ) ; Skini max sa hipa( i - end Algoritam Skini max sa hipa( A ; n ) ; Ulaz : A ( niz veličine n za smeštanje hipa ) . Izlaz : Vrh hipa ( najveći elemenat hipa ) , A ( novi hip ) , n ( nova veličina hipa ; ako je n =hip je prazan ). begin if n =then print " hip je prazan " else Vrh hipa \ := A[ 0 ] ; A[ 0 ] \ := A[ n ] ; n \ := n - Otac \ := if n >then Sin \ := while Sin <= n do if Sin +<= n and A[ Sin ] < A[ Sin + then Sin \ := Sin + if A[ Sin ] > A[ Otac ] then zameni ( A[ Otac ] ; A[ Sin ] ) ; Otac \ := Sin ; Sin \ := * Sin ; else Sin \ := n + / *da bi se iskočilo iz petlje * / end Varijacije formiranja hipa 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 . 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 + u hip A[ 0 ] , A[ 1 ] , . . . , A[ i ] . Element A[ i + 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 log2( i+1 ) . Induktivna hipoteza ( odozdo nagore ) Sva stabla predstavljena nizom A[ i + ; A[ i + , . . . , A[ n ] zadovoljavaju uslov hipa . Indukcija je po i , ali obrnutim redosledom , i = n ; n - . . . , 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 + 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 . Primer Neka { } bude niz koji želimo da sortiramo od najmanjeg do najvećeg. 1. Formiranje hipa( odozgo-nadole ) 2. Sortiranje . Literatura Thomas H . Cormen , Charles E. Leiserson , Ronald L . Rivest , and Clifford Stein . Introduction to Algorithms , Second Edition . MIT Press and McGraw-Hill . \ . ChaptersandRespectively : Heapsort and Priority Queues -{ A PDF of Dijkstra's original paper on Smoothsort }- -{ Heaps and Heapsort Tutorial by David Carlson , St . Vincent College }- -{ Heaps of Knowledge }- Spoljašnje veze -{ Courseware on Heapsort from Univ . Oldenburg - With text , animations and interactive exercises }- -{ NIST's Dictionary of Algorithms and Data Structures : Heapsort }- Алгоритми сортирања