Heapsort vremenska složenost

Hrpa se naziva 'djelomično uređena', a ne 'djelomično sortirana'. Riječ 'sort' znači potpuno sređivanje (potpuno sortiranje). Hrpa nije djelomično uređena proizvoljno. Hrpa je djelomično uređena prema kriteriju (uzorku), kao što je prikazano u nastavku.

Dakle, heapsort se sastoji od dvije faze: izgradnje hrpe i izdvajanja uređenog elementa s vrha hrpe. U drugoj fazi, nakon svakog vađenja, gomila se ponovno gradi. Svaka ponovna izgradnja je brža od izvornog procesa izgradnje budući da se ponovna izgradnja vrši iz prethodne izgradnje, gdje je jedan element uklonjen. Uz to, heapsort razvrstava potpuno nesvrstan popis.

Cilj ovog članka je ukratko objasniti heapsort, a zatim prikazati njegovu vremensku složenost (pogledajte značenje vremenske složenosti u nastavku). Pred kraj, kodiranje se radi u C++.

Minimalna gomila

Hrpa može biti minimalna ili maksimalna hrpa. Max-heap je onaj gdje je prvi element najviši element, a cijelo stablo ili odgovarajući popis je djelomično poredan silaznim redoslijedom. Min-heap je onaj gdje je prvi element najmanji element, a cijeli popis je djelomično poredan uzlaznim redoslijedom. U ovom članku razmatra se samo minimalna hrpa. Napomena: u temi gomile, element se također naziva čvor.

Hrpa je potpuno binarno stablo. Binarno stablo se može izraziti kao polje (lista); čitajte od vrha prema dolje i slijeva na desno. Svojstvo hrpe za min-heap je da je nadređeni čvor manji ili jednak svakom od svoja dva djeteta. Primjer neuređenog popisa je:

Prvi red ove tablice su elementi niza. U drugom redu su indeksi temeljeni na nuli. Ovaj popis elemenata može se izraziti kao stablo. Dodani su nulti elementi kako bi se napravilo potpuno binarno stablo. Strogo govoreći, nulti elementi nisu dio liste (stabla). Ovaj popis nema redoslijed, tako da još nije hrpa. Postat će hrpa kada ima djelomično sređivanje, prema svojstvu hrpe.

Odnos između čvorova i indeksa

Upamtite, hrpa je potpuno binarno stablo prije konfiguracije hrpe (svojstvo hrpe). Prethodna lista još nije hrpa, jer elementi ne poštuju svojstvo hrpe. Postaje gomila nakon preuređivanja elemenata u djelomični redoslijed prema svojstvu min-hop. Djelomični poredak može se promatrati kao djelomično sortiranje (iako riječ 'sortiranje' znači potpuno poredak).

Bilo da je binarno stablo gomila ili ne, svaki roditelj ima dvoje djece, osim listova (zadnjih) čvorova. Postoji matematički odnos među indeksima između svakog roditelja i njegove djece. To je kako slijedi: Ako je roditelj na indeksu i, onda je lijevi dijete na indeksu:

a desno dijete je na indeksu:

Ovo je za indeksiranje temeljeno na nuli. I tako, roditelj na indeksu 0 ima lijevo dijete na indeksu 2×0+1=1 i desno dijete na 2×0+2=2. Roditelj na indeksu 1 ima lijevo dijete na indeksu 2×1+1=3 i desno dijete na indeksu 2×1+2=4; i tako dalje.

Po svojstvu min-heap, roditelj na i manji je ili jednak lijevom djetetu na 2i+1 i manji ili jednak desnom djetetu na 2i+2.

Hrpa

Nagomilavanje znači stvaranje gomile. To znači preurediti elemente popisa (ili odgovarajućeg stabla) tako da zadovolje svojstvo gomile. Na kraju procesa gomilanja, lista ili stablo je hrpa.

Ako se prethodni nesortirani popis gomila, postat će:

Napomena: na popisu je 12 elemenata, a ne 15. U drugom redu su indeksi. U procesu izgradnje gomile, elemente je trebalo provjeriti, a neke zamijeniti.

Primijetite da je najmanji i prvi element 3. Ostali elementi slijede na uzlazni ali valovit način. Ako su lijevi i desni potomci na pozicijama 2i+1 i 2i+2 svaki veći ili jednaki roditelju na i, tada je ovo min-hrpa. Ovo nije potpuno sređivanje ili sortiranje. Ovo je djelomično sređivanje, prema svojstvu gomile. Odavde počinje sljedeća faza za heap sortiranje.

Heapify Time Complexity

Vremenska složenost je relativno vrijeme izvođenja nekog koda. Može se promatrati kao broj glavnih operacija koje taj kod treba izvršiti. Postoje različiti algoritmi za izgradnju hrpe. Najučinkovitiji i najbrži kontinuirano dijele popis na dva, provjeravajući elemente od dna, a zatim radeći neke izmjene elemenata. Neka je N broj praktičnih elemenata u listi. S ovim algoritmom, maksimalni broj glavnih operacija (zamjena) je N. Vremenska složenost za gomilanje je prethodno dana kao:

Gdje je n N i najveći mogući broj glavnih operacija. Ova notacija se naziva Big-O notacija. Počinje s O velikim slovima, nakon čega slijede zagrade. Unutar zagrada nalazi se izraz za najveći mogući broj operacija.

Upamtite: zbrajanje može postati množenje ako se ista stvar koja se dodaje stalno ponavlja.

Heapsort ilustracija

Prethodni nesortirani popis koristit će se za ilustraciju heapsort-a. Dati popis je:

Min-heap proizveden iz liste je:

Prva faza heapsort-a je stvaranje hrpe koja je proizvedena. Ovo je djelomično uređen popis. To nije sortirani (potpuno sortirani) popis.

Druga faza sastoji se od uklanjanja najmanjeg elementa, koji je prvi element, iz gomile, ponovnog gomilanja preostale hrpe i uklanjanja najmanje elemenata u rezultatima. Najmanji element uvijek je prvi element u ponovno gomilanoj hrpi. Elementi se ne uklanjaju i ne bacaju. Mogu se poslati u drugi niz redoslijedom kojim su uklonjeni.

Na kraju, novi niz bi imao sve elemente poredane (u potpunosti), uzlaznim redoslijedom; a ne više samo djelomično naručeno.

U drugoj fazi, prva stvar koju treba učiniti je ukloniti 3 i smjestiti ga u novi niz. Rezultati su:

i

Preostali elementi moraju se gomilati prije izdvajanja prvog elementa. Gomila preostalih elemenata može postati:

Izdvajanje 5 i dodavanje novom popisu (nizu) daje rezultate:

i

Nagomilavanje preostalog skupa dalo bi:

Izdvajanje 6 i dodavanje novom popisu (nizu) daje rezultate:

i

Nagomilavanje preostalog skupa dalo bi:

Izdvajanje 7 i njegovo dodavanje na novi popis daje rezultate:

i

Nagomilavanje preostalog skupa daje:

Izdvajanje 9 i dodavanje na novi popis daje rezultate:

i

Nagomilavanje preostalog skupa daje:

Izdvajanje 11 i njegovo dodavanje na novi popis daje rezultate:

i

Nagomilavanje preostalog skupa dalo bi:

Izdvajanje 14 i njegovo dodavanje na novi popis daje rezultate:

i

Nagomilavanje preostalog skupa dalo bi:

Izdvajanje 15 i njegovo dodavanje na novi popis daje rezultate:

i

Nagomilavanje preostalog skupa dalo bi:

Izdvajanje 17 i njegovo dodavanje na novi popis daje rezultate:

i

Nagomilavanje preostalog skupa dalo bi:

Izdvajanje 19 i njegovo dodavanje na novi popis daje rezultate:

i

Nagomilavanje preostalog skupa daje:

Izdvajanje 22 i njegovo dodavanje na novi popis daje rezultate:

i

Nagomilavanje preostalog skupa daje:

Izdvajanje 24 i njegovo dodavanje na novi popis daje rezultate:

i

Niz hrpe je sada prazan. Svi elementi koje je imao na početku sada su u novom nizu (listi) i sortirani.

Heapsort algoritam

Iako je čitatelj možda pročitao u udžbenicima da se heapsort sastoji od dva stupnja, heapsort se još uvijek može vidjeti kao da se sastoji od jednog stupnja, koji se iterativno smanjuje iz zadanog niza. Uz to, algoritam za sortiranje heapsortom je sljedeći:

• Povećajte nerazvrstani popis.
• Izdvojite prvi element hrpe i stavite ga kao prvi element nove liste.
• Povećajte preostali popis.
• Izdvojite prvi element nove gomile i stavite ga kao sljedeći element nove liste.
• Ponavljajte prethodne korake redom dok se popis hrpe ne isprazni. Na kraju se novi popis sređuje.

Heapsort Time Complexity Proper

Jednostupanjski pristup koristi se za određivanje vremenske složenosti heapsort-a. Pretpostavimo da postoji 8 nesortiranih elemenata koje treba sortirati.

Maksimalni mogući broj operacija je:

Prosjek ovih brojeva operacija je:

Primijetite da se zadnje četiri hrpe u prethodnoj ilustraciji nisu promijenile kada je prvi element uklonjen. Neke od prethodnih gomila nisu se također promijenile kada je prvi element uklonjen. Time je bolji prosječni broj glavnih operacija (zamjena) 3 a ne 4,5. Dakle, bolji ukupni prosječni broj glavnih operacija je:

jer log _dva 8 = 3.

Općenito, prosječna složenost slučaja za heapsort je:

Gdje točka znači množenje, a n je N, ukupan broj elemenata na popisu (bilo koji popis).

Imajte na umu da je operacija izdvajanja prvog elementa zanemarena. Na temu Vremenska složenost, operacije koje traju relativno kratko vrijeme se zanemaruju.

Kodiranje u C++

U biblioteci algoritama C++ postoji funkcija make_heap(). Sintaksa je:

Uzima iterator koji pokazuje na prvi element vektora kao prvi argument, a zatim iterator koji pokazuje neposredno iza kraja vektora kao posljednji argument. Za prethodni nesortirani popis, sintaksa bi se koristila kako slijedi kako bi se dobila minimalna gomila:

Ovaj kod mijenja vektorski sadržaj u konfiguraciju minimalne gomile. U sljedećim C++ vektorima, dva će se vektora koristiti umjesto dva niza.

Za kopiranje i vraćanje prvog elementa vektora upotrijebite vektorsku sintaksu:

Da biste uklonili prvi element vektora i bacili ga, koristite sintaksu vektora:

Da biste dodali element iza vektora (sljedeći element), koristite vektorsku sintaksu:

Početak programa je:

Uključene su algoritam i vektorske biblioteke. Sljedeća u programu je funkcija heapsort(), koja je:

To je rekurzivna funkcija. Koristi funkciju make_heap() biblioteke C++ algoritama. Drugi segment koda u definiciji funkcije izdvaja prvi element iz starog vektora nakon izgradnje gomile i dodaje kao sljedeći element za novi vektor. Imajte na umu da su u definiciji funkcije vektorski parametri reference, dok se funkcija poziva s identifikatorima (imenima).

Prikladna C++ glavna funkcija za ovo je:

Izlaz je:

sortiran (potpuno).

Zaključak

U članku se detaljno raspravlja o prirodi i funkciji Heap Sort-a, poznatog kao Heapsort, kao algoritma za sortiranje. Heapify Time Complexity, Heapsort ilustracija i Heapsort kao algoritam obrađeni su i potkrijepljeni primjerima. Prosječna vremenska složenost za dobro napisan heapsort program je O(nlog(n))