Биномни хип

Из Википедије, слободне енциклопедије

У Информатици, биномни хип је хип, сличан бинарном хипу, који подржава брзо спајање 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 (погледај слику испод).

Example of a binomial heap
Пример биномног хипа који садржи 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), као што је изнад већ објашњено.

Употреба[уреди]

Референце[уреди]

Спољашње везе[уреди]