Binomska kopica

Iz MaFiRaWiki

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

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

Naslednja različica →
Vrstica 64: Vrstica 64:
[[/Primer brisanja minimuma|Primer]] [[/Primer brisanja minimuma|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 zmanjšanja ključa|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.
 +
 + Binomial-Heap-Delete(H,x)
 + Binomial-Heap-Decrease-Key(H,x,-∞)
 + Binomial-Heap-Extract-Min(H)
==Glej tudi== ==Glej tudi==

Različica od 10:17, 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

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.

 Binomial-Heap-Delete(H,x)
 Binomial-Heap-Decrease-Key(H,x,-∞)
 Binomial-Heap-Extract-Min(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