Podatkovna struktura je sistematični način, kako organizirati skupino podatkov.

Za vsako podatkovno strukturo potrebujemo postopke za vstavljanje, brisanje, iskanje...

Podatkovne strukture ločimo glede na to, katere podatke dobimo iz nje in na kakšen način.

Primeri podatkovnih struktur so seznami, tabele, drevesa, kopice ...

Kopico uvrščamo med levo poravnane urejene drevesne podatkovne strukture. Kopica ima na vozliščih elemente, ki so urejeni po velikosti, zato rečemo, da je urejena. Levo poravnano drevo pa pomeni, da smo vanj vstavljali elemente od leve proti desni ter hkrati nismo začeti zapolnjevati nekega sloja, če prejšnji sloj še ni bil zapolnjen.

Kopica je uporabna predvsem zaradi možnosti hitrega dostopa do največjega oz. najmanjšega elementa, kadar imamo podatke urejene po velikosti.

Lastnosti kopice:

1. Višina kopice je odvisna od števila vozlišč . Izračunamo jo

2. Število listov je tudi odvisno od števila vozlišč:

   (celoštevilsko deljenje z ).

Primer: Kolikšna je višina spodnje kopice in koliko ima listov?

Kopica

1. Število vozlišč:
2. Višina:
3. Število listov:

Najvišje postavljeni element kopice imenujemo oče ali koren kopice, nižje postavljeni so sinovi.

Kopice ločimo glede na urejenost vozlišč.

MINIMALNA KOPICA je kopica, za katero velja, da je element v korenu vedno manjši od elementov njegovih sinov, obe poddrevesi korena pa sta spet minimalni kopici.

Primer minimalne kopice

MAKSIMALNA KOPICA je kopica, za katero velja, da je element v korenu vedno večji od elementov njegovih sinov, obe poddrevesi korena pa sta spet maksimalni drevesi.

Primer maksimalne kopice

MAKSIMALNA IN MINIMALNA KOPICAje kopica, katere element v korenu je enak elementom njegovih sinov, obe poddrevesi korena pa sta prav tako maksimalni in minimalni drevesi.

Primer maksimalne in minimalne kopice

Spodaj so primeri dreves. Prva skupina predstavlja kopice, druga ne.

Primeri kopic

Primeri niso kopice - niso levo poravnani.

Tabela je pri veliki količini podatkov preglednejša in je zelo učinkovita predvsem pri opreacijah urejanja. Če želimo kopico predstaviti s tabelo, upoštevamo naslednja pravila:

1. Koren/oče je prvi element tabele (na mestu z indeksom nič je lahko kar koli, saj tega mesta ne štejemo).
2. Če je vozlišče kopice na -tem mestu, je njegov levi sin na mestu , desni pa na mestu .
3. Vozlišče na -tem mestu ima torej svojega očeta na mestu (celoštevilsko deljenje).

Primer:

kopica

Tabela, ki ustreza zgornji kopici:

Vstavljanja elementa se lotimo tako, da element vstavimo v list drevesa na -to mesto. Nov element moramo razporediti po kopici navzgor (primerjati ga moramo z očetom), dokler novonastalo drevo ne ustreza urejenosti kopice. To drevo je ponovno urejena kopica.

Naj ima kopica na prvem mestu maksimalni element. Vzemimo ga iz kopice. S tem smo spremenili kopico. Popravimo jo tako, da na mesto, kjer manjka element - na prvo mesto - postavimo zadnji element v tabeli. Po že znanem postopku nato uredimo kopico.

Spodnja slika prikazuje primer kopice, ki smo jo uredili po odvzemu maksimalnega elementa.

Odvzem maksimalnega elementa

Kaj je to kopica?

Nazaj Naprej

Katere skupine kopic pozanmo?

Nazaj Preveri Naprej

Označi pravilne trditve.

Nazaj Preveri Naprej

Katero vrednost ima oče v kopici:

Preveri

Nazaj Naprej

Vsak začetek stavka v levem stolpcu dopolnite z ustreznim nadaljevanjem na desni strani.

Nazaj Preverite Naprej

• http://penelope.fmf.uni-lj.si/r2wiki/images/4/4b/KOPICA2.pdf

• http://www.nauk.si/materials/4630/out/#state=9

• http://www.nauk.si/materials/1318/out/#state=55

• http://wiki.fmf.uni-lj.si/wiki/Kopica