Heapsort tidskompleksitet

Heap Sort, skrevet som Heapsort, er en slags sorteringsalgoritme. Den tar en liste som delvis er bestilt og produserer en sortert liste fra den. Sortering kan være stigende eller synke. I denne artikkelen stiger sorteringen. Merk at Heapsort ikke sorterer en ufullstendig usortert liste. Det sorterer en delvis bestilt (sortert) liste. Den delvis bestilte listen er en haug. I denne artikkelen er haugen som vurderes minimum (stigende) haugen.

En haug blir referert til som "delvis ordnet" og ikke "delvis sortert". Ordet "sortering" betyr fullstendig bestilling (fullstendig sortering). En haug bestilles ikke delvis vilkårlig. En haug er delvis bestilt etter et kriterium (mønster), som vist nedenfor.

Så heapsort består av to stadier: å bygge haugen og trekke ut det bestilte elementet fra toppen av haugen. I den andre trinnen, etter hver ekstraksjon, gjenoppbygges haugen. Hver ombygging er raskere enn den opprinnelige byggeprosessen siden ombyggingen gjøres fra en tidligere bygning, der ett element er fjernet. Og med det sorterer Heapsort en helt usortert liste.

Målet med denne artikkelen er å kort forklare Heapsort og deretter produsere sin tidskompleksitet (se betydningen av tidskompleksitet nedenfor). Mot slutten gjøres koding i C++.

Minimum haug

En haug kan være en minimum haug eller en maksimal haug. En max-heap er et der det første elementet er det høyeste elementet, og hele treet eller tilsvarende liste er delvis bestilt i synkende rekkefølge. En min-heap er en der det første elementet er det minste elementet, og hele listen er delvis bestilt i stigende rekkefølge. I denne artikkelen er det bare minimumshaugen. Merk: I emnet for haugen kalles et element også en node.

En haug er et komplett binært tre. Det binære treet kan uttrykkes som en matrise (liste); Les fra topp til bunn og venstre til høyre. Heapegenskapen for en min-heap er at en foreldrode er mindre enn eller lik hvert av de to barna. Et eksempel på en uordnet liste er:

9	19	24	5	3	11	14	22	7	6	17	15	null	null	null
0	1	2	3	4	5	6	7	8	9	10	11	12	1. 3	14

Den første raden i denne tabellen er elementene i matrisen. I den andre raden er de nullbaserte indeksene. Denne listen over elementer kan uttrykkes som et tre. Nullelementene er lagt til for å lage et fullt binært tre. Strengt tatt er ikke nullelementene en del av listen (treet). Denne listen har ingen ordre, så den er ikke en haug ennå. Det vil bli en haug når den har hatt delvis bestilling, ifølge Heap -eiendommen.

Forholdet mellom noder og indekser

Husk at en haug er et komplett binært tre før du har Heap -konfigurasjonen (Heap -eiendom). Den forrige listen er ikke en haug ennå, fordi elementene ikke overholder Heap -eiendommen. Det blir en haug etter å omorganisere elementer i delvis rekkefølge i henhold til min-heap-eiendommen. Delvis ordre kan sees på som delvis sortering (selv om ordet "sortering" betyr fullstendig bestilling).

Enten et binært tre er en haug eller ikke, hver av foreldrene har to barn, bortsett fra bladet (sist) noder. Det er et matematisk forhold mellom indeksene mellom hver av foreldrene og dets barn. Det er som følger: Hvis forelderen er på indeks I, så er det venstre barnet på indeks:

2*i + 1

Og det rette barnet er på indeks:

2*i + 2

Dette er for nullbasert indeksering. Og så har en forelder på indeks 0 sitt venstre barn på indeks 2 × 0+1 = 1 og dets høyre barn på 2 × 0+2 = 2. En forelder på indeks 1 har sitt venstre barn på indeks 2 × 1+1 = 3 og høyre barn ved indeks 2 × 1+2 = 4; og så videre.

Ved min-heap-eiendommen er en forelder på I mindre enn eller lik det venstre barnet på 2i+1 og mindre enn eller lik det høyre barnet på 2i+2.

Haug

Hauger betyr å bygge en haug. Det betyr å omorganisere elementene i en liste (eller tilsvarende tre) slik at de tilfredsstiller Heap -eiendommen. På slutten av dynselingsprosessen er listen eller treet en haug.

Hvis den forrige usorterte listen er dynget, vil den bli:

3	5	11	7	6	15	14	22	9	19	17	24	null	null	null
0	1	2	3	4	5	6	7	8	9	10	11	12	1. 3	14

Merk: Det er 12 elementer og ikke 15 på listen. I den andre raden er indeksene. I bygningsprosessen måtte elementene kontrolleres, og noen byttet ut.

Legg merke til at det minste og første elementet er 3. Resten av elementene følger på en stigende, men bølgende måte. Hvis venstre og høyre barn på stillinger 2i+1 og 2i+2 er hver større enn eller lik foreldrene på I, er dette en min-heap. Dette er ikke full bestilling eller sortering. Dette er delvis bestilling, ifølge Heap -eiendommen. Det er herfra neste trinn for haug -sort starter.

Heapify tidskompleksitet

Tidskompleksitet er den relative kjøretiden for en viss kode. Det kan sees på som antall hovedoperasjoner for den koden som skal fullføres. Det er forskjellige algoritmer for haugbygging. Den mest effektive og raskeste deler kontinuerlig listen med to, sjekker elementene fra bunnen, og deretter gjør noen bytte av elementer. La n være antall praktiske elementer på listen. Med denne algoritmen er maksimalt antall hovedoperasjoner (bytte) n. Tidskompleksiteten for å ha blitt gitt tidligere som:

På)

Hvor n er n og er maksimalt mulig antall hovedoperasjoner. Denne notasjonen kalles Big-O-notasjonen. Det begynner med O i store bokstaver, etterfulgt av parenteser. Inne i parentesene er uttrykket for mulig høyeste antall operasjoner.

Husk: Tillegg kan bli multiplikasjon hvis det samme blir lagt til, fortsetter å gjenta.

Heapsort -illustrasjon

Den forrige usorterte listen vil bli brukt til å illustrere Heapsort. Den gitte listen er:

9 19 24 5 3 11 14 22 7 6 17 15

Min-heap produsert fra listen er:

3 5 11 7 6 15 14 22 9 19 17 24

Den første fasen i Heapsort er å produsere haugen som er produsert. Dette er en delvis bestilt liste. Det er ikke en sortert (helt sortert) liste.

Det andre trinnet består av å fjerne det minste elementet, som er det første elementet, fra haugen, re-heapifying den gjenværende haugen og fjerne minstelementene i resultatene. Det minste elementet er alltid det første elementet i den re-heapifyied haugen. Elementene blir ikke fjernet og kastet. De kan sendes til en annen rekke i den rekkefølgen de fjernes.

Til slutt ville den nye matrisen ha alle elementene sortert (helt), i stigende rekkefølge; og ikke lenger bare delvis bestilt.

I andre trinn er det første å gjøre å fjerne 3 og plassere den i den nye matrisen. Resultatene er:

3

og

5 11 7 6 15 14 22 9 19 17 24

De resterende elementene må høstes før det første elementet blir trukket ut. Mynten til de gjenværende elementene kan bli:

5 6 7 9 15 14 22 11 19 17 24

Å trekke ut 5 og legge til den nye listen (Array) gir resultatene:

3 5

og

6 7 9 15 14 22 11 19 17 24

Å ha det gjenværende settet vil gi:

6 7 9 15 14 22 11 19 17 24

Å trekke ut 6 og legge til den nye listen (Array) gir resultatene:

3 5 6

og

7 9 15 14 22 11 19 17 24

Å ha det gjenværende settet vil gi:

7 9 11 14 22 15 19 17 24

Å trekke ut 7 og legge den til den nye listen gir resultatene:

3 5 6 7

og

9 11 14 22 15 19 17 24

Å ha det gjenværende settet gir:

9 11 14 22 15 19 17 24

Å trekke ut 9 og legge til den nye listen, gir resultatene:

3 5 6 7 9

og

11 14 22 15 19 17 24

Å ha det gjenværende settet gir:

11 14 17 15 19 22 24

Å trekke ut 11 og legge den til den nye listen gir resultatene:

3 5 6 7 9 11

og

14 17 15 19 22 24

Å ha det gjenværende settet vil gi:

14 17 15 19 22 24

Å trekke ut 14 og legge den til den nye listen gir resultatene:

3 5 6 7 9 11 14

og

17 15 19 22 24

Å ha det gjenværende settet vil gi:

15 17 19 22 24

Å trekke ut 15 og legge den til den nye listen gir resultatene:

3 5 6 7 9 11 14 15

og

17 19 22 24

Å ha det gjenværende settet vil gi:

17 19 22 24

Å trekke ut 17 og legge den til den nye listen gir resultatene:

3 5 6 7 9 11 14 15 17

og

19 22 24

Å ha det gjenværende settet vil gi:

19 22 24

Å trekke ut 19 og legge den til den nye listen gir resultatene:

3 5 6 7 9 11 14 15 17 19

og

22 24

Å ha det gjenværende settet gir:

22 24

Å trekke ut 22 og legge den til den nye listen gir resultatene:

3 5 6 7 9 11 14 15 17 19 22

og

24

Å ha det gjenværende settet gir:

24

Å trekke ut 24 og legge den til den nye listen gir resultatene:

3 5 6 7 9 11 14 15 17 19 22 24

og

- - -

Heap -arrayen er nå tom. Alle elementene det hadde i begynnelsen er nå i den nye matrisen (listen) og sortert.

Heapsort -algoritmen

Selv om leseren kanskje har lest i lærebøker som Heapsort består av to etapper, kan Heapsort fremdeles sees på som bestående av ett trinn, som iterativt krymper av det gitte utvalget. Med det er algoritmen for å sortere med Heapsort som følger:

• Heapify den usorterte listen.
• Pakk ut det første elementet i haugen og legg det som det første elementet i den nye listen.
• Heapify den gjenværende listen.
• Pakk ut det første elementet i den nye haugen og sett som det neste elementet i den nye listen.
• Gjenta de foregående trinnene i orden til heaplisten er tom. Til slutt er den nye listen sortert.

Heapsort tidskompleksitet riktig

En-trinns tilnærming brukes til å bestemme tidskompleksiteten for heapsort. Anta at det er 8 usorterte elementer som skal sorteres.

Det mulige maksimale antall operasjoner for å huse de 8 elementene er 8.
Det mulige maksimale antall operasjoner for å huse de resterende 7 elementene er 7.
Det mulige maksimale antall operasjoner for å huse de resterende 6 elementene er 6.
Det mulige maksimale antall operasjoner for å huse de resterende 5 elementene er 5.
Det mulige maksimale antall operasjoner for å huse de resterende 4 elementene er 4.
Det mulige maksimale antall operasjoner for å huse de resterende 3 elementene er 3.
Det mulige maksimale antall operasjoner for å huse de resterende 2 elementene er 2.
Det mulige maksimale antall operasjoner for å huse det gjenværende 1 elementet er 1.

Det mulige maksimale antall operasjoner er:

8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

Gjennomsnittet av disse antall operasjoner er:

36/8 = 4.5

Legg merke til at de fire siste hauene i forrige illustrasjon ikke endret seg, da det første elementet ble fjernet. Noen av de forrige haugene endret seg ikke også når det første elementet ble fjernet. Med det er et bedre gjennomsnittlig antall hovedoperasjoner (swappings) 3 og ikke 4.5. Så et bedre totalt gjennomsnittlig antall hovedoperasjoner er:

24 = 8 x 3
=> 24 = 8 x log₂8

siden loggen₂8 = 3.

Generelt er den gjennomsnittlige casetidskompleksiteten for Heapsort:

På.log2n)

Der prikken betyr multiplikasjon og n er n, er det totale antall elementer i listen (begge listen).

Merk at driften av å trekke ut det første elementet er blitt ignorert. Når det gjelder tidskompleksitet, blir operasjoner som tar relativt korte tider ignorert.

Koding i c++

I algoritmebiblioteket til C ++ er det en make_heap () -funksjon. Syntaksen er:

mal
constExpr void make_heap (randomAccessiterator First, randomAccessIterator sist, sammenlign komp);

Det tar iteratoren som peker på det første elementet i en vektor som det første argumentet, og deretter peker iteratoren rett utenfor slutten av vektoren som det siste argumentet. For den forrige usorterte listen, vil syntaksen bli brukt som følger for å oppnå en minimums haug:

vektor VTR = 9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15;
vektor:: iterator iterb = vtr.begynne();
vektor:: Iterator Iterere = VTR.slutt();
make_heap (iterb, itere, større());

Denne koden endrer et vektorinnhold til en minimum Heap -konfigurasjon. I de følgende C ++ vektorer vil to vektorer bli brukt i stedet for to matriser.

For å kopiere og returnere det første elementet i en vektor, bruk vektorsyntaks:

constExpr referansefront ();

For å fjerne det første elementet i en vektor og kaste den bort, bruk vektorsyntaks:

constExpr iterator erase (const_iterator posisjon)

For å legge til et element på baksiden av en vektor (neste element), bruk vektorsyntaks:

constExpr void push_back (const t & x);

Begynnelsen på programmet er:

#inkludere
#inkludere
#inkludere
ved hjelp av navneområdet STD;

Algoritmen og vektorbibliotekene er inkludert. Neste i programmet er Heapsort () -funksjonen, som er:

ugyldige heapsort (vektor & oldv, vektor & newv)
hvis (oldv.størrelse ()> 0)
vektor:: iterator iterb = oldv.begynne();
vektor:: Iterator Iterere = oldv.slutt();
make_heap (iterb, itere, større());
int neste = oldv.front();
oldv.slette (iterb);
Newv.push_back (neste);
Heapsort (OldV, Newv);

Det er en rekursiv funksjon. Den bruker make_heap () -funksjonen til C ++ algoritmebiblioteket. Det andre kodesegmentet i funksjonsdefinisjonen trekker ut det første elementet fra den gamle vektoren etter haugbygningen og legger til som det neste elementet for den nye vektoren. Merk at i funksjonsdefinisjonen er vektorparametrene referanser, mens funksjonen kalles med identifikatorene (navn).

En passende C ++ hovedfunksjon for dette er:

int main (int argc, char ** argv)

vektor oldV = 9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15;
vektor Newv;
Heapsort (OldV, Newv);
for (int i = 0; icout << newV[i] << ";

cout << endl;
retur 0;

Utgangen er:

3 5 6 7 9 11 14 15 17 19 22 24

sortert (helt).

Konklusjon

Artikkelen diskuterte i detalj arten og funksjonen til haugesort som ofte er kjent som Heapsort, som en sorteringsalgoritme. Heapify tidskompleksitet, heapsort illustrasjon og heapsort som algoritme ble dekket og støttet av eksempler. Gjennomsnittlig tidskompleksitet for et velskrevet Heapsort-program er O (NLOG (N))