Binomska kopica

Iz MaFiRaWiki

(Razlika med različicami)

Različica od 20:28, 29 april 2007

Vsebina

Binomska kopica

Binomska kopica (Vuillemin, 1978) je zbirka 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

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] = NIL. Če x nima otrok, potem je levi[x] = NIL in če je x najbolj desni otrok , potem je desni[x]= NIL. 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] = NIL.
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:

 Make-Binomial-Heap()
 head[H] = NIL
 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:

 Binomial-Heap-Minimum(H)
 y := NIL
 x := head[H]
 min := infinity
 while x ≠  NIL
     do if key[x] < min
           then min := key[x]
                y := x
        x := sibling[x]
 return y

Unija dveh kopic

Dve binomski kopici H in H' združimo v dveh fazah. Prva faza je, da izvedemo operacijo Binomial-Heap-Merge, 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 Binomial-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 Binomial-Heap-Union 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:

 Binomial-Heap-Insert(H,x)
 H' := Make-Binomial-Heap()
 p[x] := NIL
 child[x] := NIL
 sibling[x] := NIL
 degree[x] := 0
 head[H'] := x
 H := Binomial-Heap-Union(H,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