Strukture podataka i algoritmi: Heap Sort

Strukture podataka i algoritmi

7.2 Heap Sort

Prilikom ranije diskusije o gomilama, primetili smo da one, pored koriscenja kao prioritetni redovi, daju i algoritam za sortiranje:

konstruisi gomilu,
dodaj svaki objekat na nju (cuvajuci svojstvo gomile!),
kad su svi objekti dodati, brisi ih jedan po jedan (cuvajuci svojstvo gomile prilikom brisanja).

I dodavanje i brisanje sa gomile su O(logn) operacije. Potrebno je da izvrsimo n dodavanja i brisanja, sto daje O(nlogn) algoritam. Razmotricemo jos jedan efikasan algoritam za sortiranje, Quick Sort, a zatim cemo ga uporediti sa Heap Sort-om.

Animacija

Sledeca animacija koristi malu modifikaciju prethodnog pristupa za direktno sortiranje pomocu gomile. Primeticete da ona najpre smesta sve objekte u niz, tada uzima objekte sa dna gomile i uspostavlja svojstvo gomile, umesto da odrzava svojstvo gomile prilikom dodavanja svakog objekta, kako gornji algoritam nalaze.

Obratite paznju da animaciju pokazuje podatke

smestene u niz (kao sto i jeste u implementaciji algoritma) i takodje
u obliku stabla - tako da se struktura gomile moze jasno uociti.

Oba predstavljanja su, naravno, ekvivalentna.

Animacija algoritma Heap Sort
Ovu animaciju je napisao Woi Ang.

Posaljite komentare na adresu
morris@ee.uwa.edu.au