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.

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

• 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

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.
  

• 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

  
  

HVALA ZA VAŠO POZORNOST IN LEP DAN ŠE NAPREJ