Kopica

Iz Wikipedije, proste enciklopedije

Kopíca je urejena drevesna podatkovna struktura.

Če sta A in B elementa in je B otrok od A, potem mora veljati sledeče pravilo:

ključ(A) ≥ ključ(B)

Na splošno je to v kopicah vseh vrst edina omejitev, pomeni pa, da je ekstremni element (bodisi najmanjši ali največji, odvisno od pomena relacije ≥) vedno v korenu drevesa. Zaradi te lastnosti se kopica uporablja tudi za implementacijo prednostne vrste, uporablja pa se tudi v algoritmu za urejanje z izboljšanim izbiranjem (ang. heapsort).

Najpogostejše operacije na kopici so izbris korenskega elementa in dodajanje novega elementa.