Binomska kopica/Primer unije dveh kopic

Iz MaFiRaWiki

image:Unija1.jpg

Slika 1.1 Združili bomo dve binomski kopici H in H'.

image:Unija2.jpg

Slike 1.2 Kopici smo združili tako, da stopnja binomskih dreves od leve proti desni narašča.

image:Unija3.jpg

Slika 1.3 Sedaj nadaljujemo z združevanjem dreves z isto stopnjo. V tem koraku smo združili vozlišči 10 in 11, saj sta oba 0-te stopnje. Manjši postane koren večjega.

image:Unija4.jpg

Slika 1.4 Naslednji drevesi, ki ju združimo sta 5 in 3, saj sta oba 2. stopnje. Večji postane levi sin manjšega.

image:Unija5.jpg

Slika 1.5 Vidimo, da imata drevesi 3 in 8 isto stopnjo, zato združimo še ti dve drevesi, po načelu večji postane levi sin manjšega.
Postopek je končan, saj smo dobili dve drevesi različne stopnje.

Psevdo koda:

 Binomska-Kopica-Unija(H1,H2)
 H := Naredi-Binomsko-Kopico()
 glava[H] := Binomska-Kopica-Združitev(H1,H2)
 if glava[H] = null
    then return H
 prej-x := null
 x := glava[H]
 nasl-x := desni[x]
 while nasl-x ≠ null
     do if (stopnja[x] ≠ stopnja[nasl-x]) or
               (desni[nasl-x] ≠ null
               and stopnja[desni[nasl-x]] = stopnja[x])
           then prej-x := x
                x := nasl-x
           else if ključ[x] <= ključ[nasl-x]
                then desni[x] := desni[nasl-x]
                     Binomial-Link(next-x,x)
                else if prej-x = null
                        then glava[H] = nasl-x
                        else desni[prej-x] := nasl-x
                     Binomial-Link(x,nasl-x)
                     x := nasl-x
        nasl-x := desni[x]
 return H

Binomial-Link(y,z) operacija poveže drevo Bk-1 (ki ima koren y) z drevesom Bk-1 (ki ima koren z), t.j. z postane starš od y. Koren drevesa Bk postane z.

 Binomska-Link(y,z)
 p[y] := z
 desni[y] := levi[z]
 levi[z] := y
 stopnja[z] := stopnja[z] + 1

Operacija Binomial-Heap-Merge(H1,H2) pa poveže korene dreves H1 in H2, tako, da stopnja dreves narašča.

 Binomska-Kopica-Združitev(H1,H2)
 a = glava[H1]
 b = glava[H2]
 glava[H1] = Min-Stopnja(a, b)
 if glava[H1] = null
    return
 if glava[H1] = b
  then b = a
 a = glava[H1]
 while b ≠ null
   do if desni[a] = null
         then desni[a] = b
              return
         else if stopnja[desni[a]] < stopnja[b]
                 then a = desni[a]
                 else c = desni[b]
                      desni[b] = desni[a]
                      desni[a] = b
                      a = desni[a]
                      b = c
Osebna orodja