Binarni hip

Binarni hip (енгл. binary heap) je hip struktura podataka organizovana po principu binarnog stabla. Može se posmatrati kao binarno stablo sa dva dodatna ograničenja:

Svojstvo oblika: Stablo je kompletno binarno stablo ako svi nivoi stabla, osim možda poslednjeg, u potpunosti popunjeni, a u slučaju da poslednji nivo stabla nije popunjen, čvorovi tog nivoa se popunjavaju s leva na desno.
Svojstvo hipa: Svi čvorovi su ili “veći ili jednaki” ili “manji ili jednaki” od svakog čvora koji mu je dete u zavisnosti od toga koja funkcija za poređenje se koristi u implementaciji.

Stablo sa funkcijom za poređenje “veće ili jednako” (≥) se zove max-heap, a sa funkcijom za poređenje “manje ili jednako” (≤) se zove min-heap. Min-heap se koristi za primenu redova sa prioritetom. ^[1]^[2]

Pošto red rođaka u hipu nije specifikovan svojstvima hipa, dva deteta jednog čvora mogu biti slobodno zamenjena, osim ako to ne narušava svojstvo oblika.

Binarni hip je poseban primer n-arnog hipa gde je n=2.

Operacije u hipu

I operacija umetanja i operacija uklanjanja modifikuju hip tako da se prvo zadovolji svojstvo oblika dodavanjem ili uklanjanjem čvora sa dna stabla, a zatim se realizuje svojstvo hipa poprečnim kretanjem po hipu. I jedna i druga operacija zahtevaju vremensku složenost O(log n).

Umetanje

Da bi se element dodao u stablo moramo obaviti up-heap operaciju (takođe: bubble-up, percolate-up, sift-up, trickle-up, cascade-up) prateći sledeći algoritam:

Dodaj element u donji nivo stabla
Uporedi dodati element sa njegovim roditeljem; ako su u ispravnom redosledu stani
Ako ne, zameni ubačeni element sa njegovim roditeljem i vrati se na prethodni korak.

Broj potrebnih operacija zavisi od broja nivoa koje novi element mora da pređe da bi zadovoljio svojstvo hipa pa zato operacija umetanja ima vremensku složenost O(log n). Međutim, 1974.godine [Tomas Porter] i [Istvan Sajmon] dokazali su da funkcija za prosečan broj nivoa koje jedan ubačen cvor pređe ima gornju granicu - konstantu 1.6067.^{[тражи се извор]} Prosečan broj potrebnih operacija za umetanje u binarno stablo je 2.6067 jer je obavljeno jedno dodatno poređenje koje ne rezultuje pomeranjem ubačenog čvora za jedan nivo nagore. Stoga, u proseku, umetanje u binarno stablo ima konstantnu vremensku složenost, O(1). Ovo ima smisla jer približno 50% elemenata čini lišće stabla, a približno 75% elemenata se nalazi na donja dva nivoa. Vrlo je verovatno da će se podaci koje treba ubaciti pomaći za nekoliko nivoa nagore da bi se stablo održalo.

Kao primer umetanja podataka u binarno stablo uzećemo max-heap:

Ako želimo da ubacimo broj 15 u stablo, treba prvo da postavimo broj na mesto koje označava X. Međutim, osobina stabla je narušena jer je 15 veće od 8, tako da treba da im zamenimo mesta. Dobijamo stablo koje, nakon prve zamene, izgleda ovako:

Osobina stabla je i dalje narušena jer je 15 veće od 11, tako da je potrebna još jedna zamena:

Dobijamo ispravno max-heap stablo. Nakon ovoga, nema potrebe da proveravamo decu. Pre nego što smo postavili 15 na označeno mesto, stablo je bilo ispravno, odnosno 11 je veće od 5. Ako je 15 veće od 11, a 11 veće od 5, onda i 15 mora biti veće od 5 zbog principa prelaznosti.

Brisanje

Postupak brisanja korena iz hipa (efikasno uklanjanje maksimalne vrednosti kada je u pitanju max-heap ili minimalne kada je u pitanju min-heap) i obnavljanje osobina se zove down-heap (takođe: bubble-down, percolate-down, sift-down, heapify-down, extract-min/max). To se radi po slede'em algoritmu:

Zameni koren hipa poslednjim elementom na poslednjem nivou
Uporedi novi koren sa njegovom decom; ako su u pravilnom poretku stani
Ako ne, zameni element sa jednim od njegove dece i vrati se na prethodni korak. (Zameni najmanjim detetom za min-heap i najvećim za max-heap)

Zatim, ukoliko imamo isti max-heap kao i pre

Uklanjamo 11 i postavljamo 4.

Sada je osobina stabla narušena jer je 8 veće od 4. U ovom slučaju, zamena ova dva elementa, 4 i 8, biće dovoljna da vrati svojstvo stabla tako da je dodatna zamena nepotrebna.

Unos koji se kretao prema dole menjan je većim među decom za max-heap (za min-heap bio bi zamenjen najmanjim detetom), sve dok njegova nova pozicija nije ispunila uslov normalnog poretka u hipu. Ova funkcionalnost postignuta je Max-Heapify funkcijom kao što je dole definisano u pseudokodu za hip zasnovano na nizu A dužine: heap_length[A]. Primetićete da je “A” indeksirano od 1, a ne od 0 kao što je čest slučaj kod mnogih stvarnih programskih jezika.

Max-Heapify^[3] (A, i):

  left ← 2i
  right ← 2i + 1
  largest ← i
  if left ≤ heap_length[A] and A[left] > A[largest] then:
     largest ← left
  if right ≤ heap_length[A] and A[right] > A[largest] then:
     largest ← right
  if largest ≠ i then:
    swap A[i] ↔ A[largest]
    Max-Heapify(A, largest)

Da bi ovaj algoritam ispravno preuredio niz, cvor sa indeksom i i njegova direktna dva deteta moraju da naruše svojstvo hipa. Ukoliko ne naruše svojstvo hipa, algoritam će biti sproveden bez ikakvih promena u nizu. Operacija down-heap (bez prethodne zamene) može takođe biti upotrebljena da bi se modifikovala vrednost korena, čak i ako element nije izbrisan. U najgorem slučaju, novi koren mora biti zamenjen svojim detetom na svakom nivou sve dok ne spadne na donji nivo hipa, što znači da operacija brisanja ima vremensku složenost koja je povezana sa visinom stabla, ili O(log n).

Izgradnja stabla

Hip može biti izgrađen uzastopnim ubacivanjem. Ovaj pristup zahteva $O(n\log n)$ vremena jer svaki unos zahteva $O(\log n)$ vremena, a postoji n elemenata. Međutim, ovo nije optimalni metod. Optimalni metod počinje proizvoljnim dodavanjem elemenata u binarno stablo, prateći svojstvo oblika (stablo može biti predstavljeno kao niz). Zatim, krećući od najnižeg nivoa prema višim, zameniti koren svakog podstabla prema dole kao u algoritmu za brisanje sve dok se svojstvo hipa ne obnovi. Tačnije, ako je svako podstablo koje se nalazi na istoj visini $h$ (mereno sa dna) već nagomilano (енгл. heapified), onda stabla na visini $h+1$ mogu biti nagomilana (енгл. heapify) pomeranjem korena prema dole prateći putanju dece sa najvećim vrednostima kao kada se pravi max-heap ili putanju dece minimalnih vrednosti ako je u pitanju min-heap. Ovaj proces zahteva $O(h)$ operacija (zamena) po čvoru. U ovom metodu najviše gomilanja (енгл. heapification) se odvija na nižim nivoima. Pošto je visina hipa $\left\lfloor \lg(n)\right\rfloor$ , broj čvorova na visini $h$ je $\leq \left\lceil 2^{\left(\lg n-h\right)-1}\right\rceil =\left\lceil {\frac {2^{\lg n}}{2^{h+1}}}\right\rceil =\left\lceil {\frac {n}{2^{h+1}}}\right\rceil$ . Stoga, cena gomilanja svih podstabala je:

{\begin{aligned}\sum _{h=0}^{\lceil \lg n\rceil }{\frac {n}{2^{h+1}}}O(h)&=O\left(n\sum _{h=0}^{\lceil \lg n\rceil }{\frac {h}{2^{h+1}}}\right)\\&\leq O\left(n\sum _{h=0}^{\infty }{\frac {h}{2^{h}}}\right)\\&=O(n)\end{aligned}}

Ovo koristi činjenicu da zadati beskonačni niz h / 2^h ima graničnu vrednost 2. Tačna vrednost ove jednačine (najveći mogući broj poređenja tokom izgradnje hipa) jednak je:

2n-2s_{2}(n)-e_{2}(n)

,^[4]

gde ₂(n) predstavlja zbir svih cifara n binarnog sistema, a e₂(n) predstavlja eksponent 2 u osnovnom razlaganju na proste činioce.

Funkcija Build-Max-Heap koja sledi, pretvara niz A u kojem je sačuvano kompletno binarno stablo sa n cvorova u max-heap tako što iznova koristi Max-Heapify funkciju po principu od dna ka vrhu. Ovo je zasnovano na zaključku da je svaki element niza indeksiran sa floor(n/2) + 1, floor(n/2) + 2, ..., n predstavlja lišće jednog stabla, tako da svaki predstavlja hip sa samo jednim elementom. Build-Max-Heap sprovodi Max-Heapify na svakom od preostalih čvorova stabla.

Build-Max-Heap^[3] (A):

  heap_length[A] ← length[A]

  for i ← floor(length[A]/2) downto 1 do

    Max-Heapify(A, i)

Implementacija hipa

Hipovi se uglavnom implementiraju zajedno sa nizom. Svako binarno stablo može biti sačuvano preko niza, ali pošto je binarni hip skoro uvek kompletno binarno stablo, ono može biti sačuvano i kompaktno. Pokazivači nisu potrebni. Umesto toga, roditelj i deca svakog cvora mogu biti pronađeni putem aritmetike u indeksima niza. Ove karakteristike čine ovakvu primenu stabla jednostavnim primerom jedne implicitne strukture podataka ili Ahnentafel listu. Detalji zavise od pozicije korena, a koren može da zavisi od ograničenja programskog jezika korišćenog za implementaciju ili od programerovog izbora. Ponekad je koren postavljen sa indeksom 1, žrtvujući na taj način prostor samo da bi se pojednostavila aritmetika. Operacija peek za pronalaženje minimalnih/maksimalnih vrednosti jednostavno vraća vrednost korena, te stoga iznosi O(1).

Neka je n broj elemenata u stablu a i proizvoljni ispravni indeks niza po kome je stablo sačuvano. Ukoliko je koren stabla indeks 0, sa ispravnim indeksima 0 do n – 1, onda svaki element a sa indeksom i ima

Decu sa indeksom 2i + 1 i 2i + 2
Njihove roditelje ⌊(i − 1) ∕ 2⌋ gde je ⌊…⌋ floor funkcija koja mapira realan broj do najvećeg prethodnog ili najmanjeg sledećeg celog broja.

U drugom slučaju, kada je koren stabla na indeksu 1 sa ispravnim indeksima 1 do n, onda svaki element a sa indeksom i ima:

Decu sa indeksima 2i i 2i +1
Njihove roditelje sa indeksom ⌊i ∕ 2⌋.

Ova implementacija se koristi kod hipsort algoritma za sortiranje gde je dozvoljeno da se prostor u ulazni niz ponovo iskoristi za čuvanje hipa. Algoritam vrši sortiranje u mestu). Implementacija je takođe korisna kao i red sa prioritetom gde korišćenje dinamičkog niza dozvoljava ubacivanje neograničenog broja članova.

Operacije upheap/downheap mogu biti izražene po principu niza na sledeći način: pretpostavimo da osobina hipa zadržava indekse b, b+1, …, e. Funkcija sift-down proširuje osobinu hipa na b-1, b, b+1, …, e. Samo indeks i = b-1 može da naruši karakteristike hipa. Neka je j indeks najvećeg deteta a[i] za max-heap, ili najmanjeg deteta za min-heap u rasponu od b ,…, e. Ako ne postoji takav indeks jer je 2i > e onda se karakteristike hipa čuvaju i za novi nivo i nema potrebe da se bilo šta menja. Menjanjem vrednosti a[i] za a[j] karakteristike za poziciju i su utvrđene. U ovom trenutku, jedini problem je to što karakteristika hipa možda neće sačuvati indeks j. Funkcija sift-down se primenjuje rep-rekurzivno na indeks j sve dok karakteristike hipa ne postanu ispravne za sve elemente.

Funkcija sift-down je brza. U svakom koraku obavlja dva poređenja i jednu zamenu. Indeksna vrednost o kojoj se radi se duplira svakim ponavljanjem tako da je najviše log₂ e koraka potrebno.

Za velike hipove i za korišćenje virtuelne memorije, čuvanje elemenata u nizu prateći prethodnu šemu nije efikasno: skoro svaki nivo se nalazi na drugoj strani. B-heap B-heap je binarni hip koji čuva sva podstabla na jednoj strani, tako da je za deset puta manji broj strana kojima se pristupa.^[5]

Operacija spajanja dva binarna hipa zahteva Θ(n) vremena u slučaju izjednačenih hipova. Najbolje što možete da uradite (za slučaj primene niza) je da jednostavno spojite dva hipa sa nizom i dobijete stablo koje ste tražili.^[6] Hip sa n elementima može biti spojen sa hipom od k elementima korišćenjem O(log n log k) poređenja, ili u slučaju implementacije zasnovane na pokazivačima za O(log n log k) vremena.^[7] Algoritam za razdvajanje jednog hipa sa n elemenata na dva hipa sa k i n-k elemenata, zasnovan je na pravljenju kolekcije podhipova.^[8] Taj algoritam zahteva O(log n * log n) poređenja. Za spajanje hipova se koristi konceptualno jednostavan algoritam. Kada je spajanje učestali zadatak, preporučuje se drugačiji način implementacije stabla, kao što je binomijalni heap, koji može biti spojen za O(log n). vremena.

Binarni hip može biti implementiran u skladu sa tradicionalnim načinom čuvanja podataka, ali tu postoji problem sa pronalaženjem susednih elemenata na poslednjem nivou binarnog hipa prilikom dodavanja novog elementa. Ovaj element može biti određen algoritmički ili ubacivanjem dodatnih podataka u čvorove, koji se zovu vezom drveta - umesto čuvanja referenci na decu, čuvamo inorder naslednike čvora.

Moguće je modifikovati strukturu hipa tako da dozvoljava izdvajanje i najvećih i najmanjih elemenata za $O$ $(\log n)$ vremena.^[9]. Da bi se to postiglo, redovi se naizmenično prebacuju između minimalnog i maksimalnog hipa. Algoritmi su naizgled isti, osim što se pri svakom koraku moraju uzeti u obzir naizmenični redovi sa naizmeničnim poređenjima. Sprovođenje je skoro isto kao i kod normalnog hipa sa jednim pravcem. Ova ideja može se uopštiti za min-max-median hip.

Izvođenje indeksne jednačine

U hipu sa nizom, deca i roditelji čvorova mogu biti locirani izvođenjem jednačina sa indeksom čvora. Ovaj deo izvodi bitne jednačine za hip sa korenom koji ima indeks 0, sa dodatnim napomenama za hip sa korenom koji ima indeks 1. Da bismo izbegli zabune, definisaćemo nivo čvora kao njegovu udaljenost od korena, tako da sam koren zauzima nivo 0.

Čvorovi dece

Za opšti čvor lociran na indeksu (počevši od 0), prvo ćemo izvesti indeks desnog deteta, ${\text{right}}=2i+2$ . Neka je čvor $i$ lociran na nivou $L$ , s tim da svaki nivo $l$ sadrži tačno $2^{l}$ čvorova. Zatim, postoji tačno $2^{l+1}-1$ čvorova sadržanih u slojevima uključujući i sloj $l$ (razmislite o binarnom računanju: 0111...111 = 1000...000 – 1 ). Pošto je koren pozicioniran na nulu, $k$ -ti cvor će biti smešten na indeks $(k-1)$ . Svi ovi zaključci dovode do sledeće jednačine za indeks poslednjeg čvora na sloju l.

{\text{last}}(l)=(2^{l+1}-1)-1=2^{l+1}-2

Uzmimo $j$ -ti čvor nakon čvora $i$ na sloju L, tako da je

{\begin{alignedat}{2}i=&\quad {\text{last}}(L)-j\\=&\quad (2^{L+1}-2)-j\\\end{alignedat}}

Svaki od ovih $j$ -tih čvorova mora imati tačno 2 deteta, tako da treba da postoji $2j$ čvorova koji odvajaju desno dete čvora $i$ od kraja njegovog sloja ( $L+1$ )

{\begin{alignedat}{2}{\text{right}}=&\quad {\text{last(L + 1)}}-2j\\=&\quad (2^{L+2}-2)-2j\\=&\quad 2(2^{L+1}-2-j)+2\\=&\quad 2i+2\end{alignedat}}

kao što je zahtevano.

Ako primetimo da je levo dete bilo kog čvora uvek jednu poziciju ispred desnog deteta nekog od tih čvorova, dobićemo ${\text{left}}=2i+1$ .

Ako je koren lociran na indeksu 1 umesto na 0, poslednji čvor svakog nivoa je usled toga na indeksu $2^{l+1}-1$ . Koristeći ovo sve do kraja dobijamo ${\text{left}}=2i$ i ${\text{right}}=2i+1$ za hip sa korenom na indeksu 1.

Čvorovi roditelja

Svaki čvor je ili levo ili desno dete istog roditelja, tako znamo da li je sledeća jednačina tačna ili ne:

$i=2\times ({\text{parent}})+1$
$i=2\times ({\text{parent}})+2$

Zato je

{\text{parent}}={\frac {i-1}{2}}{\textbf {or}}{\frac {i-2}{2}}

Sada razmotrimo izraz $\left\lfloor {\dfrac {i-1}{2}}\right\rfloor$ .

Ako je čvor i levo dete, dobijamo rezultat istog trenutka, međutim, tačan rezultat dobijamo i ako je čvor i desno dete. U ovom slučaju, $(i-2)$ mora biti paran, a samim tim $(i-1)$ mora biti neparan.

{\begin{alignedat}{2}\left\lfloor {\dfrac {i-1}{2}}\right\rfloor =&\quad \left\lfloor {\dfrac {i-2}{2}}+{\dfrac {1}{2}}\right\rfloor \\=&\quad {\frac {i-2}{2}}\\=&\quad {\text{parent}}\end{alignedat}}

Stoga, bez obzira na to da li je čvor levo ili desno dete, njegov roditelj može biti pronađen putem jednačine:

{\text{parent}}=\left\lfloor {\dfrac {i-1}{2}}\right\rfloor

Reference

^ „heapq – Heap queue algorithm”. Python Standard Library.
^ „Class PriorityQueue”. Java™ Platform Standard Ed. 6.
^ ^а ^б Cormen, T. H.; al. (2001), Introduction to Algorithms (2nd изд.), Cambridge, Massachusetts: The MIT Press, ISBN 978-0-07-013151-4 Непознати параметар |name-list-style= игнорисан (помоћ)
^ Suchenek, Marek A. (2012), „Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program”, Fundamenta Informaticae, IOS Press, 120 (1): 75—92, doi:10.3233/FI-2012-751
^ Poul-Henning Kamp. "You're Doing It Wrong". ACM Queue. June 11, 2010.
^ Chris L. Kuszmaul. "binary heap" Архивирано на сајту Wayback Machine (8. август 2008). Dictionary of Algorithms and Data Structures, Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 November 2009.
^ J.-R. Sack and T. Strothotte "An Algorithm for Merging Heaps"^{[мртва веза]}, Acta Informatica 22, 171-186 (1985).
^ . J.-R. Sack and T. Strothotte "A characterization of heaps and its applications" Information and Computation Volume 86, Issue 1, May 1990, Pages 69–86.
^ Atkinson, M.D., J.-R. Sack, N. Santoro, and T. Strothotte (1. 10. 1986). „Min-max heaps and generalized priority queues.” (PDF). Programming techniques and Data structures. Comm. ACM, 29(10): 996–1000. Архивирано из оригинала (PDF) 27. 01. 2007. г. Приступљено 30. 03. 2014.

[1] „heapq – Heap queue algorithm”. Python Standard Library.

[2] „Class PriorityQueue”. Java™ Platform Standard Ed. 6.

[CLRS-3] а ^б Cormen, T. H.; al. (2001), Introduction to Algorithms (2nd изд.), Cambridge, Massachusetts: The MIT Press, ISBN 978-0-07-013151-4 Непознати параметар |name-list-style= игнорисан (помоћ)

[4] Suchenek, Marek A. (2012), „Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program”, Fundamenta Informaticae, IOS Press, 120 (1): 75—92, doi:10.3233/FI-2012-751

[5] Poul-Henning Kamp. "You're Doing It Wrong". ACM Queue. June 11, 2010.

[6] Chris L. Kuszmaul. "binary heap" Архивирано на сајту Wayback Machine (8. август 2008). Dictionary of Algorithms and Data Structures, Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 November 2009.

[7] J.-R. Sack and T. Strothotte "An Algorithm for Merging Heaps"^{[мртва веза]}, Acta Informatica 22, 171-186 (1985).

[8] . J.-R. Sack and T. Strothotte "A characterization of heaps and its applications" Information and Computation Volume 86, Issue 1, May 1990, Pages 69–86.

[sym-9] Atkinson, M.D., J.-R. Sack, N. Santoro, and T. Strothotte (1. 10. 1986). „Min-max heaps and generalized priority queues.” (PDF). Programming techniques and Data structures. Comm. ACM, 29(10): 996–1000. Архивирано из оригинала (PDF) 27. 01. 2007. г. Приступљено 30. 03. 2014.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]