Kazalo:
Opredelitev - Kaj pomeni Heap?
Kopa, v okviru strukture podatkov, je drevesna podatkovna struktura, ki izpolnjuje lastnost kopice, kjer je vsakemu elementu dodeljena ključna vrednost ali ponder. Ključ nižje vrednosti ima vedno nadrejeno vozlišče s ključem višje vrednosti. Temu se reče max-heap struktura, med vsemi vozlišči pa ima korensko vozlišče najvišji ključ.
Včasih ima drevesna struktura obratno strukturo, kjer ima element s ključem z večjo vrednostjo kot nadrejeno vozlišče vedno ključ z nižjo vrednostjo. Temu rečemo struktura min-heap, med vsemi vozlišči pa ima koreninsko vozlišče najnižjo tipko.
Techopedia razlaga Heap
Praktičnih omejitev glede števila otrok, ki jih lahko vsako vozlišče ima v kopici, ni, čeprav ima vsako vozlišče največ dva. Kopča velja za najučinkovitejšo izvedbo abstraktne podatkovne vrste, znane kot prednostna vrsta. Izvedba kopice je bistvena v različnih algoritmih grafov (vključno z algoritmom Dijkstra), pa tudi v algoritmu razvrščanja množice.
Heaps ima več različic, ki z visoko učinkovitostjo delujejo kot abstraktne izvedbe prioritetnih vrst podatkovnih vrst. Mnoge aplikacije, kot so algoritmi grafov, zahtevajo izvajanje prioritetnih čakalnih vrst.
Niz je najpogostejša izvedbena oblika kopice, kjer za povezavo med njenimi elementi ni potrebnih kazalcev.
Heaps izvaja več operacij, vključno z:
- Find-max: Išči največje ključno vozlišče med skupino vozlišč
- Najdi-min: Išči najnižje vozlišče ključ med skupino vozlišč
- Delete-max: Izbriše najvišje ključno vozlišče med skupino vozlišč
- Delete-min: izbriše najnižje vozlišče ključev med skupino vozlišč
Heaps vključujejo tudi funkcije, ki izvajajo spajanje, vstavljanje in spremembe tipk.
Ta opredelitev je bila napisana v okviru strukture podatkov
