هرم مورب

هیپ‌های مورب با استفاده از الگوریتم بازگشتی زیر تعریف می‌شوند:

• یک هیپ با تنها یک عنصر، هیپ مورب است.
• ادغام دو هیپ مورب، یک هیپ مورب تولید می‌کند.

ادغام دو هیپ مورب

می توان از الگوریتمی مشابه با ادغام دو درخت چپ‌گرا استفاده کرد:

• مقایسهٔ ریشهٔ دو هیپ؛ هیپ با ریشهٔ کوچکتر را p و هیپ دیگر را q در نظر می گیریم. هیپ حاصل را نیز r می نامیم.
• ریشهٔ هیپ r را برابر با ریشهٔ p (ریشهٔ کوچکتر)، و به جای زیردرخت راست r، زیردرخت چپ p را قرار می دهیم.
• زیردرخت چپ r را با ادغام زیردرخت راست p و هیپ q به صورت بازگشتی محاسبه می کنیم.

قبل :

بعد :

ادغام غیربازگشتی

یک الگوریتم غیربازگشتی هم وجود دارد، که طولانی تر است و در ابتدا به مرتب سازی نیاز دارد.

• هر هیپ را با جدا کردن سمت راست‌ترین مسیر به چند زیردرخت تقسیم می کنیم. (با شروع از ریشه، گرهٔ سمت راست را جدا کرده و فرزند راست آن را زیردرختش قرار می دهیم.) با این روش، مجموعه ای از درخت‌ها تولید می‌شوند که ریشهٔ آن‌ها فقط فرزند چپ دارد یا اصلاً فرزند ندارد.
• زیردرخت‌ها را به ترتیب صعودی مقادیر ریشه‌شان مرتب می کنیم.
• از سمت راست دو زیردرخت آخر را با هم ادغام می کنیم و این کار را تکرار می کنیم تا زمانی که به یک درخت برسیم.
  • اگر ریشهٔ زیردرخت یکی مانده به آخر، فرزند چپ داشته باشد، آن را با فرزند راست جا به جا می کنیم.
  • ریشهٔ آخرین زیردرخت را به جای فرزند چپ زیردرخت یکی مانده به آخر قرار می دهیم.

افزودن مقادیر

اضافه کردن یک مقدار جدید به هیپ مورب، مانند ادغام آن هیپ با یک هیپ تک عضوی است.

حذف مقادیر

حذف اولین مقدار در یک هیپ مانند حذف ریشه و ادغام دو زیردرخت آن است.

پیاده سازی

در بسیاری از زبان های برنامه نویسی که دارای تابع هستند، پیاده‌سازی هیپ مورب بسیار ساده است. قطعه کد زیر، پیاده‌سازی کامل این داده ساختار به زبان 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)

• Sleator, Daniel Dominic; Tarjan, Robert Endre (1986). "Self-Adjusting Heaps". SIAM Journal on Computing. 15 (1): 52–69. doi:10.1137/0215004. ISSN 0097-5397.
• CSE 4101 lecture notes, York University

• Animations comparing leftist heaps and skew heaps, York University
• Java applet for simulating heaps, Kansas State University