Kopica

Kopico uvrščamo med levo poravnane in hkrati urejene drevesne podatkovne strukture.
Urejenost se nanaša na vozlišča, saj le ta vsebujejo elemente razporejene po "razmerju" oče: sin. Pri maksimalni kopici zahteva urejenost, da je oče trenutnega vozlišča večji (ali enak) od le tega ter sta hkrati sinova trenutnega vozlišča manjša (ali enaka) od le tega. Za minimalno kopico velja podobno.

Prikaz razmerja OČE:SIN

Levo poravnano drevo oziroma levo zapolnjeno drevo je drevo, v katerega elemente vstavljamo od leve proti desni ter hkrati ne moremo začeti zapolnjevati nekega sloja, če prejšnji sloj še ni zapolnjen.

Levo poravnano drevo

Glede na urejenost ločimo maksimalno in minimalno kopico.
Tudi levo poravnano drevo s samimi enakimi elementi je kopica.

Maksimalna in minimalna kopica

Trije primeri kopic

Primeri dreves, ki ne predstavljajo kopic

Primeri dreves, ki ne predstavljajo kopice

Zgornji primeri ne predstavljajo kopice, ker drevesa niso levo poravnana.

• Višina kopice:
  
• Število listov:
  Primer:
  
  
  
  

Kopica

• Zahteva pri maksimalni kopici:
  Element, ki ga hranimo v vozlišču očeta, ni manjši od elementa, ki ga hranimo pri sinovih:
  Podatek(oče) ≥ Podatek(otrok).
  

• Posledici zahteve:

  • Največji element se nahaja v korenu kopice.
    
  • Poddrevesi maksimalne kopice prav tako predstavljata maksimalno kopico.
    

Maksimalna kopica

Minimalna kopica

• Zahteva pri minimalni kopici:
  Element, ki ga hranimo v vozlišču očeta, ni večji od elementa, ki ga hranimo pri sinovih:
  Podatek(oče) ≤ Podatek(otrok).
  

• Posledici zahteve:

  • Najmanjši element se nahaja v korenu kopice.
    
  • Poddrevesi minimalne kopice prav tako predstavljata minimalno kopico.
    

Minimalna kopica

Kopico zelo pogosto predstavljamo s tabelo. Predstavitev kopice s tabelo je učinkovita predvsem pri operaciji urejanja, vendar se kljub temu uporablja pri predstavitvi vseh operacij, kar bomo videli tudi v nadaljevanju. Predstavitev kopice s tabelo pa je tudi preglednejša v primeru velike količine podatkov.
Če želimo kopico predstaviti s pomočjo tabele, upoštevamo naslednja pravila:

• Koren oz. oče je prvi element tabele (ničto mesto v tabeli zanemarimo).
  
• Če je vozlišče na i-tem mestu, je njegov levi sin na mestu 2i, desni pa na mestu 2i+1.
  
• Vozlišče na i-tem mestu ima torej svojega očeta na mestu i/2. Uporabimo celoštevilsko deljenje.
  

Oblikovanje kopice iz tabele

Primer urejenosti elementov v tabeli

• Poglejmo si element z indeksom 3, ki ima vrednost 14.
  

  • Levi sin: 2i = 2*3 = 6 (vrednost 9)
    
  • Desni sin: 2i+1 = 2*3+1 = 7 (vrednost 7)
    
  • Oče: i2 = 32 = 1 (vrednost 20)
    
    

• Poglejmo si element z indeksom 4, ki ima vrednost 12.
  

  • Levi sin: 2i = 2*4 = 8 (vrednost 5)
    
  • Desni sin: 2i+1 = 2*4+1 = 9 (ne obstaja)
    
  • Oče: i2 = 42 = 2 (vrednost 17)
    

Pri kazalčni porazdelitvi vozlišča drevesa predstavimo s strukturo, kjer poleg podatka hranimo še kazalce (reference) na vozlišča, kjer hranimo očeta in sinova.
Možnosti, kaj torej hranimo v posameznih vozliščih, so:

• Podatek, kazalec na očeta
  
• Podatek, kazalec na levega in desnega sina
  
• Podatek, kazalec na očeta, kazalec na levega in desnega sina.
  

Pri kazalčni predstavitvi kopice je smiselno v posameznih vozliščih hraniti podatek, kazalec na očeta, kazalec na levega in desnega sina. Torej vozlišče izgleda tako kot ga prikazuje spodnja slika.

Izgled vozlišča v kazalčni predstavitvi kopice

Oblikovanje kopice

• Od narave problema je odvisno, kateri postopek bomo uporabili.
  
  
• Od tukaj naprej bo v vseh primerih uporabljena maksimalna kopica. Na podoben način naredimo vse tudi za minimalno kopico.
  

Osnovna operacija je vstavljanje novega element v tekočo, do sedaj zgrajeno kopico.

• Postopek:
  

  • element najprej vstavimo na n-to mesto (v list drevesa);
    
  • pustimo, da se element, ki smo ga vstavili v kopico, dvigne po kopici navzgor dokler novo nastalo drevo ne ustreza urejenosti kopice (torej, da je vstavljeni element manjši ali enak očetu ter hkrati večji ali enak sinovom);
    
  • to drevo je ponovno urejena kopica.
    

• PRIMER:
  Enega za drugim dobivamo naslednje elemente: 5, 10, 4, 20, 18, 14. Iz dobljenih elementov hočemo sestaviti (oblikovati) kopico z zaporednim vstavljanjem elementov v kopico.
  

1. Korak: Na začetku vzamemo prva dva elementa in tvorimo kopico.

• Potek vseh naslednjih korakov: Na vsakem koraku dodamo nov element in ga sproti preverjamo, da je urejen po pravilu kopice.
  

2. Korak

3. Korak

Primer obravnavamo na enakih podatkih kot prejšnjega in sicer vhodni elementi so 5, 10, 4, 20, 18, 14. Vsak korak bomo podčrtali element, ki je v tekočem koraku vstavljen v kopico.

Sestavljanje kopice v vektorju

• PREDNOST: Zaradi poznavanja elementov, ki jih želimo vstaviti, nam ni treba na vsakem koraku (ob vskame vstavljanju) pregledati podatkov, ki tvorijo trenutno kopico. Dovolj bo le, da kopico dobimo na koncu.
  
  
• Imamo tabelo števil, katera ni nujno da zadošča lastnostim kopice.
  
• Števila bi radi uredili tako, da prvo mesto v tabeli predstavlja koren kopice.
  

• Postopek:
  

  • Začnemo pri vseh poddrevesih in jih uredimo v kopico, vse dokler tega ne storimo tudi za korenski element --> začnemo pri najnižjih nivojih in spajamo kopice.
    

• PRIMER:
  Imamo naslednjo tabelo:
  
  

  Začetna tabela

  
  Prvo poddrevo, ki ga moramo pregledati, je označeno z zeleno. Vidimo, da je vrednost korena 20 in ima samo enega otroka z vrednostjo 3. Ker je 20 večje od 3, drevo zadošča lastnostim kopice.
  
  

  Prvi korak

Naslednje drevo, ki ga pregledamo je označeno z oranžno. To drevo ima v korenu vrednost 10 ter dva otroka z vrednostma 25 in 13. Ker vidimo, da je vrednost korena manjša od vrednosti otrok, premaknemo vrednost korena v smeri večjega otroka (zamenjamo 25 in 10).

Drugi korak - ni še urejenosti po pravilu kopice

Drugi korak

Postopek ponovimo za drevo s korenom 15. Ker je drevo že kopica (je koren večji od svojih sinov), ni premikanja.

Tretji korak

Naslednje poddrevo je poddrevo s korenom 8. Njegova sinova sta 25 in 20. Ker vidimo, da je vrednost korena manjša od vrednosti otrok, premaknemo vrednost korena v smeri večjega otroka (zamenjamo 25 in 8).

Četri korak - ni še urejenosti po pravilu kopice

Četri korak - delna urjeneost po pravilu kopice

S tem se spremeni še oranžno poddrevo, ki ima sedaj v korenu vrednost 8. Vidimo, da je vrednost korena manjša od vrednosti otrok, premaknemo vrednost korena v smeri večjega otroka (zamenjamo 13 in 8).

Četri korak

Na koncu ostane drevo s korenom 30, ki ima za otroka 25 in 15 (na sliki označeno z rumeno). To drevo že ustreza lastnostim kopice, zato ni premikanja.

Končna kopica

Združi dve kopici in vozlišče tako, da znova dobimo kopico.

• Pogoj:
  

  • leva kopica mora biti polna,
    
  • desna kopica mora biti levo poravnana,
    
  • obe kopici morata imeti enako višino.
    

• Postopek:
  

  • tvori drevo z elementom x[i] kot korenom, ki ima poddrevesi drevesi s korenom 2*i+1 in 2*i+2
    

  • ponavljaj
    

    • če vrednost korena ne zadošča prvi lastnosti kopice, "premakni" vrednost korena v smeri večjega od otrok
      
    • premikanje zaključimo, če je izpolnjena prva lastnost kopice, katera se nanaša na urejenost. Premikanje kopice torej zaključimo, ko je oče vozlišča večji (ali enak) od trenutnega vozlišča ter sta hkrati sinova opazovanega vozlišča manjša (ali enaka) od njega oziroma sta njegova sinova prazni drevesi.
      

Z vozliščem s podatkom 5 želimo združiti naslednji kopici:

Začetni kopici

Oranžno in rumeno obarvana polja že sama zase predstavljajo kopico oziroma ustrezajo lastnostim kopice (19 je večje od obeh otrok in sicer od 1 in od 13 ter 12 je večje od otroka 3).

Izpolnjena je tudi druga lastnost kopice, da so vsa poddrevesa tudi kopice.

Iz zgornjih dveh kopic in dodatnega vozlišča sestavimo tabelo oziroma oblikujemo kopico:

Prvi korak

Obe kopici želimo povezati z elementom 5, ki je rdeče obarvan. Končno dobljeno drevo mora ustrezati pogoju, da bo drevo s korenom v rdeče obarvanem elementu zadoščalo lastnostim kopice (rumeno drevo je levo poddrevo, oranžno drevo je desno poddrevo).

Ker je 5 manjše od elementa v levem otroku torej 19 in manjše od elementa v desnem otroku torej 12, pravilo kopice ni izpolnjeno.
Po postopku spajanja kopice je potrebno število 5 premakniti v smeri večjega otroka. Na podlagi tega zamenjamo števili 5 in 19.

Drugi korak

Opazujemo drevo, ki ima v korenu element 5 (rumeno drevo).

Ker je element v korenu 5 manjši od elementa v desnem otroku (13), zamenjamo elementa 5 in 13.

Tretji korak

Drevo s korenom 5 nima otrok, zato zadošča vsem lastnostnim kopice in postopek zaključimo.

Če je v tabeli shranjena kopica, to pomeni, da je največji element polja na prvem mestu v tabeli. To dejstvo lahko s pridom izkoristimo za urejanje števil v tabeli.

• Postopek:
  

  • Če tabela ne predstavlja kopice, nad poljem izvedemo postopek Zgradi kopico.
    

  • Za vse elemente polja, ki ne predstavljajo listov, ponavljaj:
    

    • Zamenjaj prvi (največji) element polja z zadnjim elementom.
      
    • "Zmanjšaj" velikost kopice za en element.
      
    • Ker smo prvi element premaknili z zadnjega mesta, iz "zmanjšane" tabele zgradimo kopico. V bistvu smo z "odstranitvijo" prvega elementa kopico razbili na dve podkopici. Ti dve kopici nato skupaj spojimo v novo kopico z elementom, ki je ta največji (odstranjen) element zamenjal.
      

Uporabili bomo končno tabelo, katero smo s postopkom Zgradi kopico dobili v prejšnjem poglavju. Velikost kopice bomo označevali z zeleno barvo. Ostale elemente, ki ne spadajo več v kopico, bomo označevali z rdečo barvo.

Začetna tabela oziroma kopica

V prvem koraku zamenjamo prvi element z zadnjim elementom in spojimo element 3 s kopicama s koreni 25 in 15.

Prvi korak

Preostale elemente (brez elementa 30) ponovno uredimo po lastnostih kopice.

Prikaz potapljanja elementa od korena navzdol po kopici

Tabela po prvem koraku

V vseh naslednjih korakih prvi element zamenjamo z zadnjim elementov. Tabele, ki jih dobimo po vsakem koraku, še uredimo po lastnostih kopice.

Drugi korak

Vmesni koraki potekajo na enak način.

Deveti in deseti korak ter končna tabela

• Postopek:
  
  

  • Element dodamo na prvo prosto mesto.
    
  • Nato ga premikamo navzgor po kopici, če je vrednost elementa v staršu manjša.
    
    
• Postopek ponavljamo, dokler ne pridemo do korena ali pa je vrednost v staršu elementa večja kot tista v elementu, ki ga vstavljamo. Premikanje navzgor pomeni zamenjavo vrednosti, ki ju gledamo, torej zamenjavo otroka s staršem.
  

• Primer: V spodnjo kopico želimo vstaviti element 17.
  
  

Vstavljanje elementa v kopico

• Primer: Vstavljanje elementa 17 v kopico s pomočjo tabele.
  
  

Vstavljanje elementa v kopico s pomočjo tabele

Novo nastala kopica je povečana za en element glede na začetno kopico. Za vsak element, ki ga želimo vstaviti v kopico, postopek ponovimo.

Da iz kopice odstranimo največji element (koren) si pomagamo s postopkom pod naslovom: Postopek uredi s kopico.

Začetna kopica

1. KORAK

• Omogoča hiter dostop do največjega oziroma najmanjšega elementa.
  
  
• Zagotavlja ugodne logaritemske časovne zahtevnosti za večino ostalih operacij.
  
  
• Uporablja se tudi pri implementaciji podatkovne strukture prednostna vrsta in pri algoritmu za urejanje z izboljšanim izbiranjem (angleško HeapSort).
  
  
• Uporaba na področju ekonomičnega vzdrževanja podatkov, urejenih po velikosti, na primer v operacijskih sistemih in prevajalnikih.
  

Katere lastnosti so značilne za podatkovno strukturo kopica?

Preveri

Zaporedoma dobivamo naslednje elemente: 13,2,20,10,1,9. Katera od spodnjih slik predstavlja kopico sestavljeno iz zgornjih elementov?

V spodnjo kopico vstavimo element (10). Katera od možnih kopic predstavlja novo kopico (stara z vstavljenim elementom)?

Katero od spodnjih operacij ne izvajamo na kopici?

• Opis kopice na MaFiRaWiki-ju
• Opis kopice na wiki-ju
• Podatkovna struktura kopica
• Seminarska naloga Kopica
• Seminarska naloga Kopica 2009
• Jernej Kozak: Podatkovne strukture in algoritmi, DMFA, Ljubljana 1986.
• Igor Kononenko, Marko Robnik Šikonja: Algoritmi in podatkovne strukture I, založba FE in FRI, Ljubljana 2003.