Krūvos rikiavimo algoritmas

Tarkim, turime duomenų masyvą {a₁, a₂, ..., a_n}. Pirmiausia susikurkime tikslą perkelti duomenų elementus taip, kad gautume {a₁', a₂', ..., a_n'), kur a_i' >= a_2i' ir a_i' >= a_2i+1'.

Grafiškai tai atrodys kaip dvejetainis medis, kurio kiekvienos viršūnės sūnūs yra ne didesni už tėvus. Tarkime, turime pradinius duomenis {6, 4, 8, 7, 3, 9, 1, 2}. Masyvo elementų skaičius n=9. Pradėsime nuo pradinio elemento i=n/2=4.

Elementų perkėlimas bus vykdomas taip:

i = 4

6 4 8 7 3 9 1 2
      ^       ^

i = 3

6 4 8 7 3 9 1 2
    ^     ^ ^
    |     |
    <-----> 
6 4 9 7 3 8 1 2

i = 2

6 4 9 7 3 8 1 2
  ^   ^ ^
  |   |
  <--->
6 7 9 4 3 8 1 2 

i = 1

6 7 9 4 3 8 1 2
^ ^ ^
|   |
<--->
9 7 6 4 3 8 1 2
    ^     ^ ^
    |     |
    <----->
9 7 8 4 3 6 1 2

Taigi gavome {9, 7, 6, 4, 3, 8, 1, 2}. Šiame masyve jau tenkinama mūsų minėta sąlyga.

Paveiksliukas

Tokia duomenų struktūra vadinama rūšiavimo medžiu. Pirma algoritmo dalis būtent ir buvo rūšiavimo medžio sudarymas.

Antroji algoritmo dalis yra pats rūšiavimas. Eilinėje iteracijoje imama šio medžio viršūnė ir sukeičiama vietomis su paskutiniu masyvo elementu. Kadangi medžio viršūnėje visada bus didžiausias elementas (nes medžio viršūnė yra pirmasis masyvo elementas), tai jį sukeitę vietomis su paskutiniu masyvo elementu, žinosime, kad maksimalus masyvo elementas yra jo paskutinėje pozicijoje. Taip sukeitę elementus vietomis, turime atkurti rūšiavimo medį. Atkurti rūšiavimo medį yra paprasta, nes vietą pakeitęs būna tik vienas elementas (jis atsiduria viršūnėje). Šį elementą, jei jis nėra didžiausias, reikia perstumti keletu lygių žemiau, kol vėl gausime rūšiavimo medį. Tai atlikę, pradedame naująją iteraciją, tik šį kartą jau nagrinėsime vienetu trumpesnį masyvą, nes didžiausias elementas, kuris anksčiau buvo viršūnėje, jau atsidūrė savo vietoje ir jo nagrinėti nereikia. Tokių iteracijų skaičius yra N-2.

Paveiksliukas

Rūšiavimo medžio lygių skaičius gali būti rastas formule log₂n.

Algoritmo savybės

Šis rūšiavimo algoritmas nėra stabilus. Pirmoje algoritmo dalyje nereikės atlikti daugiau nei 2n-4 palyginimų, taigi pirmosios dalies sudėtingumas tiesinis. Antrojoje dalyje pirmasis medžio elementas sukeičiamas su paskutiniu vietomis ir atkuriamas rūšiavimo medis. Atkuriant rūšiavimo medį, elementą blogiausiu atveju gali tekti perkelti iš viršūnės į apatinį lygį, o, kaip minėta, medžio lygių skaičius randamas log₂n. Taigi antroji lemiama algoritmo dalis yra O(nlog(n)) sudėtingumo. Būtent tokio sudėtingumo ir yra algoritmas. Joks rūšiavimo algoritmas, naudojantis palyginimus, negali turėti mažesnio sudėtingumo, tačiau bendru atveju už jį greitesnis yra greitasis rūšiavimo algoritmas. Priešingai nei rūšiavimas suliejimu, kurio sudėtingumas taip pat toks pats, šiam metodui nereikia papildomos atminties.

Rūšiavimo medis gali būti naudojamas kaip prioritetų eilė.

Apibendrintas krūvos rūšiavimo algoritmas

TODO: aprašyti apibendrintą, paveiksliukai, kodas