Биномни хип

У Информатици, биномни хип је хип, сличан бинарном хипу, који подржава брзо спајање 2 хипа. То је постигнуто користећи посебну структуру стабла. Биномни хип је важан као имплементација апстрактног типа података спојиви хип, који је ред са приоритетима који подржава спајање (са другим редом).

Биномно стабло

Биномни хип је имплементиран као колекција биномних стабала (упоредите са бинарним хипом, који има облик бинарног стабла). Биномно стабло је задато рекурзивно:

• Биномно стабло степена 0 је један чвор (корен без деце)
• Биномно стабло степена k има корен чија су деца корени биномних стабала степена k-1,k-2,...,2,1,0 (тим редоследом)

Биномна стабла степена од 0 до 3. Свако стабло има корен са подстаблима нижег степена, која су означена. Нпр. биномно стабло степена 3 је спојено са биномним стаблом 2,1 и 0. степена (означена као плаво, зелено и црвено; тим редоследом).

Биномно стабло степена k има 2^k чворова и висина стабла је k. Због јединствене структуре, биномно стабло степена k може бити направљено од 2 стабла степена k-1, једноставно качећи једно од њих као најлевље дете корена другог стабла. Ово својство је најбитније за операцију спајања биномног хипа, која је главна предност у односу на друге хипове. Име долази од облика; биномни коефицијент $n$ има ${\tbinom {n}{d}}$ чворова при дубини $d$. (Погледај Биномни коефицијент)

Структура биномног хипа

Биномни хип је имплементиран као склоп биномних стабала која задовољавају својства биномног хипа:

• Свако биномно стабло у хипу се придржава својства „најмањи хип"; кључ чвора је већи или једнак кључу његовог родитеља
• Може бити само једно или ниједно биномно стабло за сваки степен, укључујући степен 0.

Прво својство осигурава да корен сваког биномног стабла садржи најмањи кључ у стаблу, и својство важи за цео хип. Друго својство осигурава да се биномни хип са n чворова састоји од највише log n + 1 биномних стабала. У ствари, број и степен ових стабала је јединствено одређен бројем чворова n: свако биномно стабло одговара једној цифри у бинарном приказу броја n. Нпр, број 13 је 1101 у бинарној основи, $2^{3}+2^{2}+2^{0}$, па се биномни хип са 13 чворова састоји од 3 биномна стабла степена 3, 2, и 0 (погледај слику испод).

Пример биномног хипа који садржи 13 чворова са кључевима. Хип се састоји од 3 биномна стабла степена 0, 2, и 3.

Имплементација

Пошто ни једна операција не захтева насумичан приступ кореним чворовима биномних стабала, они могу бити чувани у повезаној листи, поређани по растућем степену стабала.

Спајање

Да би спојили два биномна стабла, прво поредимо кључеве корена. Пошто је 7>3, тамније стабло (на левој страни) је накачено на светлије стабло (на десној страни) као подстабло. Резултат је стабло реда 3.

Као што је поменуто изнад, најједноставнија и најбитнија операција је спајање два биномна стабла истог реда из два биномна хипа. Због структуре биномних стабала, она могу бити спојена једноставно. Пошто је корени чвор најмањи елемент биномног стабла (има најмањи кључ), поредећи два кључа, онај мањи је најмањи кључ у оба стабла, и он постаје нови корен. Друго стабло онда постаје подстабло спојеног стабла. Ова операција је основна за потпуно спајање два биномна хипа.

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

Операција спајања два хипа је вероватно најзанимљивија и користи се као подрутина у већини других операција.

Ова слика показује спајање два биномна хипа. Ово је постигнуто спајањем два биномна стабла истог степена једно по једно. Ако је добијено спојено стабло истог реда као биномно стабло у једном од два хипа, онда се та два спајају.

Кроз листу свих корена оба хипа се пролази истовремено, слично као у алгоритму спајања. Ако само један хип садржи стабло степена ј, то стабло се помера у спојени хип. Ако оба хипа садрже стабло степена ј, онда се оба стабла спајају у једно реда ј+1, тако да својство „најмањи хип“ буде задовољено. Приметите да ће можда бити потребно ово стабло спојити са неким другим стаблом степена ј+1, које већ постоји у једном од хипова. У току извршавања алгоритма морамо да испитамо највише 3 стабла било ког степена (два из два хипа и једно изграђено од 2 мања). Пошто свако биномно стабло у биномном хипу одговара једној цифри у бинарном приказу броја чворова хипа, постоји аналогија између спајања два хипа и бинарног сабирања броја чворова оба хипа, здесна налево. Кад год се током сабирања јави пренос, то означава да су се спојила два биномна стабла током спајања хипова. Свако стабло је степена највише log n, где је n број чворова у хипу, па је време извршавања операције спајања 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()

Уметање

Уметање новог елемента у постојећи хип може бити извршено прављењем новог хипа, који садржи само тај елемент и онда га спојити са првобитним хипом. Због спајања уметање захтева O(log n) времена, али ипак има амортизовано време O(1).

Тражење најмањег

Да би пронашли најмањи елемент хипа, довољно је пронаћи чвор са најмањим кључем међу кореним чворовима биномних стабала. Ово је могуће урадити у времену O(log n), јер постоји само logn стабала и исто толико корених чворова за испитивање. Користећи додатни показивач на најмањи елемент, време за ову операцију је могуће смањити на O(1). Показивач мора бити ажуриран при свакој операцији осим тражења најмањег. Ово се може извршити у O(logn), без повећања времена извршавања било које операције (O(logn) + O(logn) => O(logn)).

Брисање најмањег

За брисање најмањег елемента из хипа, прво треба пронаћи тај елемент, избрисати га из биномног стабла, и направити листу његових подстабала. Затим трансформисати ову листу подстабала у посебан хип, преуређиваћи их од најмањег ка највећем. Затим спојити овај хип са првобитним хипом. Пошто свако стабло има највише logn деце, прављење новог стабла захтева O(logn) времена. Спајање захтева O(logn), па цела операција брисања захтева O(logn) времна.

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)

Смањивање кључа

Након смањивања кључа неког елемента, он може постати мањи од кључа родитеља, нарушавајући својство „најмањи хип“. У овом случају разменити тај елемент са његовим родитељем, а ако је потребно и са родитљем родитеља, и тако даље све док својство „најмањи хип“ није задовољено. Свако биномно стабло има висину од logn, тако да ова операција захтева O(logn) времена.

Брисање

За брисање елемента из хипа, смањити му кључ на минус бесконачно, тј. на вредност мању од вредности кључа било ког другог елемента, а затим избрисати најмањи елемент у хипу (а то је управо елемент који смо хтели да избришемо).

Перформансе

Свака од следећи операција раде у времену O(logn), где је n број елемената:

• Уметање новог елемента у хип
• Тражење елемента са најмањим кључем
• Брисање елемента са најмањим кључем
• Смањивање кључа датог елемента
• Брисање датог елемента из хипа
• Спајање два хипа у један

Тражење најмањег се може постићи у времену O(1), као што је изнад већ објашњено.

Употреба

• Симулација изолованих догађаја (en:Discrete event simulation)
• Ред са приоритетима

Референце

• 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. стр. 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.

Спољашње везе

• Јава аплет који симулира биномни хип
• Имплементација биномног хипа у програмском језику Пајтон
• Две имплементације биномног хипа у програмском језику C (општи и оптимизован за целобројне кључеве)
• Имплементација биномног хипа у програмском језику Хаскел
• Имплементација биномног хипа у програмском језику Common Lisp