Krūvos rikiavimo algoritmas

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



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.

Krūvos sudarymas 
Tarkim, turime duomenų masyvą:
 
Pirmiausia sukeiskime jo elementus vietomis, kad gautume:
  kur  ir 

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 . Masyvo elementų skaičius . Pradėsime nuo pradinio elemento .

Elementų perkėlimas bus vykdomas taip:

 6 4 8 7 3 9 1 2
       ^       ^

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

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

 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 . Š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 didžiausias 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 .

Krūvos aukštis gali būti rastas formule .

Algoritmo savybės 

Šis rikiavimo algoritmas nėra stabilus. Pirmoje algoritmo dalyje nereikės atlikti daugiau nei  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  (arba , jei tartume kad viršūnė yra  lygyje). Taigi antroji lemiama algoritmo dalis yra  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ė.

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);
		}
	}

...

}

Nuorodos 
 http://www2.hawaii.edu/~copley/665/HSApplet.html  (spauskite mygtuką iš dešinės)
 http://www.sig.lt/linas/teaching/ad2005/dw/lib/exe/fetch.php?cache=cache&media=lectures%3A5_1p.pdf
 Heapsort code

Rikiavimo algoritmai