RACU N A L NI STVO Podatkovna struktura kopica Andrej Taranenko -» Tokrat bomo predstavili podatkovno strukturo, imenovano kopica. V literaturi se pojavlja vec različnih definicij strukture, ki se skriva pod imenom kopica. V našem prispevku bo kopica dvojiško drevo z zahtevanimi dodatnimi lastnostmi, podrobneje definirana v nadaljevanju. Ponovimo na zacetku nekaj o dvojiških drevesih. iAl (^l (C (D (E © (G H (u © ' s> ' si (m) SLIKA 1. Levo poravnano dvojiško drevo in dvojiško drevo, ki ni levo poravnano. Dvojiško drevo in predstavitev s poljem Dvojiško drevo je podatkovna struktura, ki je bodisi prazna bodisi za vsako vozlišče velja, da ima največ dva otroka. Z besedo vozlišče imamo v mislih strukturo, ki vsebuje vrednost, imenovano ključ, ter dve vozlišči, imenovani levi in desni otrok. Kadar govorimo samo o otrocih, bomo v mislih imeli poljubnega izmed njiju ali oba. Vozlišče v je starš vozlišča u, če je u otrok vozlišča v. V dvojiškem drevesu, ki ni prazno, imamo posebno vozlišče, imenovano koren oz. korensko vozlišče. Korensko vozlišče imamo za prvi nivo drevesa. Njegovi otroči so na drugem nivoju drevesa, njihovi otroči na tretjem itd. Naj bo v vozlišče dvojiškega drevesa. Ce pogledamo drevo, katerega korensko vozlišče je levi otrok vozlišča v, govorimo o levem poddrevesu, drevo, katerega koren je desni otrok vozlišča v, pa je desno poddrevo. Vozlišče drevesa, ki nima otrok, imenujemo list. Na sliki 1 vidimo primera dveh dvojiških dreves. V obeh je vozlišče s ključem A korensko vozlišče. Ce se omejimo na levo drevo na sliki 1, je drevo, ki ga tvorijo vozlišča s ključi C, F in G, desno poddrevo vozlišča s ključem A. Listi drevesa pa so vozlišča s ključi F, G, H, I in J. Drevo ima štiri nivoje. Vozlišče s ključem A je na prvem nivoju drevesa, vozlišči s ključema B in C na drugem nivoju drevesa, na tretjem so vozlišča s ključi D, E, F in G, na zadnjem (četrtem) nivoju pa vozlišča s ključi H, I in J. Za dvojiško drevo, ki je levo poravnano, velja, da ima na vseh nivojih, razen morda zadnjem, vsa možna vozlišča. Na zadnjem nivoju drevesa pa dopuščamo, da na desni strani manjkajo vozlišča. Primer levo poravnanega drevesa vidimo na levi strani slike 1; primer devesa, ki ni levo poravnano, saj med vozliščem J in vozliščem M manjkajo črtkasto narisana vozlišča, pa vidimo na desni strani slike 1. Dvojiško drevo lahko v računalniku med drugim predstavimo s poljem tako, da ključe v vozliščih od zgoraj navzdol in od leve proti desni za povrstjo shranimo v polje. Levo drevo na sliki 1 bi na ta način predstavili s poljem v tabeli 1. Ce ne bi zahtevali, da je drevo levo poravnano, bi pri tej predstavitvi v polju dobili prazna (neizkoriščena) mesta. V tabeli 2 vidimo desno drevo s slike 1 predstavljeno s poljem. 0 1 2 3 4 5 6 7 8 9 vrednost A B C D E F G H I J TABELA1. Predstavitev dvojiškega drevesa s poljem 0 1 234567 8 9 10 11 12 vrednost A B C D E F G H I J M TABELA 2. Dvojiško drevo, ki ni levo poravnano, predstavljeno s poljem. 22 PRESEK 43 (2015/2016) 6 RAČUNALNIŠ TVO Predpostavimo, da so elementi polja indeksirani od 0 naprej. Sami lahko preverite, da ima vozlišče, ki ga v polje shranimo na indeks i, levega otroka shranjenega na indeksu 2 i + 1, desnega pa na indeksu 2i + 2. Starš vozlišča, shranjenega na indeksu i, je shranjen na indeksu L^J. V vseh primerih zapisano seveda velja, če element z ustreznim indeksom v polju sploh obstaja. Kopica in operacije na njej Kopica je levo poravnano dvojiško drevo, v katerem za vsako vozlišče velja: Ce je A starš vozlišča B, potem je ključ v vozlišču A večji ali enak ključu v vozlišču B. Ce vozlišče nima otrok, velja, da je lastnosti zadoščeno. Tako definirana kopiča se imenuje tudi maksimalna kopica. Podobno bi definirali minimalno kopico, kjer bi za vsako vozlišče veljalo, da je ključ v vozlišču manjši od ključa v otroku. V nadaljevanju bomo maksimalni kopiči rekli samo kopiča. Ker bomo ko-pičo predstavili s poljem, zahtevamo, da imamo levo poravnano dvojiško drevo. Primer kopiče vidimo na sliki 2. Opazimo lahko, da je v korenskem vozlišču kopiče vedno ključ največje vrednosti, kar je tudi splošna lastnost kopiče. Spoji kopiči Prvi postopek nad kopičami, ki ga bomo predstavili, se imenuje spoji kopici. Gre za naslednje: podani imamo dve kopiči in še eno vozlišče. Vse troje bi radi spojili (združili) v eno dvojiško drevo, ki bo tudi kopiča. Začetno stanje problema je predstavljeno na sliki 3, na kateri vidimo dve kopiči (rdeče in zeleno obarvano drevo) ter dodatno (modro obarvano) vozlišče, ki bi ga želeli povezati s podanima kopičama. Rdeče in zeleno drevo zadoščata lastnostim kopiče, čelotno drevo pa ne predstavlja kopiče, saj modro vozlišče nima ključa, večjega od desnega otroka. Postopek spoji kopiči izvedemo tako: naše trenutno vozlišče na začetku postane dodatno (modro) vozlišče. Dokler s trenutnim vozliščem nismo v listu kopiče ali pa trenutno vozlišče krši lastnost kopiče (ključ v trenutnem vozlišču je manjši od vsaj enega izmed ključev v otročih), zamenjaj ključ s ključem večjega izmed otrok in se prestavi na vozlišče, s katerim smo zamenjali vrednosti. Korake postopka spoji kopiči za primer s slike 3 vidimo na sliki 4, pri čemer je trenutno vozlišče vedno obarvano z modro. Zgradi kopičo Pri postopku zgradi kopico predpostavimo, da imamo podano polje, katerega elementi ne zadoščajo nujno lastnostim kopiče. Elemente polja želimo preurediti tako, da bo čelotno polje predstavljalo ko-pičo. Poglejmo si primer, kjer je začetno stanje predstavljeno s sliko 5. Pri izgradnji kopiče si bomo pomagali s postopkom spoji kopici. Ker mora vsako vozlišče drevesa SLIKA 2. Primer kopice SLIKA 3. Začetno stanje postopka spoji kopici 23 PRESEK 43 (2015/2016) 6 RAČU N A L NIŠTVO —^ zadoščati lastnosti kopice, bomo po vrsti od desne proti levi in od spodaj navzgor spajali posamezne kopice. Listi dvojiškega drevesa vedno zadoščajo lastnosti kopice, saj nimajo otrok. Torej prvo vozlišče, pri katerem bomo izvedli postopek spoji kopici, bo starš najbolj desnega lista na zadnjem nivoju drevesa, zadnje bo pa korensko vozlišce. korak 1 26) korak 2 korak 3 31) SLIKA 4. Koraki postopka spoji kopici 0 1 2 3 4 5 6 7 8 9 vrednost 53 41 75 62 21 97 24 10 15 42 SLIKA 5. Polje, ki ne predstavlja nujno kopice, in pripadajoče dvojiško drevo. Na sliki 6 vidimo posamezne korake (en klic postopka spoji kopici) izvajanja postopka zgradi kopico. Poddrevesa z modro obarvanimi vozlišci že zadošcajo lastnostim kopice. Vozlišce obarvano z rdece pa na vsakem koraku predstavlja vozlišce, ki ga spajamo s pripadajocima poddrevesoma (kopicama). Po zadnjem koraku dobimo dvojiško drevo, ki predstavlja kopico. Odstrani najvecji element iz kopice Tokrat želimo iz obstojece kopice odstraniti najvecji element. V mislih imejmo, da bo v racunalniku kopica shranjena v polju, tako da ne bomo elementa dejansko odstranili, ampak se bomo pretvarjali, da je velikost kopice (število elementov v kopici) manjša od števila vseh elementov v polju. Najvecji element kopice ucinkovito odstranimo tako: Zamenjaj najvecji element kopice (korenski) z najbolj desnim listom zadnjega nivoja. Zmanjšaj velikost kopice za en element. Spoji »novi« korenski element s kopicama, ki ju predstavljata njegova otroka. korak 1 53) korak 2 53 korak 3 53 korak 4 53 korak 5 53 po koraku 5 ( SLIKA 6. Koraki postopka zgradi kopico 24 PRESEK 43 (2015/2016) 6 RACUNALNIŠ TVO Poglejmo primer odstranjevanja največjega elementa iz kopice s slike 7. Iz kopice želimo odstraniti največji element. Na prvem koraku ga zamenjamo z najbolj desnim listom zadnjega nivoja in zmanjšamo velikost kopice za 1. Na slikah 8 in 9 to pomeni, da si predstavljamo, da modro obarvano vozlišče (element polja) ni več del kopice. SLIKA 7. Kopica in pripadajoče polje Ker smo spremenili prvi element drevesa, se lahko zgodi, da krši pravilo kopice. Drugih elementov, ki so ostali v kopici, nismo spreminjali, zato so ohranili lastnost kopice. Imamo torej dve kopici (levo in desno poddrevo) korenskega vozlišca in korensko vozlišce, ki morebiti krši lastnost kopice. Izpolnjeni so torej pogoji, da izvedemo postopek spoji kopici. Ne pozabite, modro obarvano vozlišce ni vec del kopice. Po izvedenem postopku spajanja korenskega vozlišca s kopicama v levem in desnem pod-drevesu dobimo kopico predstavljeno z belimi vozli-šci na sliki 9. Uporaba kopice Kopica je zaradi svojih lastnostih koristna pri raz-licnih problemih. Ker imamo v kopici v korenskem vozlišcu na vsakem koraku vedno element z najve-cjim kljucem, je kopica zelo primerna za uporabo kot prednostna vrsta. V prednostno vrsto namrec dajemo elemente v nekem vrstnem redu, iz nje jih pa pridobivamo v vrstnem redu glede na njihovo prioriteto, ki pri implementaciji s kopico, predstavlja kljuce, glede na katere gledamo urejenost. Kot smo povedali v prejšnjih razdelkih, imamo v kopici v korenu vedno najvecji element, ki ga znamo enostavno odstraniti. Drugi primer uporabe, ki ga bomo predstavili tukaj, pa je urejanje podatkov v polju. Problem je sle- 0 1 2 3 4 5 6 7 8 9 vrednost 97 62 75 41 42 53 24 10 15 21 0 1 2 3 4 5 6 7 8 9 vrednost 21 62 75 41 42 53 24 10 15 97 0 1 2 3 4 5 6 7 8 9 vrednost 75 62 53 41 42 21 24 10 15 97 SLIKA8. SLIKA 9. Prvi korak odstranjevanja največjega elementa Dobljena kopica po odstranjevanju največjega elementa PRESEK 43 (2015/2016) 6 25 RAČU N A L NIŠTVO —^ dec: imamo polje napolnjeno s podatki. Podatke v polju želimo urediti nepadajoce. Tokrat bomo problem urejanja podatkov rešili s kopico. Pri odstranjevanju največjega elementa iz kopice lahko opazimo, da na mesto zadnjega elementa kopice (preden spremenimo velikost kopice) dobimo ravno najvecji element. Ce torej iz dobljenih kopic zaporedoma odstranjujemo najvecji element, dobimo v polju kljuce, urejene v nepadajo-cem vrstnem redu. Elemente odstranjujemo, dokler ima dobljena kopica vec kot en element. Seveda moramo pred odstranjevanjem kljucev iz podatkov polja zgraditi zacetno kopico. Temu postopku urejanja pravimo urejanje s kopico. Urejanje s kopico ima ca-sovno zahtevnost O(n log n) in je zato po hitrosti primerljivo z najhitrejšimi algoritmi urejanja. Poglejmo postopek urejanja s kopico na spodnjem primeru. Tokrat bomo zapisovali le polja, ki jih dobimo, in ne bomo izrisovali pripadajocih dvojiških dreves. Postopek je prikazan na sliki 10, pri cemer znova velja, da modro obarvani elementi niso vec del kopice. Križne vsote indeks 0 1 2 3 4 5 6 7 8 9 zacetno stanje polja 53 41 75 62 21 97 24 10 15 42 zvedemo zgradi kopico 97 62 75 41 42 53 24 10 15 21 odstrani najvecjega 75 62 53 41 42 21 24 10 15 97 odstrani najvecjega 62 42 53 41 15 21 24 10 75 97 odstrani najvecjega 53 42 24 41 15 21 10 62 75 97 odstrani najvecjega 42 41 24 10 15 21 53 62 75 97 odstrani najvecjega 41 21 24 10 15 42 53 62 75 97 odstrani najvecjega 24 21 15 10 41 42 53 62 75 97 odstrani najvecjega 21 10 15 24 41 42 53 62 75 97 odstrani najvecjega 15 10 21 24 41 42 53 62 75 97 odstrani najvecjega 10 15 21 24 41 42 53 62 75 97 postopek zakljucen 10 15 21 24 41 42 53 62 75 97 SLIKA 10. Koraki postopka uredi s kopico na primeru podanega polja _XXX www.dmfa-zaloznistvo.si -> Naloga reševalca je, da izpolni bele kvadratke s števkami od 1 do 9 tako, da bo vsota števk v zaporednih belih kvadratkih po vrsticah in po stolpcih enaka številu, ki je zapisano v sivem kvadratku na zacetku vrstice (stolpca) nad (pod) diagonalo. Pri tem morajo biti vse števke v posamezni vrstici (stolpcu) razlicne. ,6 3 10 9 2 16 11 14 N 9 RES ITEV KRIŽ NE VSOTE S 17 9 6 L 61 u S 9 LL E Z L 9 L 6 01 ■ 61 XXX 26 PRESEK 43 (2015/2016) 6