Krūvos rikiavimo algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Algoritmas
Tipas	Rikiavimo algoritmai
Pavadinimas	Krūvos (HeapSort)
Sudėtingumas	Vidutinis - Nlog(N); blogiausias - Nlog(N)
Greitos nuorodos	Algoritmai Rikiavimo algoritmai Krūvos Šablonas

Krūvos rikiavimo algoritmas (angl. heapsort) - rikiavimo algoritmas, kai rikiuojama duomenis sukeliant į krūvos (piramidinę) struktūrą.

[taisyti] Apibendrintas algoritmas

Sudaroma Krūvos duomenų struktūra
Iteraciškai iš sudarytos krūvos pašalinamos šaknys. Jas išsaugome mum reikiama tvarka: pvz., realizuojant masyvu, galime ją įrašyti į masyvo gale atsilaisvinusią vietą (pašalinus šaknį ji yra pakeičiama mažiausiu krūvos lapu).

Gauta šaknų seka yra surikiuota.

[taisyti] Krūvos sudarymas

Tarkim, turime duomenų masyvą

{a₁, a₂, ..., a_n}.

Pirmiausia sukeiskime jo elementus vietomis, 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.

Pradiniai duomenys

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

Sutvarkyti duomenys

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

Tokia duomenų struktūra vadinama Krūva. Pirma algoritmo dalis būtent ir buvo krūvos sudarymas.

Antroji algoritmo dalis yra pats rikiavimas. Eilinėje iteracijoje imama krūvos viršūnė ir sukeičiama vietomis su paskutiniu masyvo elementu. Kadangi krūvos viršūnėje visada bus didžiausias 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 krūvą. Tai padaryti 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 krūvą. 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.

Krūvos aukštis gali būti rastas formule $\lceil \log_2 {n +1} \rceil$ .

[taisyti] Algoritmo savybės

Šis rikiavimo 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 atkuriama krūva. Atkuriant krūvą, elementą blogiausiu atveju gali tekti perkelti iš viršūnės į apatinį lygį, o, kaip minėta, medžio lygių skaičius randamas $\lceil \log_2 {n +1} \rceil$ (arba [log₂n +1], jei tartume kad viršūnė yra 0 lygyje). Taigi antroji lemiama algoritmo dalis yra O(nlog(n)) sudėtingumo. Būtent tokio sudėtingumo ir yra algoritmas. Joks rikiavimo algoritmas, naudojantis palyginimus, negali turėti mažesnio sudėtingumo, tačiau bendru atveju už jį greitesnis yra greitasis rikiavimo algoritmas. Priešingai nei rikiavimo suliejimu, kurio sudėtingumas taip pat toks pats, šiam metodui nereikia papildomos atminties.

Rikiavimo medis gali būti naudojamas kaip prioritetų eilė.

[taisyti] Pavyzdžiai

Algoritmo realizacija Java kalba

public class Pavyzdys {

...

        private int[] duomenys;
        private final int ilgis;
...
        private void perstatyti(int i, int j) {
                if (i <= j/2) {
                        int k1 = 2 * i;
                        int k2 = 2 * i + 1;
                        if (k2 > j) {
                                k2 = k1;
                        }
                        int k;
                        if ( duomenys[k1-1] > duomenys[k2-1] ){
                                k = k1;
                        }
                        else {
                                k = k2;
                        }
                        if (duomenys[i-1] < duomenys[k-1]) {
                                int laikinas = duomenys[i-1];
                                duomenys[i-1] = duomenys[k-1];
                                duomenys[k-1] = laikinas;
                                perstatyti(k, j);
                        }
                }
        }
        
        private void sudarytiRusiavimoMedi() {
                for (int i=ilgis/2;i>=1;i--) {
                        perstatyti(i,ilgis);
                }
        }
        
        private void rusiuotiKruvosMetodu() {
                sudarytiRusiavimoMedi();
                for (int i=ilgis;i>=2;i--) {
                        int laikinas = duomenys[0];
                        duomenys[0] = duomenys[i-1];
                        duomenys[i-1] = laikinas;
                        perstatyti(1,i-1);
                }       
        }

...

}