Kopica

Iz MaFiRaWiki

Vsebina


Kopica je dvojiško drevo, z vozlišči, ki so označena z elementi neke linearne urejenosti in ki ima naslednji lastnosti:

  • element v korenu je večji od elementov v njegovih sinovih,
  • obe poddrevesi korena sta kopici.

Tako definirano kopico imenujemo maksimalna kopica. Če zahtevamo, da je koren manjši od obeh sinov, dobimo minimalno kopico. Zgled kopice:

Predstavitev s tabelo

Kopico lahko implementiramo s katerokoli implementacijo dvojiških dreves. Pogosto se obnese predstavitev kopice s tabelo, na primer pri urejanju s kopico. Pri tej predstavitvi so elementi kopice shranjeni v tabeli po naslednjem pravilu:

  • koren je prvi element tabele,
  • če je vozlišče na n-tem mesu, sta njegov levi in desni sin na 2n-tem in 2n + 1-tem mestu,
  • sledi, da ima vozlišče na n-tem mestu svojega očeta na n / 2-tem mestu, pri čemer uporabimo celoštevilsko deljenje.

Na primer, zgornjo kopico predstavimo s tabelo

10, 8, 7, 7, 6, 2, 3, ?, ?, ?, ?, ?, ?, 1, 0

Pri tem smo z znakom ? označili mesta v tabeli, ki ne predstavljajo nobenega vozlišča. Da bi se izgonili neuporabljenim elementom v tabeli, ki predstavlja kopico, običajno zahtevamo, da je ta levo poravnano drevo.

Zgled levo poravnane kopice in njena predstavitev s tabelo:

Algoritem Sestavi Kopico

Problem sestavi kopico lahko rešimo z dvema različnima algoritmoma, ki imata različni časovni zahtevnosti:

  1. Dobivamo element za elementom in vsakega posebej vnašamo v kopico
  2. Tabelo z znanimi elementi preoblikujemo v kopico

Podatke zaporedoma vnašamo v kopico O(n log n)

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 podprograma vstavi. Časovna zahtevnost O(n * logn)

Algoritem vstavi

  • algoritem vstavi, ki vstavi nov element v kopico, ki že ima n elementov. Časovna zahtevnost O(log n).

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 je število elementov, ki jih vstavljamo v kopico.
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);
}

  • algoritem, ki že pozna vse elemente in jih zgradi v kopico
tabela[]; //dobimo tabelo, n je število elementov v tabeli
for(oce = n/2; oce >=1 ; oce--){ //prvi kandidat za očeta je srednji element, elementi v  desni polovici tabele nimajo
                                   naslednikov, pregleda vse elemente, od sredine do začetka tabele, potaplja
 vstavi(tabela, n, oče); //potapljamo


Primer

Iz elementov Slika:kop1.jpg hočemo narediti kopico.
Na začetku vzamemo prva dva elementa, potem pa na vsakem koraku dodamo nov element in sproti gledamo, da je oče vedno večji od sinov.

Slika:kop11.jpg

Končna rešitev:

Slika:kop1Reš.jpg

Dobimo vse podatke naenkrat O(n)

Vse elemente vidimo naenkrat, kar lahko izkoristimo za učinkovitejše vstavljanje. Ker vnaprej vemo, katere elemente bomo vstavili, nam ni treba na vsakem koraku, pri vsakem vstavljanju elementa vztrajati, da že pregledani podatki tvorijo kopico. Dovolj bo le, da kopico dobimo na koncu.
Na tekočem koraku izberemo nov, še ne pregledan element in dve že sestavljeni kopici ter tvorimo novo kopico. S tem na vsakem koraku število dreves zmanjšamo za eno, tako da nam na koncu preostane le ena kopica. Tekoči element je edini element, ki ne zadošča zahtevam kopice. Vstavimo ga v koren in spustimo v globino tako globoko, kot je potrebno. Urejenost ohranjamo tako, da ga zamenjamo vedno z večjim sinom.

Isti primer še enkrat

Imamo dva primera.

  • spoji dve kopici v novo, večjo kopico

Slika:Kop2.jpg

Slika:kop22.jpg

Slika:kop23.jpg

Slika:kop24.jpg

  • zgradi kopico v celoti
    Podano imamo tabelo elementov:
[ 10, 21, 17, 98, 17, 27, 41, 1, 9 ]
  • Iz teh elementov hočemo sestaviti kopico.
  • n = 9
    (n + 1)/2 je listov (torej 5), ki so že kopice.
    Prvi oče nove kopice je na mestu z indeksom n/2, torej na mestu 9/2 = 4.
    Njegov levi sin je na mestu z indeksom 2*4 = 8.
    Njegov desni sin je na mestu z indeksom 2*4 + 1 = 9.
    Slika:kop3.jpg
  • n = 7
    (n + 1)/2 je listov (torej 4), ki so že kopice.
    Oče nove kopice je na mestu z indeksom n/2, torej na mestu 7/2 = 3.
    Njegov levi sin je na mestu z indeksom 2*3 = 6.
    Njegov desni sin je na mestu z indeksom 2*3 + 1 = 7.
    Slika:kop32.jpg
  • n = 5
    (n + 1)/2 je listov (torej 3), ki so že kopice.
    Oče nove kopice je na mestu z indeksom n/2, torej na mestu 5/2 = 2.
    Njegov levi sin je na mestu z indeksom 2*2 = 4.
    Njegov desni sin je na mestu z indeksom 2*2 + 1 = 5.
    Slika:kop33.jpg
  • n = 3
    (n + 1)/2 je listov (torej 2), ki so že kopice.
    Oče nove kopice je na mestu z indeksom n/2, torej na mestu 3/2 = 1.
    Njegov levi sin je na mestu z indeksom 2*1 = 2.
    Njegov desni sin je na mestu z indeksom 2*1 + 1 = 3.
    Slika:kop34.jpg
  • Končna kopica je:
[ 98, 21, 41, 10, 17, 27, 17, 1, 9 ]

Algoritem Briši maksimalni element O(log n)

Najlepša lastnost kopice je, da ima na prvem mestu maksimalni element. Velikokrat ga vzamemo iz kopice. Toda s tem pokvarimo kopico. Popravimo jo tako, da vzamemo zadnji element v tabeli in ga prestavimo na prvo mesto, kjer manjka odvzeti element. Potem po že znanem postopku ta element potopimo.

Primer

Kopica na začetku:

[88, 39, 24, 31, 10, 17, 10, 5, 7]


Slika:max.jpg

Kopica na koncu:

[39, 31, 24, 7, 10, 17, 10, 5]

Uporaba kopic

  • Kopico uporabljamo za učinkovito implementacijo podatkovne strukture vrsta s prednostjo.
  • Druga, nič manj pomembna uporaba pa je pri učinkovitem postopku za urejanje tabele, ki je znana pod imenom urejanje s kopico.

Glej tudi

Osebna orodja