„Heapsort“ laiko sudėtingumas

Krūva vadinama „iš dalies sutvarkyta“, o ne „iš dalies surūšiuota“. Žodis „rūšiuoti“ reiškia visišką užsakymą (visą rūšiavimą). Krūva nėra iš dalies užsakyta savavališkai. Krūva yra iš dalies sutvarkyta pagal kriterijų (schemą), kaip parodyta toliau.

Taigi, kaupų rūšiavimas susideda iš dviejų etapų: krūvos sukūrimas ir užsakyto elemento ištraukimas iš krūvos viršaus. Antrame etape po kiekvieno ištraukimo krūva atkuriama. Kiekvienas atstatymas yra greitesnis nei pradinis kūrimo procesas, nes atstatymas atliekamas iš ankstesnės konstrukcijos, kai buvo pašalintas vienas elementas. Be to, heapsort surūšiuoja visiškai nerūšiuotą sąrašą.

Šio straipsnio tikslas yra trumpai paaiškinti krūvos rūšiavimą ir tada pateikti jo laiko sudėtingumą (žr. laiko sudėtingumo reikšmę žemiau). Pabaigoje kodavimas atliekamas C++.

Minimali krūva

Krūva gali būti minimali arba didžiausia krūva. Maksimali krūva yra tokia, kurios pirmasis elementas yra aukščiausias elementas, o visas medis arba atitinkamas sąrašas iš dalies išdėstytas mažėjančia tvarka. Min-heap yra toks, kuriame pirmasis elementas yra mažiausiai elementų, o visas sąrašas iš dalies išdėstytas didėjančia tvarka. Šiame straipsnyje atsižvelgiama tik į mažiausią krūvą. Pastaba: krūvos temoje elementas dar vadinamas mazgu.

Krūva yra pilnas dvejetainis medis. Dvejetainis medis gali būti išreikštas kaip masyvas (sąrašas); skaityti iš viršaus į apačią ir iš kairės į dešinę. Minimalios krūvos krūvos savybė yra ta, kad pirminis mazgas yra mažesnis arba lygus kiekvienam iš dviejų antrinių. Netvarkingo sąrašo pavyzdys:

Pirmoje šios lentelės eilutėje yra masyvo elementai. Antroje eilutėje yra nuliniai indeksai. Šį elementų sąrašą galima išreikšti medžiu. Nuliniai elementai buvo pridėti, kad būtų sukurtas pilnas dvejetainis medis. Griežtai kalbant, nuliniai elementai nėra sąrašo (medžio) dalis. Šiame sąraše nėra tvarkos, todėl jis dar nėra krūva. Jis taps krūva, kai bus atliktas dalinis užsakymas, atsižvelgiant į krūvos savybę.

Ryšys tarp mazgų ir indeksų

Atminkite, kad krūva yra pilnas dvejetainis medis prieš turint krūvos konfigūraciją (krūvos savybę). Ankstesnis sąrašas dar nėra krūva, nes elementai nepaklūsta krūvos savybei. Pertvarkius elementus į dalinę tvarką pagal min-heap savybę, jis tampa krūva. Dalinė tvarka gali būti vertinama kaip dalinis rūšiavimas (nors žodis „rūšiuoti“ reiškia visišką tvarką).

Nesvarbu, ar dvejetainis medis yra krūva, ar ne, kiekvienas iš tėvų turi du vaikus, išskyrus lapų (paskutinį) mazgus. Tarp kiekvieno iš tėvų ir jo vaikų yra matematinis ryšys tarp indeksų. Tai yra taip: Jei tėvas yra indekse i, tada kairysis vaikas yra indekse:

ir tinkamas vaikas yra indekse:

Tai skirta nuliniam indeksavimui. Taigi, tėvo, kurio indeksas 0, kairiojo vaiko indeksas yra 2 × 0 + 1 = 1, o dešiniojo - 2 × 0 + 2 = 2. Vienas iš tėvų, kurio indeksas 1, turi kairiojo vaiko indeksą 2×1+1=3, o dešinįjį – 2×1+2=4; ir taip toliau.

Pagal minimalios krūvos ypatybę vienas iš tėvų, esantis i, yra mažesnis arba lygus kairiajam vaikui, esant 2i+1, ir mažesnis už arba lygus dešiniajam vaikui, esantis 2i+2.

Krūva

Sukrauti krūvą reiškia kaupti krūvą. Tai reiškia, kad sąrašo (arba atitinkamo medžio) elementus reikia pertvarkyti taip, kad jie atitiktų krūvos savybę. Krūvos formavimo proceso pabaigoje sąrašas arba medis yra krūva.

Jei ankstesnis nerūšiuotas sąrašas bus sukrautas, jis taps:

Pastaba: sąraše yra 12 elementų, o ne 15. Antroje eilutėje yra indeksai. Krūvos kūrimo procese reikėjo patikrinti elementus, o kai kuriuos pakeisti.

Atkreipkite dėmesį, kad mažiausias ir pirmasis elementas yra 3. Likę elementai seka didėjančia, bet banguota tvarka. Jei kairysis ir dešinysis vaikai, esantys 2i+1 ir 2i+2 padėtyse, yra didesni arba lygūs tėvui taške i, tai yra min krūva. Tai nėra pilnas užsakymas ar rūšiavimas. Tai yra dalinis užsakymas, atsižvelgiant į krūvos savybę. Būtent nuo čia prasideda kitas krūvos rūšiavimo etapas.

Padidinkite laiko sudėtingumą

Laiko sudėtingumas yra santykinis tam tikro kodo veikimo laikas. Jis gali būti vertinamas kaip pagrindinių operacijų, skirtų tam kodui užbaigti, skaičius. Yra skirtingi krūvos kūrimo algoritmai. Veiksmingiausi ir greičiausi nuolat padalija sąrašą iš dviejų, tikrindami elementus iš apačios, o tada keisdami elementus. Tegul N yra praktinių elementų skaičius sąraše. Taikant šį algoritmą, didžiausias pagrindinių operacijų (sukeitimo) skaičius yra N. Laiko sudėtingumas kaupimui anksčiau buvo nurodytas kaip:

Kur n yra N ir yra didžiausias galimas pagrindinių operacijų skaičius. Šis žymėjimas vadinamas Big-O žymėjimu. Jis prasideda didžiosiomis raidėmis O, po kurių rašomi skliausteliai. Skliausteliuose yra galimo didžiausio operacijų skaičiaus išraiška.

Atminkite: sudėjimas gali tapti daugyba, jei tas pats pridedamas dalykas kartojasi.

Heapsort iliustracija

Ankstesnis nerūšiuotas sąrašas bus naudojamas iliustruoti krūvą. Pateiktas sąrašas yra toks:

Minimali krūva, sudaryta iš sąrašo, yra:

Pirmasis krūvos rūšiavimo etapas yra sukurti krūvą, kuri buvo pagaminta. Tai iš dalies sutvarkytas sąrašas. Tai nėra surūšiuotas (visiškai surūšiuotas) sąrašas.

Antrasis etapas susideda iš mažiausio elemento, kuris yra pirmasis elementas, pašalinimo iš krūvos, likusios krūvos pakartotinio kaupimo ir mažiausiai elementų pašalinimo rezultatuose. Mažiausias elementas visada yra pirmasis elementas pakartotinai sukauptoje krūvoje. Elementai nėra nuimami ir išmetami. Jie gali būti siunčiami į kitą masyvą ta tvarka, kuria jie buvo pašalinti.

Galų gale naujame masyve visi elementai būtų surūšiuoti (visiškai) didėjančia tvarka; ir jau ne tik iš dalies užsakyta.

Antrame etape pirmiausia reikia pašalinti 3 ir įdėti jį į naują masyvą. Rezultatai yra:

ir

Likusieji elementai turi būti sukrauti prieš ištraukiant pirmąjį elementą. Likusių elementų krūva gali tapti:

Ištraukus 5 ir pridėjus prie naujo sąrašo (masyvo), gaunami rezultatai:

ir

Sukaupus likusį rinkinį gautųsi:

Ištraukus 6 ir pridėjus prie naujo sąrašo (masyvo), gaunami rezultatai:

ir

Sukaupus likusį rinkinį gautųsi:

Ištraukus 7 ir įtraukus jį į naują sąrašą, gaunami rezultatai:

ir

Sukaupus likusį rinkinį gaunama:

Ištraukus 9 ir įtraukus į naują sąrašą, gaunami rezultatai:

ir

Sukaupus likusį rinkinį gaunama:

Ištraukus 11 ir įtraukus jį į naują sąrašą, gaunami rezultatai:

ir

Sukaupus likusį rinkinį gautųsi:

Ištraukus 14 ir įtraukus jį į naują sąrašą, gaunami rezultatai:

ir

Sukaupus likusį rinkinį gautųsi:

Ištraukus 15 ir įtraukus juos į naują sąrašą gaunami rezultatai:

ir

Sukaupus likusį rinkinį gautųsi:

Ištraukus 17 ir įtraukus jį į naują sąrašą, gaunami rezultatai:

ir

Sukaupus likusį rinkinį gautųsi:

Ištraukus 19 ir įtraukus jį į naują sąrašą, gaunami rezultatai:

ir

Sukaupus likusį rinkinį gaunama:

Ištraukus 22 ir įtraukus jį į naują sąrašą, gaunami rezultatai:

ir

Sukaupus likusį rinkinį gaunama:

Ištraukus 24 ir įtraukus jį į naują sąrašą, gaunami rezultatai:

ir

Dabar krūvos masyvas tuščias. Visi elementai, kuriuos ji turėjo pradžioje, dabar yra naujame masyve (sąraše) ir surūšiuoti.

Heapsort algoritmas

Nors skaitytojas vadovėliuose galėjo skaityti, kad krūvos rūšiavimas susideda iš dviejų etapų, vis tiek galima žiūrėti, kad rūšiavimas į krūvą susideda iš vieno etapo, kuris kartotiškai sumažina pateiktą masyvą. Tai reiškia, kad rūšiavimo su heapsort algoritmas yra toks:

• Supildykite nerūšiuotą sąrašą.
• Išskleiskite pirmąjį krūvos elementą ir įtraukite jį kaip pirmąjį naujojo sąrašo elementą.
• Supilkite likusį sąrašą.
• Išskleiskite pirmąjį naujos krūvos elementą ir įtraukite kaip kitą naujo sąrašo elementą.
• Kartokite ankstesnius veiksmus eilės tvarka, kol krūvos sąrašas bus tuščias. Galiausiai naujas sąrašas surūšiuojamas.

Tinkamas rūšiavimo laiko sudėtingumas

Vieno etapo metodas naudojamas krūvos rūšiavimo laiko sudėtingumui nustatyti. Tarkime, kad reikia rūšiuoti 8 nerūšiuotus elementus.

Galimas maksimalus operacijų skaičius:

Šių operacijų skaičiaus vidurkis yra:

Atkreipkite dėmesį, kad paskutinės keturios krūvos ankstesnėje iliustracijoje nepasikeitė, kai buvo pašalintas pirmasis elementas. Kai kurios ankstesnės krūvos taip pat nepasikeitė pašalinus pirmąjį elementą. Tokiu atveju geresnis vidutinis pagrindinių operacijų (sukeitimų) skaičius yra 3, o ne 4,5. Taigi geresnis bendras vidutinis pagrindinių operacijų skaičius:

nuo žurnalo _du 8 = 3.

Apskritai, vidutinis krūvos rūšiavimo atvejo sudėtingumas yra toks:

Kai taškas reiškia daugybą, o n yra N, bendras elementų skaičius sąraše (bet kuriame sąraše).

Atminkite, kad pirmojo elemento ištraukimo operacija buvo ignoruojama. Kalbant apie laiko sudėtingumą, operacijos, kurios trunka palyginti trumpai, yra ignoruojamos.

Kodavimas C++

C++ algoritmų bibliotekoje yra funkcija make_heap(). Sintaksė yra tokia:

Pirmuoju argumentu laikomas iteratorius, nukreipiantis į pirmąjį vektoriaus elementą, o po to iteratorius, nukreipiantis tiesiai už vektoriaus galo, kaip paskutinis argumentas. Ankstesniame nerūšiuotame sąraše sintaksė būtų naudojama taip, kad būtų gauta mažiausia krūva:

Šis kodas pakeičia vektorinį turinį į minimalią krūvos konfigūraciją. Tolesniuose C++ vektoriuose vietoj dviejų masyvų bus naudojami du vektoriai.

Norėdami nukopijuoti ir grąžinti pirmąjį vektoriaus elementą, naudokite vektoriaus sintaksę:

Norėdami pašalinti pirmąjį vektoriaus elementą ir jį išmesti, naudokite vektoriaus sintaksę:

Norėdami pridėti elementą vektoriaus gale (kitas elementas), naudokite vektoriaus sintaksę:

Programos pradžia yra tokia:

Algoritmas ir vektorinės bibliotekos yra įtrauktos. Kitas programoje yra heapsort() funkcija, kuri yra:

Tai rekursinė funkcija. Jis naudoja C++ algoritmų bibliotekos funkciją make_heap(). Antrasis funkcijos apibrėžimo kodo segmentas ištraukia pirmąjį elementą iš senojo vektoriaus po krūvos kūrimo ir prideda kaip kitą naujo vektoriaus elementą. Atkreipkite dėmesį, kad funkcijos apibrėžime vektoriaus parametrai yra nuorodos, o funkcija iškviečiama su identifikatoriais (pavadinimais).

Tam tinkama pagrindinė C++ funkcija:

Išvestis yra:

surūšiuota (visiškai).

Išvada

Straipsnyje išsamiai aptartas Heap Sort, paprastai žinomo kaip Heapssort, kaip rūšiavimo algoritmo, pobūdis ir funkcija. „Heapify Time Complexity“, „Heapsort“ iliustracija ir „Heapsort“ kaip algoritmas buvo aprašyti ir paremti pavyzdžiais. Vidutinis gerai parašytos krūvos programos sudėtingumas yra O(nlog(n))