Hip (struktura podataka)

Из Википедије, слободне енциклопедије
Min-max heap.jpg

U kompjuterskim naukama, hip je struktura podataka organizovana po principu stabla koja mora da zadovoljava uslov hipa: ključ svakog čvora je veći ili jednak od ključeva njihovih sinova. Kada je maksimalan broj dece jednog čvora dva, to je binarni hip.

Hip je izuzetno bitan u nekim algoritmima, kao što je Dijkstra algoritam i hipsort. Hip je veoma korisna struktura podataka kada treba da se ukloni čvor najvišeg ili najnižeg prioriteta.

Čvor je jedna memorijska jedinica i sadrži kljuc tj, podatak. Svaki čvor ima svog pretka, sem korena stabla koji predstavlja vrh hijerarhije. Ako je čvor A predak cvora B, onda je B potomak od A. Čvor bez potomaka se zove list, a čvor koji nije list se zove unutrašnji čvor. Ključ svakog čvora je uvek veci ili jednaki od kljuceva njegovih potamaka i najveci kljuc je u korenu stabla. Ne postoji posebna veza između čvorova na istom nivou ili braće. Kako je hip binarno stablo,ima najmanju moguću visinu - O(log n) za hip sa n čvorova. Kako između braće ne postoji veza i čvor je direktno vezan samo sa roditeljem i decom (prvim pretkom i potomcima), ne postoji mogućnost za obilazak stabla.

Hip je maksimalno efikasna implementacija apstraktnog tipa podataka koji se zove red sa prioritetom. U stvari redove sa prioritetom cesto nazivaju "hipom", bezobzira na to kako su implemetirani. Uprkos sličnosti imena "hip" sa imenima "stek" i "red",druga dva su apstraktni tip podataka, dok je hip specifična struktura podataka i "red sa prioritetom" je pogodan naziva sa apstraktni tip podataka.

Heap sort example.gif

Operacije u hipu[уреди]

Operacije uklanjanja i umetanja elementa se obavljaju tako da se prvo zadovolji svojstvo oblika dodavanjem ili uklanjanjem čvora sa dna stabla, a zatim se sređuje svojstvo hipa kretanjem po hipu. Obe operacija zahtevaju vremensku složenost O(log n), što znači da se efikasno izvršavaju.Nedostatak hipa je što se traženje ključa ne može izvršiti tako jednostavno. Smatraćemo da su ključevi čvorova hipa smešteni u vektor A,dok je n broj elemenata hipa. Elementi su na indekisama od 1 do n.

Umetanje[уреди]

  1. Broj n se uveća za jedan i novi element se upiše na slobodnu poziciju A[n]
  2. Upoređujemo taj ključ i ključ elementa na poziciji A[i],gde je i=⌊n/2⌋,pa ako je veći od njega,menjaju im se mesta
  3. Postupak se nastavlja premeštanjem ključa naviše,sve dok n bude manji ili jednak od oca
  4. Induktivna hipoteza: Ako je umetnuti ključ nakon premeštanja u čvoru A[j], onda je to koren ispravnog hipa i ako se to podtsablo ukloni,ostatak stabla zadovoljava uslov hipa
Konstruktion Heap.jpg

Uklanjanje elementa sa navećim ključem[уреди]

  1. ključ najvećeg elementa je A[1], pa ga je lako naći
  2. zamenimo elemente A[n] i A[1]
  3. n smanjimo za jedan
  4. x=A[1] a y=max{A[2], A[3]}(veći od sinova korena)
  5. ako je x ≥ y,onda je kompletno stablo ispravan hip
  6. inace,posle zamene ključeva elemenata x i y,,podstablo sa nepromenjenim korenom ostaje ispravan hip,a u drugom podstablu je promenjen koren
  7. rekurzivno se sređuje podtsablo
  8. induktivna hipoteza: ako je posle i koraka x na poziciji A[j],onda samo podstablo sa korenom A[j] eventualno ne zadovoljava uslov hipa. Dalje se x upoređuje sa A[2j] i A[2j+1] i dalje se zamenjuju mesta ako treba.
Heap delete step0.svg
Heap remove step1.svg
Heap remove step2.svg

Vrste hipa[уреди]

  • 2-3 hip
  • B-hip
  • Beap
  • Binarni hip
  • Binomni hip
  • Brodal red
  • d hip
  • Fibonači hip
  • Leftist hip
  • Pairing hip
  • Skew hip
  • Soft hip
  • Weak hip
  • Leaf hip
  • Radix hip
  • Randomized meldable hip
  • Ternary hip
  • Treap

Poređenje teoretskih granica za varijante[уреди]

O(f) daje asimtotsku gornju granicu i Θ(f) je asimptotski bliska granica(pogledati notaciju veliko O). Radi se sa min-hipom.

Operacija Binarni hip Binomni hip Fibonači hip Pairing hip[1] Brodal red [2][3]}} Rank-pairing[4]
naći min Θ(1) Θ(1) Θ(1) Θ(1) Θ(1) Θ(1)
izbriši min Θ(log n) Θ(log n) O(log n) O(log n) O(log n) O(log n)
ubaci Θ(log n) O(log n) Θ(1) Θ(1) Θ(1) Θ(1)
smanji ključ Θ(log n) Θ(log n) Θ(1) O(log n) Θ(1) Θ(1)
spajanje Θ(n) O(log n) Θ(1) Θ(1) Θ(1) Θ(1)


Implementacija hipa[уреди]

Hip se može realizovati eksplicitno ili implicitno zadatim stablom.Eksplicitno znači da se koristi struktura podataka koja sadrži ključ i pokazivače ka sinovima(i nekada ka ocu).Implicitno znači da se čvorovi stavljaju u niz i da su njihove veze određene njihovom pozicijom u vektoru.

Heap Array.jpg

Implementacija pomoću niza[уреди]

Svako binarno stablo može biti sačuvano preko niza, ali pošto je binarni hip skoro uvek kompletno binarno stablo,implementacija pomoću niza,bez pokazivača je pogodna.Pozicija korena moze biti na indexu 0 ili 1.Sledeća dva elementa će da sadrže njegovu decu.Sledeća četiri decu od dva čvora koji su deca od korena itd. Tako da će deca čvora na poziciji n biti na poziciji 2n i 2n+1. Ovo omogućava pomeranje elemenata koristeći proračune indexa.Balansiranje hipa se radi zamenjivanjem elemenata koji nisu na mestu.Kako možemo da napravimo hip od niza bez korišćenja dodatne memorije(za čvorove npr),hipsort može da bude korišćen za sortiranje nizova u mestu. 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.


Primena[уреди]

  • Heapsort: Jedan od najboljih metoda za sortiranje u mestu bez kvadratne složenosti za najgore slučajeve.
  • Algoritem izbora: Hip dozvoljava pristup najvećem i najmanjem elementu u konstantnom vremenu,a ostalim selekcijama (kao što su medijana i k-ti element) u sub-linearnom vremenu nad podacima koji su u hipu.[5]
  • Grefovski algoritmi:Koristeći hip kao internu strukturu podataka, vreme izvršavanja može biti smanjeno polinomijano. Primari takvih problema su Primov algoritam i Dijkstrin algoritam.
  • Red sa prioritetom: Red sa prioritetom je apstraktni koncept kao "lista" ili "mapa";Kao što lista može biti implemetirana povezanom listom ili kao niz,red sa prioritetom može biti implemetiran pomoću hipa ili drugih metoda.
  • Statistika reda: Struktura podataka heap može da se koristi za efikasno pronalaženje k-tog najmanjeg (ili najvećeg) elementa u nizu.


Reference[уреди]

  1. ^ Iacono, John (2000), „Improved upper bounds for pairing heaps“, Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, 1851, Springer-Verlag, pp. 63–77, DOI:10.1007/3-540-44985-X_5 
  2. ^ http://www.cs.au.dk/~gerth/papers/soda96.pdf
  3. ^ Goodrich, Michael T.; Tamassia, Roberto (2004). „7.3.6. Bottom-Up Heap Construction“. Data Structures and Algorithms in Java (3rd ed.). стр. 338–341. 
  4. ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2009). „Rank-pairing heaps“. SIAM J. Computing: 1463–1485. 
  5. ^ Frederickson, Greg N. (1993), „An Optimal Algorithm for Selection in a Min-Heap“, Information and Computation, 104, Academic Press, pp. 197–214, DOI:10.1006/inco.1993.1030 

Spoljašnje veze[уреди]

Викикњиге
Викикњиге имају више информација о: