Binomska kopica

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 20:28, 29 april 2007
AleksandraVujasin (Pogovor | prispevki)

← Prejšnja različica
Različica od 08:20, 30 april 2007
AleksandraVujasin (Pogovor | prispevki)

Naslednja različica →
Vrstica 23: Vrstica 23:
'''Psevdo koda:''' '''Psevdo koda:'''
Make-Binomial-Heap() Make-Binomial-Heap()
- head[H] = NIL+ glava[H] = NIL
return H return H
Vrstica 32: Vrstica 32:
Binomial-Heap-Minimum(H) Binomial-Heap-Minimum(H)
y := NIL y := NIL
- x := head[H]+ x := glava[H]
- min := infinity+ min :=
while x ≠ NIL while x ≠ NIL
- do if key[x] < min+ do if ključ[x] < min
- then min := key[x]+ then min := ključ[x]
y := x y := x
- x := sibling[x]+ x := desni[x]
return y return y
Vrstica 54: Vrstica 54:
H' := Make-Binomial-Heap() H' := Make-Binomial-Heap()
p[x] := NIL p[x] := NIL
- child[x] := NIL+ levi[x] := NIL
- sibling[x] := NIL+ desni[x] := NIL
- degree[x] := 0+ stopnja[x] := 0
- head[H'] := x+ glava[H'] := x
H := Binomial-Heap-Union(H,H') H := Binomial-Heap-Union(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 brisanja minimuma|Primer]]
==Glej tudi== ==Glej tudi==

Različica od 08:20, 30 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()
 glava[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 := glava[H]
 min := ∞
 while x ≠  NIL
     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 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
 levi[x] := NIL
 desni[x] := NIL
 stopnja[x] := 0
 glava[H'] := x
 H := Binomial-Heap-Union(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

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