Kopica
podatkovna struktura From Wikipedia, the free encyclopedia
Remove ads
Kopíca je urejena drevesna podatkovna struktura.


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.
Remove ads
Uporaba
Zaradi hitrega dostopa do največjega oziroma najmanjšega elementa in ugodne logaritemske časovne zahtevnosti za večino drugih operacij, se kopica uporablja pri implementaciji podatkovne strukture prednostna vrsta in pri algoritmu za urejanje z izboljšanim izbiranjem (angleško HeapSort).
Pogoste operacije
- brisanje korenskega elementa
- dodajanje novega elementa
- povečanje ključa v maksimalni oz. zmanjšanje ključa v minimalni kopici
- združitev dveh kopic
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads