Heapify tidskompleksitet og C -språket
Den ovennevnte minimumshaugen beskriver en haug der antallet barn per foreldrode kan være mer enn to. En binær haug er en der det høyeste antallet barn per foreldrode er to. En komplett binær haug er en der hver node har to barn, med unntak av at det på laveste nivå bare kan være en bladnode uten søsken; Med resten av de laveste bladnodene sammenkoblet og begynnelsen av den ekstreme venstre enden av den siste raden, og slutter med denne enkeltbladnoden, som må være en venstre node.
Hauger betyr å bygge (skape) en haug. Siden et tre der hver node kan ha et hvilket som helst antall barn kan gjøres om til et komplett binært tre, er det sanne målet med denne artikkelen å produsere tidskompleksiteten for å ha et komplett binært tre.
Et eksempeldiagram over et komplett binært tre er:
Enhver bladnode på det laveste nivået som ikke har søsken, må være en venstre node. Alle nodene på den siste raden, inkludert en mulig enkelt venstre node, er "skyllet" til venstre ende av den siste raden.
Ved definisjonen av en haug kan en venstre søsken være mindre, større eller lik høyre søsken. Bestillingen av begge søsknene er ikke spesifisert.
Fullt binært tre
Treet ovenfor er et komplett binært tre, men det er ikke et fullt binært tre. Det er også et minimums haug. Hvis det var et fullt binært tre, ville alle nodene på siste-men-en-nivået hatt to barn hver. Treet ovenfor er tegnet nedenfor som et fullt binært tre:
Et tre kan være representert av en matrise. Treet leses fra topp til bunn, venstre til høyre, rad for rad; deretter plassert i matrisen. Følgende tabell viser rekke innhold og indekser for dette treet:
| 4 | 6 | 12 | 8 | 7 | 16 | 15 | 23 | 10 | 20 | 18 | 25 | null | null | null |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 1. 3 | 14 |
Celleverdiene er i den første tabellraden. De nullbaserte indeksene er i den andre tabellraden.
Forholdet mellom en foreldreindeks og dens barn indekser
I treet eller tilsvarende matrise er roten ved indeks 0 for nullbasert indeksering. La jeg være variabelen for å holde hver indeks. Barna til roten er ved indeks 1 og 2, som er 0 + 1 og 0 + 2. Barna til node 1 er ved indekser 3 og 4, som er 1 + 2 og 1 + 3. Barna til node 2 er ved indeks 5 og 6, som er 2 + 3 og 2 + 4. Barna til node 3 er ved indeks 7 og 8, som er 3 + 4 og 3 + 5. Barna til node 4 er ved indeks 9 og 10, som er 4 + 5 og 4 + 6; og så videre.
La jeg være foreldreindeksen for nå. Så barna til hver forelder er på indeks I + I + 1 og ved i + I + 2, som er:
2i +1 og 2i +2
Det motsatte skal være kjent. Det vil si gitt en indeks, jeg for et venstre barn eller høyre barn, hva er foreldreindeksen? For venstre barn på indeks 1 og høyre barn på indeks 2, er foreldrene ved indeks 0. For venstre barn på indeks 3 og høyre barn på indeks 4, er foreldrene ved indeks 1. For venstre barn på indeks 5 og høyre barn på indeks 6, er foreldrene ved indeks 2. For venstre barn på indeks 7 og høyre barn på indeks 8, er forelderen på indeks 3. For venstre barn på indeks 9 og høyre barn på indeks 10, er forelderen på indeks 4.
I denne gangen, er en barneindeks (ikke en foreldreindeks). Så foreldrene til hvert venstre barn er på indeks I/2 i Heltalldivisjon, og foreldrene til det rette barnet, som er det samme som foreldrene til venstre barn (søsken), er i heltallsresultat av (i-1) /2, jeg.e.:
I/2 og (i-1)/2
der divisjonen er heltalldivisjon.
Det er også godt å vite om en node er et venstre barn eller et høyre barn: Hvis normal inndeling av 2 har en resten, er det en venstre node med nullbasert indeksering. Hvis normal inndeling med 2 ikke har noen resten, er det en riktig node med nullbasert indeksering.
Koden i C, for å vite om barneknuten er en venstre node eller en høyre node, er:
if (i%2 == 0)
// Node er en høyre node
ellers
// Node er venstre node
Etter å ha visste at en node er en venstre node, kan overordnet indeks oppnås som et heltallsresultat av I/2. Etter å ha visste at en node er en riktig node, kan overordnet indeks oppnås som et heltallsresultat av (i-1)/2.
Høyden på en full binær haug og noen indekser
Totalt antall noder
Legg merke til fra det siste fulle diagrammet over at når nivået på en haug øker med 1, er det totale antallet noder omtrent dobler. Nettopp kommer neste nivå med antall noder som gjør det nye totalen, summen av alle de tidligere nodene, pluss 1, ganger 2, deretter minus 1. Når høyden er 1, er det 1 node = (0 + 1) x 2 - 1 = 2 - 1 = 21 - 1. Når høyden er 2, er det 3 noder = (1 + 1) x 2 - 1 = 4 - 1 = 22 - 1. Når høyden er 3, er det 7 noder = (3 + 1) x 2 - 1 = 8 - 1 = 23 - 1. Når høyden er 4, er det 15 noder = (7 + 1) x 2 - 1 = 16 - 1 = 24 - 1. Når høyden er 5, er det 31 noder = (15 + 1) x 2 - 1 = 32 - 1 = 25 - 1. Når høyden er 6, er det 63 noder = (31 + 1) x 2 - 1 = 64 - 1 = 26 - 1. Når høyden er 7, er det 127 noder = (63 + 1) x 2 - 1 = 128 - 1 = 27 - 1; og så videre.
Generelt, når høyden er h,
Nei. av noder = 2H - 1
Siste nodeindeks
For et binært tre og for nullbasert indeksering er den siste indeksen:
siste indeks = n - 1
Hvor n er det totale antallet noder, eller bare antall noder.
Antall noder uten siste rad
For et fullt binært tre gir to ganger antall noder for den siste raden det totale antallet noder minus 1. Sett på en annen måte, antall noder for den siste raden er lik antallet av alle de tidligere nodene, Times Two, pluss 1. Så antall noder uten den siste raden er:
Nei. av noder uten siste = heltallsresultat av n/2
Dette er fordi, for nullbasert indeksering, det totale antallet noder for et fullt binært tre alltid er et oddetall. For eksempel: Hvis antallet noder (totalt) er 15, så 15/2 = 7½. Heltallresultatet, 7, er tatt, og halvparten blir kastet. Og 7 er antall noder uten siste rad - se ovenfor.
Indeks for første node av den siste raden
Indeksen for den første noden til den siste raden skal være kjent. For nullbasert indeksering, der den første noden (elementet) er ved indeks 0, er indeksen for den første noden til den siste raden antall noder for alle nodene uten den siste raden. Det er:
heltallsresultat av n/2
Legg merke til at i den tilsvarende matrisen kalles treknutene elementer.
Sikt opp og sikt ned
Tenk på følgende undertrekk av tre noder:
Etter minimum Heap -eiendom, skal foreldroden være mindre enn eller lik den minste av barneknuter. Så node C må byttes med de minste av barneknutene; Det spiller ingen rolle om minst er venstre eller høyre søsken. Dette betyr at C må byttes med en å ha:
Når "A" beveger seg opp for å ta plassen til C, er det sile opp. Når C beveger seg ned for å ta plassen til A, er det sile ned.
Heapifiserende illustrasjon
Haugen, som vist ovenfor, er delvis bestilling, fra minste verdi til største verdi. Det er ikke grundig bestilling (ikke sorterer). Som uttrykt ovenfor, kan haugen være i treform eller i matriseform. Som uttrykt ovenfor, har heaping allerede funnet sted. I praksis vil ikke programmereren nødvendigvis finne et tre som allerede er dynget. Han ville finne en liste som er helt i uorden (helt usortert). Denne forstyrrede listen kan eksistere i form av et tre eller i form av en matrise. Følgende er et forstyrret (usortert) tre og dets tilsvarende matrise:
Den tilsvarende matrisen er:
| 10 | 20 | 25 | 6 | 4 | 12 | 15 | 23 | 8 | 7 | 18 | 16 | null | null | null |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 1. 3 | 14 |
Treet leses rad-for-rad, fra venstre mot høyre og fra topp til bunn, mens det er plassert i matrisecellene. La array-navnet være ARR, og la variabelen som representerer den nullbaserte indeksen være i. I denne artikkelen er roten ved indeks 0.
Dette treet vil gjennomgå delvis bestilling for å bli en minimum haug. Når den delvise bestillingen er fullført, vil den være minimums haug gitt i introduksjonsdelen av denne artikkelen. I denne delen gjøres den delvise bestillingen manuelt.
For å forenkle dynfing (delvis bestillingsprosess), må det komplette uordnede binære treet lages et fullt binært tre før det blir behandlet. For å gjøre det til et fullt binært tre, legg til elementer hvis verdier er større enn den høyeste verdien som allerede er funnet i den uordnede haugen. I denne artikkelen vil dette bli gjort med matrisen og ikke med grafformen til treet.
Det høyeste elementet (noden) er 25. La de tre tallene lagt til for å få et fullt tre: 26, 27 og 28. Den tilsvarende matrisen for hele treet blir:
| 10 | 20 | 25 | 6 | 4 | 12 | 15 | 23 | 8 | 7 | 18 | 16 | 26 | 27 | 28 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 1. 3 | 14 |
Når den uordnede listen blir delvis bestilt av Heap -definisjonen, vil de tre siste elementene forbli på sine siste posisjoner; og kan lett forlates.
Når denne uordnede listen er delvis bestilt av Heap -definisjonen, vil den være den delvis bestilte listen gitt ovenfor (Introduksjon). En delvis bestilt liste har en sortering, men den er ikke fullstendig bestilling (det er ikke fullstendig sortering).
Manuell omorganisering (Heap Building)
Den uordnede matrisen kan plasseres slik:
10 20 25 06 04 12 15 23 08 07 18 16 26 27 28
Det er 15 elementer. Heltallresultatet av 15/2 er 7. Listen skal deles inn i to halvdeler, med den første omgangen 7 og andre omgang, 8, som følger:
10 20 25 06 04 12 15 | 23 08 07 18 16 26 27 28
Denne divisjonen kan betraktes som en hovedoperasjon. Heapbuilding fortsetter fra høyre ende med par av elementer, 27 og 28, identifisert som barn på 15. 15 er mindre enn 27 eller 28. Så dette undertræret av tre noder tilfredsstiller minimumsegenskapen, og nodene blir ikke berørt for nå. Denne kontrollen kan betraktes som en annen hovedoperasjon. Så det er to hovedoperasjoner så langt (en array divisjon og en sjekk).
16 og 26 er barn på 12. 12 er mindre enn 16 eller 26. Så dette undertræret av tre noder tilfredsstiller minimum Heap-eiendom, og nodene berøres ikke (foreløpig). Denne kontrollen kan betraktes som en annen hovedoperasjon. Så det er tre hovedoperasjoner så langt (en divisjon og to sjekker).
07 og 18 er barna til 04. 04 er mindre enn 07 eller 18. Så dette undertræret av tre noder tilfredsstiller minimum Heap-eiendom, og nodene berøres ikke (foreløpig). Denne kontrollen kan betraktes som en annen hovedoperasjon. Så det er fire hovedoperasjoner så langt (en divisjon og tre sjekker).
23 og 08 er barna til 06. 06 er mindre enn 23 eller 08. Så dette undertræret av tre noder tilfredsstiller minimum Heap-eiendom, og nodene berøres ikke (foreløpig). Denne kontrollen kan betraktes som en annen hovedoperasjon. Så det er fem hovedoperasjoner så langt (en divisjon og fire sjekker).
Alle de 8 elementene i den siste raden av treet, og foreldrene deres, er sjekket. For å gå til forrige nivå, må venstre del av treet deles med 2, og heltallresultatet blir tatt. Heltallresultat av 7/2 er 3. Den nye plasseringen av listen er:
10 20 25 | 06 04 12 15 | 23 08 07 18 16 26 27 28
Denne divisjonen kan betraktes som en hovedoperasjon. Så det er seks hovedoperasjoner så langt (to divisjoner og fire sjekker).
12 og 15 er barna til 25. 25 er større enn 12 eller 15. Dette undertræren av tre noder tilfredsstiller ikke minimumsegenskapen, så nodene må berøres. Imidlertid kan denne sjekkingen fremdeles betraktes som en annen hovedoperasjon. Så det er syv hovedoperasjoner så langt (to divisjoner og fem sjekker).
Sifting nedover må finne sted og muligens ned til siste rad. Hver sikting (bytte) er hovedoperasjonen.
25 byttes med det minste av barna, 12 for å gi konfigurasjonen:
10 20 12 | 06 04 25 15 | 23 08 07 18 16 26 27 28
25 er nå på tredje nivå og ikke lenger på andre nivå. 25 er nå foreldre til 16 og 26. På dette tidspunktet er 25 tilfeldigvis større enn 16, men mindre enn 26. Så 25 og 16 byttes ut. Denne bytteen er en annen hovedoperasjon, og det er så ni hovedoperasjoner så langt (to divisjoner, fem sjekker og to bytter). Den nye konfigurasjonen er:
10 20 12 | 06 04 16 15 | 23 08 07 18 25 26 27 28
På det andre nivået på den gitte listen var det 20 og 25. 25 har blitt siktet helt ned til siste rad. 20 skal fremdeles sjekkes.
For øyeblikket er 06 og 04 barn på 20. 20 er større enn 06 eller 04. Dette undertræren av tre noder tilfredsstiller ikke minimumsegenskapen, så nodene må berøres. Imidlertid kan denne sjekkingen fremdeles betraktes som en annen hovedoperasjon. Så det er ti hovedoperasjoner så langt (to divisjoner, seks sjekker og to bytter). Sifting nedover må finne sted og muligens ned til siste rad. Hver sikting (bytte) er hovedoperasjonen.
20 byttes med det minste av barna, 04 for å gi konfigurasjonen:
10 04 12 | 06 20 16 15 | 23 08 07 18 25 26 27 28
20 er nå på tredje nivå og ikke lenger på andre nivå. 20 er nå foreldre til 07 og 18. På dette tidspunktet er 20 tilfeldigvis større enn 07 eller 18. Så 20 og 07 byttes ut. Denne byttet er en annen hovedoperasjon, og det er sånn tolv hovedoperasjoner så langt (to divisjoner, seks sjekker og fire bytter). Den nye konfigurasjonen er:
10 04 12 | 06 07 16 15 | 23 08 20 18 25 26 27 28
Siktinger nedover av forrige vei er avsluttet. Den venstre delen som ikke er fullstendig sjekket, må deles inn i to (går til forrige nivå) for å ha:
10 | 04 12 | 06 07 16 15 | 23 08 20 18 25 26 27 28
Heltallresultatet av 3/2 er 1.
For øyeblikket er 04 og 12 barn til 10. 10 er større enn 04, men mindre enn 12. Dette undertræren av tre noder tilfredsstiller ikke minimumsegenskapen, så nodene må berøres. Imidlertid bør denne sjekkingen fortsatt betraktes som en annen hovedoperasjon. Så det er fjorten hovedoperasjoner så langt (tre divisjoner, syv sjekker og fire bytter). Sifting nedover må finne sted og muligens ned til siste rad. Hver sikting (bytte) er hovedoperasjonen.
10 byttes med det minste av barna, 04 for å gi konfigurasjonen:
04 | 10 12 | 06 07 16 15 | 23 08 20 18 25 26 27 28
10 er nå på andre nivå og ikke lenger på første nivå. 10 er nå foreldre 06 og 07. På dette tidspunktet er 10 tilfeldigvis større enn 06 eller 07. Så 10 og 06 byttes ut. Denne bytteen er en annen hovedoperasjon, og det er derfor seksten hovedoperasjoner så langt (tre divisjoner, syv sjekker og seks bytter). Den nye konfigurasjonen er:
04 | 06 12 | 10 07 16 15 | 23 08 20 18 25 26 27 28
10 er nå på tredje nivå og ikke lenger på andre nivå. 10 er nå foreldre 23 og 08. På dette tidspunktet er 10 tilfeldigvis mindre enn 23, men større enn 08. Så 10 og 08 byttes ut. Denne bytteen er en annen hovedoperasjon, og det er så langt det er sytten hovedoperasjoner (tre divisjoner, syv sjekker og syv bytter). Den nye konfigurasjonen er:
04 | 06 12 | 08 07 16 15 | 23 10 20 18 25 26 27 28
Vel, sjekkingen, delingen og byttet begynte ved den siste indeksen og har nådd den første indeksen, med alle konsekvensene av nedadgående sile. Dette betyr at Heap Building er fullført, og i dette tilfellet med sytten hovedoperasjoner (tre divisjoner, syv sjekker og syv bytter). Det var 15 elementer, selv om de tre siste var dummyelementer som trengs for å forenkle haugbygningen.
Algoritme
Det er forskjellige algoritmer for haugbygging. Illustrasjonen gitt ovenfor vil være den mest effektive hvis en overordnet verdi blir byttet med noen av barna som er mindre og ikke alltid det minste av barna. Trinnene for algoritmen er:
- Del hele antall elementer med to.
- Fortsett fra høyre halvdel, sjekk et par søsken med foreldrene og bytte om nødvendig.
- Når alle nodene på det siste nivået er sjekket, med mulig bytte, fortsett til forrige nivå og gjenta de to trinnene ovenfor. Bytting er sile ned, og dette må kanskje nå det laveste nivået.
- Når roten er sjekket og muligens byttet, stopp.
Tidskompleksitet
Tidskompleksitet er den relative kjøretiden til en viss kode. I dette tilfellet er det den relative kjøretiden til Building Process. Tidskompleksitet er faktisk antall hovedoperasjoner i koden (programmet).
Offisielt sies tidskompleksiteten til algoritmen for denne artikkelen å være N -operasjoner, der N er antall elementer i den uordnede matrisen pluss dummyelementene. I dette tilfellet er N 15. Så tidskompleksiteten for denne algoritmen er 15.
Hvorfor skal det være 15 i stedet for 17? Det vil si, hvorfor skal det være n? - Vel, siden divisjon ikke er partisjon, er varigheten for hver divisjonsaksjon liten og kan forsømmes. Med det og for illustrasjonen ovenfor vil antall hovedoperasjoner bli 14 (syv sjekker og syv bytter), med de 3 divisjonene ignorert.
Hvis en foreldreverdi blir byttet med noen av barna som er mindre, og ikke alltid det minste av barna, vil den samlede sjekktiden reduseres. Dette vil gjøre sjekkingstid liten og så ignorert. Med det og for illustrasjonen ovenfor vil antall hovedoperasjoner bli 7 (syv bytter), med de 3 divisjonene ignorert og de syv sjekkene også ignorert.
Merk: For et godt Building -program. I dette tilfellet er det 7 operasjoner og ikke 15. Når det gjelder å håndtere tidskompleksitet, er det maksimalt mulige antall operasjoner det som må gis.
Det er mulig for alle de 15 nodene ovenfor å bli byttet. Så tidskompleksiteten for dette eksemplet må gis som 15 og ikke 7.
Tidskompleksiteten for denne algoritmen er gitt, generelt sett, som:
På)
Hvor n er n, dette er Big-O-notasjonen. Denne notasjonen bruker store O og dens parenteser. Inne i parentesene er uttrykket for mulig maksimalt antall operasjoner for koden (programmet) å fullføre.
Koding i c
C-hovedfunksjonen for å høste ovennevnte matrise er:
int main (int argc, char ** argv)
int n1 = 12;
int a1 [] = 10, 20, 25, 6, 4, 12, 15, 23, 8, 7, 18, 16;
int a2 [] = 10, 20, 25, 6, 4, 12, 15, 23, 8, 7, 18, 16, 26, 27, 28;
buildheap (A2, N2);
for (int i = 0; i = arr [leftindx] && arr [leftindx]> = arr [rightindx])
int temp = arr [parentindx]; arr [ParentIndx] = arr [rightindx]; arr [rightindx] = temp;
Lastdown = RightIndx;
ellers if (arr [ParentIndx]> = arr [rightindx] && arr [rightindx]> = arr [venstreindx])
int temp = arr [parentindx]; arr [ParentIndx] = arr [venstreindx]; arr [leftindx] = temp;
Lastdown = LeftIndx;
ellers if (arr [ParentInDX]> = arr [rightindx] && arr [rightindx] = arr [leftindx] && arr [leftindx] <= arr[rightIndx])
int temp = arr [parentindx]; arr [ParentIndx] = arr [venstreindx]; arr [leftindx] = temp;
Lastdown = LeftIndx;
Return Lastdown;
Det er en sikt-ned-funksjon. Den ville bruke SWAP () -funksjonen og sile ned til høyre til det laveste nivået i en bane. Det er:
int nextindx;
void Siftdown (int arr [], int n2, int i)
int venstreindx, RightIndx;
int parentindx = i;
venstreindx = 2*i+1;
RightIndx = 2*i+2;
if (parentIndx = 0)
nextInDX = Swap (arr, ParentIndx, LeftIndx, RightIndx);
if (nextindx = halvindx/2; i--)
SIFTDOWN (A2, N2, I);
N = n/2;
if (n> = 1)
buildheap (a2, n);
Alle ovennevnte kodesegmenter kan settes sammen for å danne et program som vil ha den uordnede matrisen.
Konklusjon
Den mest effektive algoritmen for Heapify tidskompleksitet er:
På)