Heapsort Tidskompleksitet

En bunke omtales som 'delvis ordnet' og ikke 'delvist sorteret'. Ordet 'sortering' betyder fuldstændig bestilling (fuldstændig sortering). En bunke er ikke delvist ordnet vilkårligt. En bunke er delvist ordnet efter et kriterium (mønster), som vist nedenfor.

Så heapsort består af to trin: opbygning af heapen og udtrækning af det bestilte element fra toppen af ​​heapen. I anden fase, efter hver ekstraktion, genopbygges dyngen. Hver ombygning er hurtigere end den oprindelige byggeproces, da ombygningen udføres fra en tidligere bygning, hvor et element er blevet fjernet. Og dermed sorterer heapsort en fuldstændig usorteret liste.

Formålet med denne artikel er kort at forklare heapsort og derefter producere dens tidskompleksitet (se betydningen af ​​tidskompleksitet nedenfor). Mod slutningen sker kodningen i C++.

Minimum bunke

En bunke kan være en minimal bunke eller en maksimal bunke. En max-heap er en, hvor det første element er det højeste element, og hele træet eller den tilsvarende liste er delvist ordnet i faldende rækkefølge. En min-heap er en, hvor det første element er det mindste element, og hele listen er delvist ordnet i stigende rækkefølge. I denne artikel er kun minimumsbunken taget i betragtning. Bemærk: i emnet for heapen kaldes et element også en node.

En bunke er et komplet binært træ. Det binære træ kan udtrykkes som en matrix (liste); læses fra top til bund og fra venstre mod højre. Heap-egenskaben for en min-heap er, at en overordnet node er mindre end eller lig med hver af dens to børn. Et eksempel på en uordnet liste er:

Den første række i denne tabel er elementerne i arrayet. I anden række er de nul-baserede indekser. Denne liste over elementer kan udtrykkes som et træ. Null-elementerne er blevet tilføjet for at lave et fuldt binært træ. Strengt taget er null-elementerne ikke en del af listen (træet). Denne liste har ingen rækkefølge, så den er ikke en bunke endnu. Det bliver til en bunke, når den har fået delbestilling, ifølge bunkeejendommen.

Forholdet mellem noder og indekser

Husk, at en heap er et komplet binært træ, før den har heap-konfigurationen (heap-egenskab). Den tidligere liste er endnu ikke en bunke, fordi elementerne ikke adlyder heap-egenskaben. Det bliver en heap efter at have omarrangeret elementer i delvis rækkefølge i henhold til min-heap-egenskaben. Delvis rækkefølge kan ses som delvis sortering (selvom ordet 'sortering' betyder fuldstændig rækkefølge).

Uanset om et binært træ er en bunke eller ej, har hver forælder to børn, undtagen bladknuderne (sidste). Der er en matematisk sammenhæng mellem indeksene mellem hver forælder og dens børn. Det er som følger: Hvis forælderen er ved indeks i, så er det venstre barn ved indeks:

og det rigtige barn er på indekset:

Dette er til nul-baseret indeksering. Og så har en forælder ved indeks 0 sit venstre barn ved indeks 2×0+1=1 og dets højre barn ved 2×0+2=2. En forælder ved indeks 1 har sit venstre barn ved indeks 2×1+1=3 og højre barn ved indeks 2×1+2=4; og så videre.

Ved min-heap-egenskaben er en forælder ved i mindre end eller lig med venstre barn ved 2i+1 og mindre end eller lig med højre barn ved 2i+2.

Dynge

Heapifying betyder at bygge en heap. Det betyder at omarrangere elementerne i en liste (eller tilsvarende træ), så de opfylder heap-egenskaben. I slutningen af ​​ophobningsprocessen er listen eller træet en hob.

Hvis den tidligere usorterede liste er ophobet, bliver den:

Bemærk: der er 12 elementer og ikke 15 på listen. I anden række er indekserne. I bunkebygningsprocessen skulle elementer kontrolleres, og nogle byttes.

Bemærk, at det mindste og første element er 3. Resten af ​​elementerne følger efter på en stigende, men bølgende måde. Hvis venstre og højre børn i position 2i+1 og 2i+2 hver især er større end eller lig med forælderen ved i, så er dette en min-heap. Dette er ikke fuld bestilling eller sortering. Dette er delvis bestilling, ifølge bunkeejendommen. Det er herfra, at den næste fase for bunkesortering starter.

Heapify Tidskompleksitet

Tidskompleksitet er den relative køretid for en eller anden kode. Det kan ses som antallet af hovedoperationer, som den kode skal fuldføre. Der er forskellige algoritmer til heap building. De mest effektive og hurtigste deler løbende listen med to, kontrollerer elementerne fra bunden og laver derefter nogle udskiftninger af elementer. Lad N være antallet af praktiske elementer i listen. Med denne algoritme er det maksimale antal hovedoperationer (swapping) N. Tidskompleksiteten for heapifying er tidligere givet som:

Hvor n er N og er det maksimalt mulige antal hovedoperationer. Denne notation kaldes Big-O notationen. Det begynder med O i store bogstaver efterfulgt af parenteser. Inde i parentesen er udtrykket for det mulige højeste antal operationer.

Husk: addition kan blive multiplikation, hvis det samme, der tilføjes, bliver ved med at gentages.

Heapsort Illustration

Den tidligere usorterede liste vil blive brugt til at illustrere heapsort. Den givne liste er:

Min-bunken produceret fra listen er:

Det første trin i heapsort er at producere den bunke, der er blevet produceret. Dette er en delvist ordnet liste. Det er ikke en sorteret (fuldstændig sorteret) liste.

Det andet trin består i at fjerne det mindste element, som er det første element, fra heapen, at genophobe den resterende bunke og fjerne de mindste elementer i resultaterne. Det mindste element er altid det første element i den re-heapified heap. Elementerne fjernes og smides ikke væk. De kan sendes til et andet array i den rækkefølge, de fjernes i.

I sidste ende ville det nye array have alle elementerne sorteret (helt), i stigende rækkefølge; og ikke længere kun delvist bestilt.

I anden fase er den første ting at gøre at fjerne 3 og placere den i det nye array. Resultaterne er:

og

De resterende elementer skal ophobes, før det første element udtrækkes. Bunken af ​​de resterende elementer kan blive:

Udtræk 5 og tilføjelse til den nye liste (array) giver resultaterne:

og

At ophobe det resterende sæt ville give:

Udtræk 6 og tilføjelse til den nye liste (array) giver resultaterne:

og

At ophobe det resterende sæt ville give:

Udtræk 7 og tilføjer det til den nye liste giver resultaterne:

og

Ophopning af det resterende sæt giver:

Udtræk 9 og tilføjelse til den nye liste giver resultaterne:

og

Ophopning af det resterende sæt giver:

Udtræk 11 og tilføjer det til den nye liste giver resultaterne:

og

At ophobe det resterende sæt ville give:

Udtræk 14 og tilføjer dem til den nye liste giver resultaterne:

og

At ophobe det resterende sæt ville give:

Udtræk 15 og tilføjer dem til den nye liste giver resultaterne:

og

At ophobe det resterende sæt ville give:

Udtræk 17 og tilføjer dem til den nye liste giver resultaterne:

og

At ophobe det resterende sæt ville give:

Ved at udtrække 19 og tilføje dem til den nye liste får du resultaterne:

og

Ophopning af det resterende sæt giver:

Udtræk 22 og tilføjer dem til den nye liste giver resultaterne:

og

Ophopning af det resterende sæt giver:

Udtræk 24 og tilføjer dem til den nye liste giver resultaterne:

og

Heap-arrayet er nu tomt. Alle de elementer, den havde i begyndelsen, er nu i det nye array (liste) og sorteret.

Heapsort-algoritme

Selvom læseren måske har læst i lærebøger, at heapsort består af to faser, kan heapsort stadig ses som bestående af et trin, som iterativt formindsker det givne array. Med det er algoritmen til at sortere med heapsort som følger:

• Opfyld den usorterede liste.
• Udpak det første element af heapen og sæt det som det første element i den nye liste.
• Opfyld den resterende liste.
• Udpak det første element i den nye bunke og sæt det som det næste element i den nye liste.
• Gentag de foregående trin i rækkefølge, indtil bunkelisten er tom. Til sidst sorteres den nye liste.

Heapsort Tidskompleksitet Egentlig

En-trins tilgangen bruges til at bestemme tidskompleksiteten for heapsort. Antag, at der er 8 usorterede elementer, der skal sorteres.

Det mulige maksimale antal operationer er:

Gennemsnittet af disse antal operationer er:

Bemærk, at de sidste fire dynger i den foregående illustration ikke ændrede sig, da det første element blev fjernet. Nogle af de tidligere dynger ændrede sig ikke også, da det første element blev fjernet. Med det er et bedre gennemsnitligt antal hovedoperationer (swappings) 3 og ikke 4,5. Så et bedre samlet gennemsnitligt antal hovedoperationer er:

siden log _to 8 = 3.

Generelt er den gennemsnitlige sagstidskompleksitet for heapsort:

Hvor prikken betyder multiplikation og n er N, det samlede antal elementer på listen (enten af ​​listen).

Bemærk, at operationen med at udtrække det første element er blevet ignoreret. Med hensyn til emnet Tidskompleksitet ignoreres operationer, der tager relativt kort tid.

Kodning i C++

I algoritmebiblioteket i C++ er der en make_heap() funktion. Syntaksen er:

Det tager iteratoren, der peger på det første element i en vektor som dets første argument, og derefter iteratoren, der peger lige ud over slutningen af ​​vektoren som dets sidste argument. For den tidligere usorterede liste ville syntaksen blive brugt som følger for at opnå en minimumsbunke:

Denne kode ændrer et vektorindhold til en minimal heap-konfiguration. I de følgende C++ vektorer vil to vektorer blive brugt i stedet for to arrays.

For at kopiere og returnere det første element i en vektor skal du bruge vektorsyntaksen:

For at fjerne det første element i en vektor og smide det væk, skal du bruge vektorsyntaksen:

For at tilføje et element bagerst i en vektor (næste element), skal du bruge vektorsyntaksen:

Starten på programmet er:

Algoritme- og vektorbibliotekerne er inkluderet. Næste i programmet er heapsort()-funktionen, som er:

Det er en rekursiv funktion. Den bruger make_heap()-funktionen i C++-algoritmebiblioteket. Det andet kodesegment i funktionsdefinitionen udtrækker det første element fra den gamle vektor efter bunkebygningen og tilføjer som det næste element for den nye vektor. Bemærk, at i funktionsdefinitionen er vektorparametrene referencer, mens funktionen kaldes med identifikatorerne (navnene).

En passende C++ hovedfunktion til dette er:

Udgangen er:

sorteret (helt).

Konklusion

Artiklen diskuterede i detaljer arten og funktionen af ​​Heap Sort, almindeligvis kendt som Heapsort, som en sorteringsalgoritme. Heapify Time Complexity, Heapsort-illustration og Heapsort som en algoritme blev dækket og understøttet af eksempler. Den gennemsnitlige tidskompleksitet for et velskrevet heapsort-program er O(nlog(n))