Podatkovna struktura kopica

Podatkovna struktura kopica

• Kopica (heap) je posebna oblika dvojiškega drevesa, ki se uporablja za implementacijo prioritetne vrste in urejanje podatkov (heap sort).
• Maksimalna kopica je dvojiško drevo, kjer je vrednost v korenu večja od vrednosti v njegovih otrocih, obe poddrevesi korena pa sta tudi kopici.
• Pri minimalni kopici je koren manjši od obeh otrok.
• V nadaljevanju se obravnava maksimalna kopica, vendar vse velja simetrično tudi za minimalno kopico.

Predstavitev kopice s poljem

• Koren je prvi element polja na indeksu 0.
• Vozlišče na indeksu i ima levega otroka na indeksu 2i+1 in desnega otroka na indeksu 2i+2.
• Vozlišče na indeksu i ima starša na indeksu [(i-1)/2].
• Polje [11,7,9,4,2,8,5,?,?,?,?,1,6] hrani kopico s slike, pri čemer ? označuje neizkoriščene lokacije.
• Pričakovano je, da je kopica levo poravnano drevo, izognemo se neuporabljene elemente v sredini polja.

Atributi kopice

• Za polje A, ki predstavlja kopico, se hranita dva atributa: dolžina[A], ki predstavlja velikost polja, in velikost-kopice[A], ki je število elementov v kopici.
• Velja velikost-kopice[A] ≤ dolžina[A]; če velikost kopice preseže velikost polja, je treba polje povečati ali ustvariti večje.
• Koren kopice je v elementu A[0].
• Funkcije STARS(i), LEVI(i) in DESNI(i) vrnejo indeks starša, levega in desnega otroka i-tega elementa v polju.
  • STARS(i) vrne [(i-1)/2].
  • LEVI(i) vrne 2*i+1.
  • DESNI(i) vrne 2*i+2.
• Primer: starš elementa A[3] je na indeksu [(3-1)/2]=1, levi otrok na indeksu 23+1=7 in desni otrok na indeksu 23+2=8.

Lastnosti Maksimalne kopice

• Za vsako vozlišče, razen za koren, velja A[STARS(i)] ≥ A[i].
• Največji element v kopici je shranjen v korenu dvojiškega drevesa, torej v A[0].
• Vsi elementi vsakega poddrevesa kopice so manjši ali enaki korenu poddrevesa.
• Višina vozlišča v kopici je enaka številu povezav na najdaljši poti od vozlišča do lista pod njim.
• Višina kopice ustreza višini korena.
• Višina kopice z n elementi je reda O(log n).

Vzdrževanje lastnosti kopice

• Pomožna procedura VZDRZUJ-MAX-KOPICO(A, i) preuredi polje A tako, da ponovno vzpostavi lastnost kopice, če je ta prekršena.
• Vhoda v proceduro sta polje kopice A in indeks elementa i, ki predstavlja koren (pod)drevesa.
• Procedura predpostavlja, da sta poddrevesi vozlišča i že kopici.
• Če je A[i] manjši od A[LEVI(i)] ali A[DESNI(i)], se A[i] premesti po kopici navzdol, da poddrevo s korenom pri indeksu i ponovno postane kopica.
• Na vsakem koraku premestitve se koren izmenja s tistim od otrok, ki ima večjo vrednost.
• Časovna zahtevnost procedure je O(log n).

Tvorba kopice

• Polje A dolžine n se pretvorba v kopico izvede z zaporednim izvajanjem procedure VZDRZUJ-MAX-KOPICO.
• Listi kopice postanejo elementi polja z indeksi od [n/2] do n-1. Vsak list je kopica velikosti 1.
• Lastnost kopice se v notranjih vozliščih vzpostavi s klicem procedure VZDRZUJ-MAX-KOPICO za indekse od [n/2]-1 do 0.

Algoritem za tvorbo kopice

• ZGRADI-MAX-KOPICO(A):
  • velikost-kopice[A] ← dolžina[A]
  • for i ← [dolžina[A]/2]-1 downto 0 do
  • VZDRZUJ-MAX-KOPICO(A, i)
• Primer: pretvorba polja A=[4,1,3,2,16,9,10,14,8,7] v kopico z n=10 elementi.
• V zanki se zaporedoma izvedejo klici VZDRZUJ-MAX-KOPICO(A, i) za i=4,3,2,1,0.
• Časovna zahtevnost procedure ZGRADI-MAX-KOPICO je O(n).

Urejanje s kopico (heapsort)

• Procedura UREJANJE-S-KOPICO(A) uredi polje A z n elementi tako, da ga pretvori v kopico in ponavlja naslednji postopek:
  • Največji element polja (v korenu A[0]) se postavi na zadnje mesto, z zamenjavo z A[n-1].
  • Odstrani se vozlišče n, z zmanjšanjem velikost-kopice[A] za 1.
  • Preostale podatke (A[0,...,n-2]) se pretvori v kopico s klicem VZDRZUJ-MAX-KOPICO(A, 0).
• Postopek se konča, ko velikost kopice postane 1.
• Časovna zahtevnost procedure je O(n log n).

Algoritem Urejanje s kopico

• UREJANJE-S-KOPICO(A)
• ZGRADI-MAX-KOPICO(A)
• for i ← dolžina[A]-1 downto 1 do
• zamenjaj A[0] ↔ A[i]
• velikost-kopice[A] ← velikost-kopice[A] - 1
• VZDRZUJ-MAX-KOPICO(A, 0)
• Primer urejanja polja A=[4,1,3,2,16,9,10,14,8,7] s heapsortom.
• Najprej se polje pretvori v kopico, nato se koren prestavi na zadnje mesto in polje se skrajša.
• Postopek se ponavlja, dokler ne ostane samo en element polja.

Prednostna vrsta

• Prednostna vrsta ali prioritetna vrsta (priority queue) je podatkovna struktura za vzdrževanje množice elementov s pridruženimi ključi, ki predstavljajo prioritete elementov.
• V prednostni vrsti je vedno na prvem mestu element z največjim ključem, zato jo je mogoče implementirati s kopico.
• Operacije na prednostni vrsti, implementirane s kopico:
• MAXIMUM-KOPICE(A): vrne največji ključ iz prednostne vrste A; časovna zahtevnost je O(1).
• IZLOČI-MAXIMUM-KOPICE(A): odstrani in vrne največji ključ iz A; časovna zahtevnost je O(log n).
• VSTAVI-V-KOPICO(A, k): vstavi ključ k v A; časovna zahtevnost je O(log n).

Izločanje maksimuma kopice

• IZLOČI-MAXIMUM-KOPICE(A):
• if velikost-kopice[A] < 1 then
• error prazna kopica
• max ← A[0]
• A[0] ← A[velikost-kopice[A] - 1]
• velikost-kopice[A] ← velikost-kopice[A] - 1
• VZDRZUJ-MAX-KOPICO(A, 0)
• return max

Vstavljanje v kopico

• VSTAVI-V-KOPICO(A, k):
• if velikost-kopice[A] = dolžina[A] then
• error polna kopica
• velikost-kopice[A] ← velikost-kopice[A] + 1
• i ← velikost-kopice[A] - 1
• while i > 0 and A[STARS(i)] < k do
  • A[i] ← A[STARS(i)]
  • i ← STARS(i)
• A[i] ← k
• Primer: vstavljanje ključa 12 v kopico.