Izpitno vprašanje RAČ2PRA 13300

Iz MaFiRaWiki

Vprašanje

Opiši urejanje s kopico.


Odgovor

• učinkovito urejanje

• bolj komplicirana zgradba

• primerno za velike tabele

• ne nujno stabilen

KOPICA je dvojiško drevo. Vozliščem pripadajo vrednosti, ki so urejena tako, da vrednost, ki jo hranimo v vozlišču očeta, ni manjša od vrednosti, ki ju hranimo pri sinovih. Čeprav ni vedno pravilo, bomo vseskozi privzeli, da je kopica levo poravnano drevo - lažja predstavitev s tabelo.

Dostop do elementov: Indekse začnemo šteti z 1:

- oče(i) = i/2

- levi sin(i) = 2*i

- desni sin(i) = 2*i + 1

- i... indeks v tabeli


Algoritem sestavi kopico:

Dobivamo element za elementom in vsakega posebej vnašamo v kopico. Ker elementi prihajajo drug za drugim, bo osnovna operacija kar vstavi nov element v tekočo, do sedaj zgrajeno kopico. Element, ki ga vnašamo, bo edini element, ki kvari urejenost. Če ga vstavimo na n-to mesto, torej v list drevesa, in poskrbimo, da splava k vrhu drevesa, tako da je na koncu večji od svojih sinov in manjši od očeta, bo razširjeno drevo tudi kopica. Algoritem sestavi kopico v celoti pa zahteva le dovolj zaporednih klicev osnovnega vstavi.

  algoritem, ki vstavi nov element v kopico 
   vstavi(kopica, n , element){
     kamBomDal = n;
     oce = kamBomDal / 2;
     while (oce > 0) && (kopica[oce] < element){ // proti vrhu	 
        kopica[kamBomDal] = kopica[oce]; // "potopimo" očeta
        kamBomDal = oce;
        oce = oce / 2;
     }
	kopica[kamBomDal] = element;
   }
   algoritem, ki zgradi kopico z zaporednim vstavljanjem 
   n dobi vrednost; //n se poveča za ena, ker dobimo nov element
	           //(n = n + 1)
    kopica[1] = element;  //prvi element
      for(oce = 2; oce <= n; oce++){
    element dobi vrednost; //dobimo nov element, ki ga hočemo vstaviti
      vstavi(kopica, oce, element);
      }
Osebna orodja