Binomska kopica

Iz MaFiRaWiki

Vsebina

Binomska kopica

Binomska kopica (Vuillemin, 1978) je podatkovna struktura sestavljena iz binomskih dreves, ki zadoščajo naslednjim pogojem:

  • Binomska drevesa v kopici imajo lastnost minimalnih kopic (angl. min-heap-ordered trees). To pomeni, da je spodnji ključ (otrok) vedno večji (ali enak) zgornjemu ključu (starš). To nam pove, da koren vsebuje najmanjši element drevesa.
  • Za vsako nenegativno število k, obstaja samo eno binomsko drevo v kopici, katerega koren ima stopnjo k. Torej binomska kopica ima lahko le 0 ali 1 binomsko drevo s stopnjo k. Ta lastnost nam pove, da je binomska kopica z n vozlišči sestavljena iz največ log n + 1 binomskih dreves.

Kar je še zanimivo, je to, da je število dreves in kako so ta drevesa urejena povezano s številom elementov n: vsako binomsko drevo predstavlja števko 1 v binarnem zapisu števila n. Za primer vzemimo spodnjo kopico, ki ima 19 elementov. Število 19 lahko zapišemo kot 10011 = 1*24 + 0*23 + 0*22 + 1*21 + 1*20, zato bo ta binomska kopica sestavljena iz treh dreves stopnje 4, 1 in 0.

Primer binomske kopice:

image:BinomskaKopica.jpg

Opomba: Binomska kopica ni navadna kopica.

Struktura binomske kopice

Vsako vozlišče v kopici H (označimo ga z x)vsebuje naslednje povezave: kazalec do starša (označimo z p[x]), kazalec do levega otroka, ki je najbolj oddaljen (označimo z levi[x]) in kazalec do desnega otroka, ki je najbolj oddaljen (označimo z desni[x]). Če je x koren, potem je p[x] = null. Če x nima otrok, potem je levi[x] = null in če je x najbolj desni otrok , potem je desni[x]= null. Vsako vozlišče x vsebuje tudi stopnjo[x], ki nam pove število otrok od x. Do binomske kopice dostopamo preko kazalca glava[H], ki kaže na prvi koren v kopici. Če binomska kopica ne vsebuje elementov, je glava[H] = null.
Na spodnji sliki se vidi tudi, da so koreni dreves povezani glede na stopnjo dreves. Stopnja dreves se manjša od leve proti desni.

image:KopicaStruktura1.jpg

Operacije na binomskih kopicah

Naredi kopico

Enostavno naredimo in vrnemo kopico brez elementov. Čas potreben za to je O(1).

Psevdo koda:

 Naredi-Binomsko-Kopico()
 glava[H] = null
 return H

Poišči minimum

Operacija poišči minimum vrne kazalec na minimalni element. Ta se nahaja med koreni, saj imajo drevesa lastnost minimalne kopice. Operacija preveri vse korene (največ jih je lahko logn + 1), tako da minimum shrani v min, kazalec na trenutni minimum pa v y. Čas potreben za to operacijo je O(log n).

Psevdo koda:

 Binomska-Kopica-Minimum(H)
 y := null
 x := glava[H]
 min := ∞
 while x ≠  null
   do if ključ[x] < min
         then min := ključ[x]
              y := x
      x := desni[x]
 return y

Unija dveh kopic

Dve binomski kopici H in H' združimo v dveh fazah. Prva faza je, da izvedemo operacijo Binomiska-Kopica-Združitev, ki združi korene kopic H in H' po načelu naraščanja stopnje binomskih dreves. Ko drevesi združimo, sta lahko največ dve drevesi z isto stopnjo. Nadaljujemo s procesom združevanja dreves z isto stopnjo, dokler na koncu ne ostanejo drevesa različne stopnje. To delamo z operacijo Binomska-Link, ki združi dve drevesi tako, da postane koren z večjim ključem levi sin korena z manjšim ključem.
Čas, ki ga porabimo za operacijo Binomska-Kopica-Unija je O(log n).

Primer

Vstavljanje vozlišča

Enostavno naredimo novo kopico H' (z novim elementom) in jo nato združimo z originalno kopico H. To naredimo v času O(1).

Psevdo koda:

 Binomska-Kopica-Vstavi(H,x)
 H' := Naredi-Binomsko-Kopico()
 p[x] := null
 levi[x] := null
 desni[x] := null
 stopnja[x] := 0
 glava[H'] := x
 H := Binomska-Kopica-Unija(H,H')

Brisanje minimuma

Da bi zbrisali najmanjši element, ga najprej poiščemo in ga nato odstranimo, skupaj s poddrevesi. Nastane nova kopica, ki pa jo moramo urediti tako, da stopnja dreves narašča (obrnemo kopico). Sedaj jo le še združimo s prvotno kopico.

Primer

Zmanjšanje ključa

Izberemo si ključ, ki ga želimo zmanjšati. Ključ ima sedaj novo vrednost. Če je ta vrednost manjša od vrednosti njegovega starša, ju zamenjamo. To počnemo toliko časa, dokler drevo ni urejeno (lastnost minimalnih kopic).

Primer

Brisanje ključa

Da bi zbrisali ključ v drevesu, najprej postavimo vrednost ključa na -neskončnost, tako, da je ta element sigurno najmanjši in ga nato zbrišemo.

 Binomska-Kopica-Zbriši(H,x)
 Binomska-Kopica-ZmanjšajKljuč(H,x,-∞)
 Binomska-Kopica-ZbrišiKljuč(H)

Glej tudi

Viri

Literatura

  • Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introductions to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 19: Binomial Heaps, pp. 455-475.
Osebna orodja