Skew hip

Skew hip ili samopodešavajući hip je hip struktura podataka implementirana kao binarno stablo. Skew hip su korisniji jer imaju sbosobnost da se brže spajaju od drugih binarnih hip-ova. Nasuprot binarnim hip-ovima, nema nikakva strukturna ograničenja, tako da nema nikakve garancije da je visina stabla logaritamska.

Samo dva uslova moraju da budu zadovoljena:

• Opšti hip redosled mora da bude primenjen
• Svaka operacija (dodaj, ukloni_najmanji, spoji) na dva "skew" hipa mora da da se uradi pomoću specijalnog ""skew" hip spajanja".

"Skew" hip je samopodešavajuća forma leftist hipa koji pokušava da održi balans tako sto bezuslovno razmenjuje sve čvorove u prosecesu spajanjna dva hipa.(Operacija spajanja se takođe koristi kada se dodaju i uklanjaju vrednosti.)

Bez strukturnih ogranicenja može da deluje kao da je "Skew" hip poprilično neefikasan. Međutim analiza amortizovane složenosti može da se iskoristi da se pokaže da sve operacije "skew" hip-a mogu da se urade u O(logn).

Operacije

Spajanje dva hip-a

Kada se dva skju hip-a spajaju možemo da koristimo sličan proces kao sa spajanjem leftist hip-a:

• Poredimo korene oba hip-a; p će da bude hip sa manjim korenom, a k će da bude hip sa vecim korenom. Rezultujući hip ćemo nazvati r.
• Neka koren r bude koren iz p i neka desno podstablo od r bude levo podstablo od p.
• Sada izračunati levo podstablo od r tako što rekurzivno spajamo p-ovo desno podstablo sa k-ovim.

Pre:

Posle:

Ne rekurzivno spajanje

Alternativno postoji ne rekurzivan pristup koji je vredniji i zahteva neka sortiranja od početka.

• Podeliti svaki hip na podstabla tako sto se iseče svaki krajnji desni put. (Od korenskog čvora iseći desni čvor i napraviti desnom sinu njegovo podstablo) Rezultat će biti set stabala kojima će koren imati ili samo levog sina ili neće imati uopšte.
• Sortirati podstabla u rastućem poretku po vrednostima korena vakog podstabla.
• Dok još uvek ima više podstabala iterativno spajamo poslednja dva(od desno ka levo).
  • Ako koren od pretposlednjeg podstabala ima levog sina zameniti ga da bude desni sin.
  • Povezati koren sa poslenjim podstablom kao levi sin pretposlednjeg podstabla.

Dodavanje vrednosti

Dodavanje vrednosti hipu je kao spajanje stabla sa čvorom zajedno sa originalin stablom.

Uklanjanje vrednosti

Uklanjanje prve vrednosti hipa može da se postigne uklanjanjem korena i spajanjem njegovim podstablima.

Implementacija

U mnogim funkcionalin jezicima skew hip postaje ekstremno jednostavan za implementaciju. Evo jednog kompletnog primera implementacije u Haskell-u.

data SkewHeap a = Empty
                | Node a (SkewHeap a) (SkewHeap a)

singleton :: Ord a => a -> SkewHeap a
singleton x = Node x Empty Empty

union :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a
Empty `union` t2 = t2
t1 `union` Empty = t1
t1@(Node x1 l1 r1) `union` t2@(Node x2 l2 r2)
   | x1 <= x2                                 = Node x1 (t2 `union` r1) l1
   | otherwise                                = Node x2 (t1 `union` r2) l2

insert :: Ord a => a -> SkewHeap a -> SkewHeap a
insert x heap = singleton x `union` heap

extractMin :: Ord a => SkewHeap a -> Maybe (a, SkewHeap a)
extractMin Empty = Nothing
extractMin (Node x l r) = Just (x, l `union` r)