Heapsortimise aja keerukus

Hunnikule viidatakse kui 'osaliselt järjestatud' ja mitte 'osaliselt sorteeritud'. Sõna “sordi” tähendab täielikku järjestamist (täielikku sorteerimist). Kuhja ei tellita osaliselt suvaliselt. Hunnik on osaliselt järjestatud kriteeriumi (mustri) järgi, nagu allpool näidatud.

Seega koosneb hunniku sorteerimine kahest etapist: kuhja ehitamine ja järjestatud elemendi eraldamine kuhja ülaosast. Teises etapis, pärast iga kaevandamist, ehitatakse hunnik uuesti üles. Iga ümberehitamine on kiirem kui algne ehitusprotsess, kuna ümberehitamine toimub eelmisest ehitusest, kus üks element on eemaldatud. Ja sellega sorteerib heapsort täiesti sortimata loendi.

Selle artikli eesmärk on lühidalt selgitada hunnikut ja seejärel luua selle ajaline keerukus (vt aja keerukuse tähendust allpool). Lõpupoole toimub kodeerimine C++ keeles.

Minimaalne hunnik

Hunnik võib olla minimaalne hunnik või maksimaalne hunnik. Max-hunnik on selline, kus esimene element on kõrgeim element ja kogu puu või vastav loend on osaliselt järjestatud kahanevas järjekorras. Min-hunnik on selline, kus esimene element on vähim element ja kogu loend on osaliselt järjestatud kasvavas järjekorras. Selles artiklis käsitletakse ainult minimaalset hunnikut. Märkus: kuhja teemas nimetatakse elementi ka sõlmeks.

Hunnik on täielik kahendpuu. Binaarset puud saab väljendada massiivina (loendina); loe ülevalt alla ja vasakult paremale. Min-hunniku kuhja omadus on see, et põhisõlm on väiksem või võrdne selle kahe alamsõlmega. Järjestamata loendi näide on järgmine:

Selle tabeli esimene rida on massiivi elemendid. Teises reas on nullpõhised indeksid. Seda elementide loendit saab väljendada puuna. Täieliku kahendpuu loomiseks on lisatud nullelemendid. Rangelt võttes ei kuulu nullelemendid loendisse (puusse). Sellel loendil pole järjestust, seega pole see veel kuhjaga. See muutub hunnikuks, kui see on vastavalt kuhja omadusele osaliselt tellitud.

Sõlmede ja indeksite vaheline seos

Pidage meeles, et hunnik on enne kuhja konfiguratsiooni (kuhja omadus) täielik binaarpuu. Eelmine nimekiri ei ole veel hunnik, sest elemendid ei allu kuhja omadusele. See muutub hunnikuks pärast elementide ümberpaigutamist osalisesse järjekorda vastavalt min-hunniku omadusele. Osalist järjestust võib vaadelda kui osalist sortimist (kuigi sõna “sort” tähendab täielikku järjestamist).

Olenemata sellest, kas kahendpuu on hunnik või mitte, on igal vanemal kaks last, välja arvatud lehe (viimased) sõlmed. Iga vanema ja tema laste indeksite vahel on matemaatiline seos. See on järgmine: kui vanem on indeksis i, siis vasak laps on indeksis:

ja õige laps on indeksis:

See on nullpõhise indekseerimise jaoks. Ja nii, vanemal indeksis 0 on vasak laps indeksis 2×0+1=1 ja parem laps 2×0+2=2. Indeksis 1 oleva vanema vasak laps on indeksis 2×1+1=3 ja parem laps indeksis 2×1+2=4; ja nii edasi.

Min-hunniku atribuudi järgi on vanem punktis i väiksem või võrdne vasakpoolse lapsega väärtusel 2i+1 ja väiksem või võrdne parempoolse lapsega väärtusel 2i+2.

Kuhja

Kuhjamine tähendab kuhja ehitamist. See tähendab loendi (või vastava puu) elementide ümberkorraldamist nii, et need vastaksid kuhja omadusele. Kuhjastamisprotsessi lõpus on loend või puu hunnik.

Kui eelmine sortimata loend on kuhjaga, muutub see:

Märkus: loendis on 12 elementi, mitte 15. Teises reas on indeksid. Kuhja ehitamise protsessis tuli elemente kontrollida ja osa vahetada.

Pange tähele, et väikseim ja esimene element on 3. Ülejäänud elemendid järgnevad tõusvalt, kuid laineliselt. Kui vasak- ja parempoolsed lapsed positsioonides 2i+1 ja 2i+2 on mõlemad suuremad või võrdsed i-s oleva vanemaga, siis on see min-hunnik. See ei ole täielik tellimine ega sorteerimine. See on osaline tellimine vastavalt hunniku omadusele. Siit algab hunniku sortimise järgmine etapp.

Kuhjake aja keerukust

Ajaline keerukus on mõne koodi suhteline tööaeg. Seda võib vaadelda kui selle koodi lõpuleviimiseks vajalike põhitoimingute arvu. Kuhjade ehitamiseks on erinevaid algoritme. Kõige tõhusamad ja kiiremad jagavad loendi pidevalt kahega, kontrollides elemente alt ja seejärel vahetades elemente. Olgu N praktiliste elementide arv loendis. Selle algoritmi puhul on põhioperatsioonide (vahetamise) maksimaalne arv N. Kuhjastamise ajaline keerukus on varem antud järgmiselt:

Kus n on N ja on põhitoimingute maksimaalne võimalik arv. Seda tähistust nimetatakse Big-O märkimiseks. See algab suurtähtedega O-ga, millele järgnevad sulud. Sulgude sees on avaldis võimaliku suurima arvu toimingute kohta.

Pidage meeles: liitmine võib muutuda korrutamiseks, kui sama liidetav asi kordub.

Heapsorti illustratsioon

Eelmist sortimata loendit kasutatakse hunnikusortimise illustreerimiseks. Antud nimekiri on järgmine:

Loendist saadud minimaalne hunnik on:

Hunniku sorteerimise esimene etapp on toodetud hunniku tootmine. See on osaliselt järjestatud nimekiri. See ei ole sorteeritud (täielikult sorteeritud) loend.

Teine etapp seisneb kuhjast vähima elemendi, mis on esimene element, eemaldamises, ülejäänud kuhja uuesti kuhjamises ja tulemustes kõige vähemate elementide eemaldamises. Vähim element on alati uuesti kuhjatud hunniku esimene element. Elemente ei eemaldata ja ära visata. Neid saab saata erinevasse massiivi nende eemaldamise järjekorras.

Lõpuks oleks uue massiivi kõik elemendid järjestatud (täielikult), kasvavas järjekorras; ja mitte enam ainult osaliselt tellitud.

Teises etapis on esimene asi, mida teha, eemaldada 3 ja asetada see uude massiivi. Tulemused on järgmised:

ja

Ülejäänud elemendid tuleb enne esimese elemendi ekstraheerimist kuhjata. Ülejäänud elementide hunnik võib olla:

5 ekstraheerimine ja uude loendisse (massiivi) lisamine annab tulemuse:

ja

Ülejäänud komplekti kuhjamine annaks:

6 ekstraheerimine ja uude loendisse (massiivi) lisamine annab tulemuse:

ja

Ülejäänud komplekti kuhjamine annaks:

7 ekstraheerimine ja uude loendisse lisamine annab tulemused:

ja

Ülejäänud komplekti kuhjamine annab:

9 ekstraheerimine ja uude loendisse lisamine annab tulemused:

ja

Ülejäänud komplekti kuhjamine annab:

11 ekstraheerimine ja uude loendisse lisamine annab tulemused:

ja

Ülejäänud komplekti kuhjamine annaks:

14 ekstraheerimine ja uude loendisse lisamine annab tulemused:

ja

Ülejäänud komplekti kuhjamine annaks:

15 ekstraheerimine ja uude loendisse lisamine annab tulemuse:

ja

Ülejäänud komplekti kuhjamine annaks:

17 ekstraheerimine ja uude loendisse lisamine annab tulemused:

ja

Ülejäänud komplekti kuhjamine annaks:

19 ekstraheerimine ja uude loendisse lisamine annab tulemused:

ja

Ülejäänud komplekti kuhjamine annab:

22 ekstraheerimine ja uude loendisse lisamine annab tulemused:

ja

Ülejäänud komplekti kuhjamine annab:

24 ekstraheerimine ja uude loendisse lisamine annab tulemused:

ja

Kuhja massiiv on nüüd tühi. Kõik elemendid, mis tal alguses olid, on nüüd uude massiivi (loendisse) ja sorteeritud.

Heapsortimise algoritm

Kuigi lugeja võis õpikutest lugeda, et hunnikusorteerimine koosneb kahest etapist, võib hunnikusortimist siiski näha ühest etapist koosnevana, mis kahandab iteratiivselt antud massiivist välja. Sellega on hunnikuga sortimise algoritm järgmine:

• Korraldage sortimata loend kuhjaga.
• Ekstraheerige kuhja esimene element ja asetage see uue loendi esimeseks elemendiks.
• Koguge ülejäänud loend kuhjaga.
• Ekstraheerige uue hunniku esimene element ja asetage see uue loendi järgmiseks elemendiks.
• Korrake eelmisi samme järjekorras, kuni hunniku loend on tühi. Lõpuks sorteeritakse uus loend.

Korralik kuhjade sortimise aja keerukus

Üheastmelist lähenemist kasutatakse hunnikusordi ajalise keerukuse määramiseks. Oletame, et sortimiseks on 8 sortimata elementi.

Võimalik maksimaalne toimingute arv on:

Nende toimingute arvu keskmine on:

Pange tähele, et eelmise elemendi neli viimast hunnikut esimese elemendi eemaldamisel ei muutunud. Mõned varasemad kuhjad ei muutunud ka esimese elemendi eemaldamisel. Sellega on parem keskmine põhitoimingute (vahetuste) arv 3, mitte 4,5. Seega on põhitoimingute parem keskmine koguarv:

alates log _kaks 8 = 3.

Üldiselt on hunniku sortimise juhtumite keskmine keerukus järgmine:

Kui punkt tähendab korrutamist ja n on N, siis loendi (ükskõik millise loendi) elementide koguarv.

Pange tähele, et esimese elemendi väljavõtmist on ignoreeritud. Aja keerukuse teemal ignoreeritakse operatsioone, mis võtavad suhteliselt lühikest aega.

Kodeerimine C++ keeles

C++ algoritmide teegis on funktsioon make_heap(). Süntaks on:

Selle esimeseks argumendiks on iteraator, mis osutab vektori esimesele elemendile, ja seejärel viimaseks argumendiks iteraator, mis osutab vektori lõpust veidi kaugemale. Eelmise sortimata loendi puhul kasutataks minimaalse kuhja saamiseks süntaksit järgmiselt:

See kood muudab vektori sisu minimaalseks hunniku konfiguratsiooniks. Järgmistes C++ vektorites kasutatakse kahe massiivi asemel kahte vektorit.

Vektori esimese elemendi kopeerimiseks ja tagastamiseks kasutage vektori süntaksit:

Vektori esimese elemendi eemaldamiseks ja äraviskamiseks kasutage vektori süntaksit:

Elemendi lisamiseks vektori taha (järgmine element), kasutage vektori süntaksit:

Programmi algus on:

Algoritm ja vektoriteekid on kaasatud. Järgmine programmis on funktsioon heapsort(), mis on:

See on rekursiivne funktsioon. See kasutab C++ algoritmi teegi funktsiooni make_heap(). Funktsiooni definitsiooni teine ​​koodisegment eraldab esimese elemendi vanast vektorist pärast kuhjahoonet ja lisab uue vektori järgmise elemendina. Pange tähele, et funktsiooni definitsioonis on vektori parameetrid viited, samas kui funktsiooni kutsutakse välja identifikaatorite (nimedega).

Selle jaoks sobiv C++ põhifunktsioon on:

Väljund on:

sorteeritud (täielikult).

Järeldus

Artiklis käsitleti üksikasjalikult Heap Sorti kui sortimisalgoritmi olemust ja funktsiooni. Heapify Time Complexity, Heapsort illustratsioon ja Heapsort kui algoritm olid kaetud ja toetatud näidetega. Hästi kirjutatud hunnikusorteerimisprogrammi keskmine ajaline keerukus on O(nlog(n))