Skew хип

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

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

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

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

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

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

Операције[уреди]

Спајање два хип-а[уреди]

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

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

Pre: SkewHeapMerge1.svg

Posle: SkewHeapMerge7.svg

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

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

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

SkewHeapMerge1.svg

SkewHeapMerge2.svg

SkewHeapMerge3.svg

SkewHeapMerge4.svg

SkewHeapMerge5.svg

SkewHeapMerge6.svg

SkewHeapMerge7.svg

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

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

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

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

Имплементација[уреди]

У многим функционалин језицима 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)