Binomska kopica/Primer brisanja minimuma
Iz MaFiRaWiki
< Binomska kopica(Razlika med različicami)
Različica od 08:43, 30 april 2007 AleksandraVujasin (Pogovor | prispevki) ← Prejšnja različica |
Trenutna različica AleksandraVujasin (Pogovor | prispevki) |
||
Vrstica 16: | Vrstica 16: | ||
'''Psevdo koda:''' | '''Psevdo koda:''' | ||
- | Binomial-Heap-Extract-Min(H) | + | Binomska-Kopica-Zbriši-Min(H) |
poišči koren x z najmanjšim ključem v H in ga odtsrani | poišči koren x z najmanjšim ključem v H in ga odtsrani | ||
- | H' := Make-Binomial-Heap() | + | H' := Naredi-Binomsko-Kopico() |
spremeni vrstni red otrok od x-a in postavi kazalec head[H'] na začetek kopice | spremeni vrstni red otrok od x-a in postavi kazalec head[H'] na začetek kopice | ||
- | H := Binomial-Heap-Union(H,H') | + | H := Binomska-Kopica-Unija(H,H') |
return x | return x |
Trenutna različica
Slika 1.1 Najmanjši element v drevesu je 3. Odstranimo drevo s korenom 3 in zbrišemo koren.
Slika 1.2 Ostane nam tole.
Slika 1.3 Drugo drevo postane kopica, če ga uredimo tako, da stopnja dreves narašča.
Slika 1.4 Združimo kopici.
Slika 1.5 Nadaljujemo s procesom združevanja dreves, ki imajo isto stopnjo.
Slika 1.6 Nadaljujemo s procesom združevanja dreves, ki imajo isto stopnjo.
Slika 1.7 Konec.
Psevdo koda:
Binomska-Kopica-Zbriši-Min(H) poišči koren x z najmanjšim ključem v H in ga odtsrani H' := Naredi-Binomsko-Kopico() spremeni vrstni red otrok od x-a in postavi kazalec head[H'] na začetek kopice H := Binomska-Kopica-Unija(H,H') return x