هرم مورب

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

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

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

ممکن است هیپ مورب به دلیل نداشتن محدودیت‌های ساختاری، نامناسب و غیرمفید به نظر بیاید. اگرچه، با استفاده از تحلیل سرشکنی می‌توان نشان داد که تمام عملیات روی هیپ مورب را می‌توان در (O(logn انجام داد.[۱]

تعریف

[ویرایش]

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

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

عملیات

[ویرایش]

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

[ویرایش]

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

  • مقایسهٔ ریشهٔ دو هیپ؛ هیپ با ریشهٔ کوچکتر را 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
  1. ↑ «نسخه آرشیو شده» (PDF). بایگانی‌شده از اصلی (PDF) در ۱۴ نوامبر ۲۰۱۴. دریافت‌شده در ۱۹ مه ۲۰۱۴.

پیوند به بیرون

[ویرایش]