هیپ مورب

یک هیپ مورب (یا خود سازگار شونده ) یک داده ساختار به صورت هیپ است که مانند یک درخت دودویی پیاده سازی شده است. هیپ‌های مورب در مقایسه با هیپ‌های دودویی با سرعت بیشتری ادغام می‌شوند. برخلاف هیپ‌های دودویی، هیچ محدودیتی در ساختار هیپ مورب وجود ندارد، در نتیجه هیچ تضمینی نیست که ارتفاع درخت از مرتبه‌ی لگاریتمی باشد.
تنها دو شرط باید در هیپ مورب برقرار باشد:
مرتبه‌ی کلی هیپ باید داده شده باشد.
هر عملیاتی که روی دو هیپ مورب قابل انجام است (مانند جمع، حذف عنصر کمینه و ادغام)، باید با استفاده از یک الگوریتم خاص برای ادغام انجام شود.
هیپ مورب، یک نوع درخت چپ‌گرا است که از طریق جا به جایی همه‌ی گره‌ها هنگام ادغام، تعادل هیپ را حفظ می‌کند. (عملیات ادغام همچنین در جمع و حذف مقادیر به کار برده می‌شود.)
ممکن است هیپ مورب به دلیل نداشتن محدودیت‌های ساختاری، نامناسب و غیرمفید به نظر بیاید. اگرچه، با استفاده از تحلیل سرشکنی می‌توان نشان داد که تمام عملیات روی هیپ مورب را می‌توان در (O(logn انجام داد.
تعریف
هیپ‌های مورب با استفاده از الگوریتم بازگشتی زیر تعریف می‌شوند:
یک هیپ با تنها یک عنصر، هیپ مورب است.
ادغام دو هیپ مورب، یک هیپ مورب تولید می‌کند.
عملیات
ادغام دو هیپ مورب
می‌توان از الگوریتمی مشابه با ادغام دو درخت چپ‌گرا استفاده کرد:
مقایسه‌ی ریشه‌ی دو هیپ؛ هیپ با ریشه‌ی کوچکتر را p و هیپ دیگر را q در نظر می‌گیریم. هیپ حاصل را نیز r می‌نامیم.
ریشه‌ی هیپ r را برابر با ریشه‌ی p (ریشه‌ی کوچکتر)، و به جای زیردرخت راست r، زیردرخت چپ p را قرار می‌دهیم.
زیردرخت چپ r را با ادغام زیردرخت راست p و هیپ q به صورت بازگشتی محاسبه می‌کنیم.
قبل :
پرونده:SkewHeapMerge1.svg
بعد :
پرونده:SkewHeapMerge7.svg
ادغام غیربازگشتی
یک الگوریتم غیربازگشتی هم وجود دارد، که طولانی‌تر است و در ابتدا به مرتب سازی نیاز دارد.
هر هیپ را با جدا کردن سمت راست‌ترین مسیر به چند زیردرخت تقسیم می‌کنیم. (با شروع از ریشه، گره‌ی سمت راست را جدا کرده و فرزند راست آن را زیردرختش قرار می‌دهیم.) با این روش، مجموعه‌ای از درخت‌ها تولید می‌شوند که ریشه‌ی آن‌ها فقط فرزند چپ دارد یا اصلا فرزند ندارد.
زیردرخت‌ها را به ترتیب صعودی مقادیر ریشه‌شان مرتب می‌کنیم.
از سمت راست دو زیردرخت آخر را با هم ادغام می‌کنیم و این کار را تکرار می‌کنیم تا زمانی که به یک درخت برسیم.
اگر ریشه‌ی زیردرخت یکی مانده به آخر، فرزند چپ داشته باشد، آن را با فرزند راست جا به جا می‌کنیم.
ریشه‌ی آخرین زیردرخت را به جای فرزند چپ زیردرخت یکی مانده به آخر قرار می‌دهیم.
پرونده:SkewHeapMerge1.svg
پرونده:SkewHeapMerge2.svg
پرونده:SkewHeapMerge3.svg
پرونده:SkewHeapMerge4.svg
پرونده:SkewHeapMerge5.svg
پرونده:SkewHeapMerge6.svg
پرونده:SkewHeapMerge7.svg
افزودن مقادیر
اضافه کردن یک مقدار جدید به هیپ مورب، مانند ادغام آن هیپ با یک هیپ تک عضوی است.
حذف مقادیر
حذف اولین مقدار در یک هیپ مانند حذف ریشه و ادغام دو زیردرخت آن است.
پیاده سازی
در بسیاری از زبان‌های برنامه نویسی که دارای تابع هستند، پیاده سازی هیپ مورب بسیار ساده است. قطعه کد زیر، پیاده سازی کامل این داده ساختار به زبان 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
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)