Skew хип

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=.

Skew hip или самоподешавајући хип је хип структура података имплементирана као бинарно стабло. Skew hip су кориснији јер имају сбособност да се брже спајају од других бинарних хип-ова. Насупрот бинарним хип-овима, нема никаква структурна ограничења, тако да нема никакве гаранције да је висина стабла логаритамска.

Само два услова морају да буду задовољена:

• Општи хип редослед мора да буде примењен
• Свака операција (додај, уклони_најмањи, споји) на два "skew" хипа мора да да се уради помоћу специјалног ""skew" хип спајања".

"Skew" хип је самоподешавајућа форма лефтист хипа који покушава да одржи баланс тако сто безусловно размењује све чворове у просецесу спајањна два хипа.(Операција спајања се такође користи када се додају и уклањају вредности.)

Без структурних ограницења може да делује као да је "Skew" хип поприлично неефикасан. Међутим анализа амортизоване сложености може да се искористи да се покаже да све операције "skew" хип-а могу да се ураде у O(logn).

Операције

Спајање два хип-а

Када се два скју хип-а спајају можемо да користимо сличан процес као са спајањем лефтист хип-а:

• Поредимо корене оба хип-а; п ће да буде хип са мањим кореном, а к ће да буде хип са вецим кореном. Резултујући хип ћемо назвати р.
• Нека корен р буде корен из п и нека десно подстабло од р буде лево подстабло од п.
• Сада израчунати лево подстабло од р тако што рекурзивно спајамо п-ово десно подстабло са к-овим.

Pre:

Posle:

Не рекурзивно спајање

Алтернативно постоји не рекурзиван приступ који је вреднији и захтева нека сортирања од почетка.

• Поделити сваки хип на подстабла тако сто се исече сваки крајњи десни пут. (Од коренског чвора исећи десни чвор и направити десном сину његово подстабло) Резултат ће бити сет стабала којима ће корен имати или само левог сина или неће имати уопште.
• Сортирати подстабла у растућем поретку по вредностима корена ваког подстабла.
• Док још увек има више подстабала итеративно спајамо последња два(од десно ка лево).
  • Ако корен од претпоследњег подстабала има левог сина заменити га да буде десни син.
  • Повезати корен са послењим подстаблом као леви син претпоследњег подстабла.

Додавање вредности

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

Уклањање вредности

Уклањање прве вредности хипа може да се постигне уклањањем корена и спајањем његовим подстаблима.

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

У многим функционалин језицима skew хип постаје екстремно једноставан за имплементацију. Ево једног комплетног примера имплементације у Haskell-у.

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)