Kopica

podatkovna struktura
Za druge pomene glejte Kopica (potok).

Kopíca je urejena drevesna podatkovna struktura.

Primer maksimalne dvojiške kopice
Dvojiška kopica realizirana s tabelo

Za elemente v maksimalni kopici velja naslednje:

Ključ(starš) ≥ Ključ(otrok)

Posledica te relacije je, da je element z največjim ključem vedno v korenu kopice.

V minimalni kopici pa podobno velja:

Ključ(starš) ≤ Ključ(otrok)

Ta relacija pa zagotavlja, da je v korenu kopice element z najmanjšim ključem.

UporabaUredi

Zaradi hitrega dostopa do največjega oz. najmanjšega elementa in ugodne logaritemske časovne zahtevnosti za večino ostalih operacij, se kopica uporablja pri implementaciji podatkovne strukture prednostna vrsta in pri algoritmu za urejanje z izboljšanim izbiranjem (angleško HeapSort).

Pogoste operacijeUredi

  • brisanje korenskega elementa
  • dodajanje novega elementa
  • povečanje ključa v maksimalni oz. zmanjšanje ključa v minimalni kopici
  • združitev dveh kopic