Binomni hip

U Informatici, binomni hip je hip, sličan binarnom hipu, koji podržava brzo spajanje 2 hipa. To je postignuto koristeći posebnu strukturu stabla. Binomni hip je važan kao implementacija apstraktnog tipa podataka spojivi hip, koji je red sa prioritetima koji podržava spajanje (sa drugim redom).

Binomno stablo

Binomni hip je implementiran kao kolekcija binomnih stabala (uporedite sa binarnim hipom, koji ima oblik binarnog stabla). Binomno stablo je zadato rekurzivno:

• Binomno stablo stepena 0 je jedan čvor (koren bez dece)
• Binomno stablo stepena k ima koren čija su deca koreni binomnih stabala stepena k-1,k-2,...,2,1,0 (tim redosledom)

Binomna stabla stepena od 0 do 3. Svako stablo ima koren sa podstablima nižeg stepena, koja su označena. Npr. binomno stablo stepena 3 je spojeno sa binomnim stablom 2,1 i 0. stepena (označena kao plavo, zeleno i crveno; tim redosledom).

Binomno stablo stepena k ima 2^k čvorova i visina stabla je k. Zbog jedinstvene strukture, binomno stablo stepena k može biti napravljeno od 2 stabla stepena k-1, jednostavno kačeći jedno od njih kao najlevlje dete korena drugog stabla. Ovo svojstvo je najbitnije za operaciju spajanja binomnog hipa, koja je glavna prednost u odnosu na druge hipove. Ime dolazi od oblika; binomni koeficijent $n$ ima ${\tbinom {n}{d}}$ čvorova pri dubini $d$. (Pogledaj Binomni koeficijent)

Struktura binomnog hipa

Binomni hip je implementiran kao sklop binomnih stabala koja zadovoljavaju svojstva binomnog hipa:

• Svako binomno stablo u hipu se pridržava svojstva „najmanji hip"; ključ čvora je veći ili jednak ključu njegovog roditelja
• Može biti samo jedno ili nijedno binomno stablo za svaki stepen, uključujući stepen 0.

Prvo svojstvo osigurava da koren svakog binomnog stabla sadrži najmanji ključ u stablu, i svojstvo važi za ceo hip. Drugo svojstvo osigurava da se binomni hip sa n čvorova sastoji od najviše log n + 1 binomnih stabala. U stvari, broj i stepen ovih stabala je jedinstveno određen brojem čvorova n: svako binomno stablo odgovara jednoj cifri u binarnom prikazu broja n. Npr, broj 13 je 1101 u binarnoj osnovi, $2^{3}+2^{2}+2^{0}$, pa se binomni hip sa 13 čvorova sastoji od 3 binomna stabla stepena 3, 2, i 0 (pogledaj sliku ispod).

Primer binomnog hipa koji sadrži 13 čvorova sa ključevima. Hip se sastoji od 3 binomna stabla stepena 0, 2, i 3.

Implementacija

Pošto ni jedna operacija ne zahteva nasumičan pristup korenim čvorovima binomnih stabala, oni mogu biti čuvani u povezanoj listi, poređani po rastućem stepenu stabala.

Spajanje

Da bi spojili dva binomna stabla, prvo poredimo ključeve korena. Pošto je 7>3, tamnije stablo (na levoj strani) je nakačeno na svetlije stablo (na desnoj strani) kao podstablo. Rezultat je stablo reda 3.

Kao što je pomenuto iznad, najjednostavnija i najbitnija operacija je spajanje dva binomna stabla istog reda iz dva binomna hipa. Zbog strukture binomnih stabala, ona mogu biti spojena jednostavno. Pošto je koreni čvor najmanji element binomnog stabla (ima najmanji ključ), poredeći dva ključa, onaj manji je najmanji ključ u oba stabla, i on postaje novi koren. Drugo stablo onda postaje podstablo spojenog stabla. Ova operacija je osnovna za potpuno spajanje dva binomna hipa.

function spojiStabla(p, q):
    if p.koren.kljuc <= q.koren.kljuc:
        return p.dodajPodstablo(q)
    else:
        return q.dodajPodstablo(p)

Operacija spajanja dva hipa je verovatno najzanimljivija i koristi se kao podrutina u većini drugih operacija.

Ova slika pokazuje spajanje dva binomna hipa. Ovo je postignuto spajanjem dva binomna stabla istog stepena jedno po jedno. Ako je dobijeno spojeno stablo istog reda kao binomno stablo u jednom od dva hipa, onda se ta dva spajaju.

Kroz listu svih korena oba hipa se prolazi istovremeno, slično kao u algoritmu spajanja. Ako samo jedan hip sadrži stablo stepena j, to stablo se pomera u spojeni hip. Ako oba hipa sadrže stablo stepena j, onda se oba stabla spajaju u jedno reda j+1, tako da svojstvo „najmanji hip“ bude zadovoljeno. Primetite da će možda biti potrebno ovo stablo spojiti sa nekim drugim stablom stepena j+1, koje već postoji u jednom od hipova. U toku izvršavanja algoritma moramo da ispitamo najviše 3 stabla bilo kog stepena (dva iz dva hipa i jedno izgrađeno od 2 manja). Pošto svako binomno stablo u binomnom hipu odgovara jednoj cifri u binarnom prikazu broja čvorova hipa, postoji analogija između spajanja dva hipa i binarnog sabiranja broja čvorova oba hipa, zdesna nalevo. Kad god se tokom sabiranja javi prenos, to označava da su se spojila dva binomna stabla tokom spajanja hipova. Svako stablo je stepena najviše log n, gde je n broj čvorova u hipu, pa je vreme izvršavanja operacije spajanja O (log n).

function spojiHipove(p, q):
    while not (p.kraj() and q.kraj()):
        stablo = spojiStabla(p.trenutnoStablo(), q.trenutnoStablo())
        
        if not hip.trenutnoStablo().prazno():
            stablo = spojiStabla(stablo, hip.trenutnoStablo())
        
        hip.dodajStablo(stablo)
        hip.sledeci(); p.sledeci(); q.sledeci()

Umetanje

Umetanje novog elementa u postojeći hip može biti izvršeno pravljenjem novog hipa, koji sadrži samo taj element i onda ga spojiti sa prvobitnim hipom. Zbog spajanja umetanje zahteva O(log n) vremena, ali ipak ima amortizovano vreme O(1).

Traženje najmanjeg

Da bi pronašli najmanji element hipa, dovoljno je pronaći čvor sa najmanjim ključem među korenim čvorovima binomnih stabala. Ovo je moguće uraditi u vremenu O(log n), jer postoji samo logn stabala i isto toliko korenih čvorova za ispitivanje. Koristeći dodatni pokazivač na najmanji element, vreme za ovu operaciju je moguće smanjiti na O(1). Pokazivač mora biti ažuriran pri svakoj operaciji osim traženja najmanjeg. Ovo se može izvršiti u O(logn), bez povećanja vremena izvršavanja bilo koje operacije (O(logn) + O(logn) => O(logn)).

Brisanje najmanjeg

Za brisanje najmanjeg elementa iz hipa, prvo treba pronaći taj element, izbrisati ga iz binomnog stabla, i napraviti listu njegovih podstabala. Zatim transformisati ovu listu podstabala u poseban hip, preuređivaći ih od najmanjeg ka najvećem. Zatim spojiti ovaj hip sa prvobitnim hipom. Pošto svako stablo ima najviše logn dece, pravljenje novog stabla zahteva O(logn) vremena. Spajanje zahteva O(logn), pa cela operacija brisanja zahteva O(logn) vremna.

function izbrisiNajmanji(heap)
    najmanji = hip.stabla().prvo()
    for each trenutno in hip.stabla()
        if trenutno.koren < najmanji then najmanji = trenutno
    for each stablo in najmanji.podstabla()
        tmp.dodajStablo(tree)
    hip.izbrisiStablo(min)
    spoji(hip, tmp)

Smanjivanje ključa

Nakon smanjivanja ključa nekog elementa, on može postati manji od ključa roditelja, narušavajući svojstvo „najmanji hip“. U ovom slučaju razmeniti taj element sa njegovim roditeljem, a ako je potrebno i sa roditljem roditelja, i tako dalje sve dok svojstvo „najmanji hip“ nije zadovoljeno. Svako binomno stablo ima visinu od logn, tako da ova operacija zahteva O(logn) vremena.

Brisanje

Za brisanje elementa iz hipa, smanjiti mu ključ na minus beskonačno, tj. na vrednost manju od vrednosti ključa bilo kog drugog elementa, a zatim izbrisati najmanji element u hipu (a to je upravo element koji smo hteli da izbrišemo).

Performanse

Svaka od sledeći operacija rade u vremenu O(logn), gde je n broj elemenata:

• Umetanje novog elementa u hip
• Traženje elementa sa najmanjim ključem
• Brisanje elementa sa najmanjim ključem
• Smanjivanje ključa datog elementa
• Brisanje datog elementa iz hipa
• Spajanje dva hipa u jedan

Traženje najmanjeg se može postići u vremenu O(1), kao što je iznad već objašnjeno.

Upotreba

• Simulacija izolovanih događaja (en:Discrete event simulation)
• Red sa prioritetima

Reference

• Cormen, Thomas H.; Leiserson, Charles E.; Ronald L. Rivest; Stein, Clifford (2001). „19: Binomial Heaps”. Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. str. 455-475. ISBN 978-0-262-03293-3. 
• Vuillemin, J. (1978). A data structure for manipulating priority queues. Communications of the ACM 21, 309–314.

Spoljašnje veze

• Java aplet koji simulira binomni hip
• Implementacija binomnog hipa u programskom jeziku Pajton
• Dve implementacije binomnog hipa u programskom jeziku C (opšti i optimizovan za celobrojne ključeve)
• Implementacija binomnog hipa u programskom jeziku Haskel
• Implementacija binomnog hipa u programskom jeziku Common Lisp