هرم جفت‌شده

یک هیپ جفت شده یک نوع داده ساختار هیپ با پیاده سازی نسبتا ساده و عملکرد سرشکن شده ی عالی معرفی شده توسط Micheal Fredman، Robert Sedgewick، Daniel Sleator و Robert Tarjan در سال 1986 می باشد. هیپ های جفت شده ساختمان های درختی چند راهه میباشند که مانند هیپ مرتب شده اند و میتوانند هیپ های فیبوناچی ساده شده در نظر گرفته شوند. آن ها انتخابات قوی برای پیاده سازی الگوریتم هایی مانند الگوریتم پریم در نظر گرفته میشوند  و از توابع زیر پیروی میکنند (با فرض اینکه مین-هیپ باشند):

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

تحلیل پیچیدگی زمانی هیپ های جفت شده ابتدا از درختان اسپلی الهام گرفته شده بود. اوردر سرشکن شده ی هر حذف مینیمم O(log n) است و عملیات پیدا کردن حداقل، ادغام و درج در سرشکن شده ی O(1) انجام میگیرد.

تعیین زمان دقیق مجانبی هیپ های جفت شده زمانی که یک عملیات کاهش کلید نیاز است کمی دشوار می باشد. در ابتدا به صورت تجربی حدس میزدند که زمان پیچیدگی این عملیات O(1) باشد اما Fredman ثابت کرد که زمان سرشکن هر کاهش کلید برای توالی برخی عملیات حداقل $\Omega (\log \log n)$ است. با استفاده ازمتد های مختلف استدلال استهلاکی Pettie پس از آن ثابت کرد که درج کردن و کاهش-کلید همه در $O(2^{2{\sqrt {\log \log n}}})$ سرشکن میشوند که برابر $o(\log n)$ است.  بعد از مدتی Elmasry یک نوع هیپ جفت شده معرفی کرد که کاهش کلید آن به صورت سرشکن در $O(\log \log n)$ انجام میشود و سایر عملیات مطابق هیپ فیبوناچی است اما $\Theta (\log \log n)$ برای داده ساختار اصلی درست نیست. اما این یک سوال بی جواب است که سرشکن $o(\log n)$ برای کاهش-کلید و $O(1)$ برای درج کردن را می توان به طور همزمان داشت یا خیر.

اگر چه این بدتر از دیگر الگوریتم های صف اولویت مانند هیپ فیبوناچی است که انجام کاهش کلیدشان در سرشکن  $O(1)$ است ولی در عمل بسیار عالی میباشند. Stasko و Vitter  Moret و shapiro و larkin و sen و Tarjan روی هیپ های جفت شده و سایر ساختمان های داده ی هیپ آزمایش هایی انجام دادند. آنها به این نتیجه رسیدند که هیپ های جفت شده اغلب در عمل سریع تر از هیپ های دودویی مبتنی بر آرایه و هیپ دی تایی و تقریبا همیشه عملا سریع ترند نسبت به دیگر هیپ های مبتنی بر اشاره گر از جمله ساختارهای داده ای مثل هیپ فیبوناچی که به لحاظ نظری کارآمد ترند.

ساختار

یک هیپ جفت شده یا یک هیپ خالی است یا یک جفت متشکل از یک ریشه و احتمالا یک لیست خالی از هیپ های جفت شده. برای ویژگی ترتیب هیپ ها نیاز است که ریشه هیچ کدام از زیرهیپ های این هیپ کوچکتر از ریشه ی خود هیپ نباشند. این توصیف صرفا یک هیپ تابعی را میدهد که از کاهش کلید پشتیبانی نمیکند.

type PairingHeap[Elem] = Empty | Heap(elem: Elem, subheaps: List[PairingHeap[Elem]])

یک پیاده سازی بر اساس اشاره گر برای ماشین های رم میتوان ارائه داد که از کاهش کلید پشتیبانی میکند. این پیاده سازی در هر گره سه اشاره گر دارد : یکی به اولین فرزندش، یکی به برادرش و یکی به پدرش. همیچنین اشاره به پدر میتواند حذف شود اگر برگ ها به جای فرزند به ریشه اشاره کنند و یک پرچم برای برگ ها گذاشته شود تا تشخیص داده شوند. که این یک ساختار جمع و جور تر است با همان سربار قبلی.

عملیات ها

پیدا کردن مینیمم

تابع پیدا کردن مینیمم فقط ریشه ی هیپ را برمیگرداند:

function find-min(heap)
  if heap == Empty
    error
  else
    return heap.elem

ادغام

ادغام با یک هیپ خالی هیپ اول را برمیگرداند در غیر این صورت یک هیپ جدید برگردانده میشود که ریشه ی کوچکتر ریشه ی آن بوده و هیپ با ریشه ی بزرگتر به فرزندان آن اضافه میشود:

function merge(heap1, heap2)
  if heap1 == Empty
    return heap2
  elsif heap2 == Empty
    return heap1
  elsif heap1.elem < heap2.elem
    return Heap(heap1.elem, heap2 :: heap1.subheaps)
  else
    return Heap(heap2.elem, heap1 :: heap2.subheaps)

درج

ساده ترین راه برای درج یک آیتم در یک هیپ این است که هیپ اصلی را با یک هیپ که فقط عنصر درج شده در آن قرار دارد ادغام کنیم:

function insert(elem, heap)
  return merge(Heap(elem, []), heap)

حذف 

تنها عمل اساس غیر بدیهی در هیپ حذف عنصر مینیمم از هیپ میباشد. استراتژی استاندارد اول زیردرخت ها را ادغام میکند (نام گذاری این ساختمان داده به خاطر این مرحله میباشد) از چپ به راست و سپس لیست هیپ های نتیجه شده را از راست به چپ ادغام میکند:

function delete-min(heap)
  if heap == Empty
    error
  else
    return merge-pairs(heap.subheaps)

که این از تابع کمکی merge-pairs استفاده میکند:

function merge-pairs(l)
  if length(l) == 0
    return Empty
  elsif length(l) == 1
    return l[0]
  else
    return merge(merge(l[0], l[1]), merge-pairs(l[2.. ]))

که این در واقع ادغام دو طرفه چپ به راست و راست به چپ را پیاده سازی میکند:

   merge-pairs([H1, H2, H3, H4, H5, H6, H7])
=> merge(merge(H1, H2), merge-pairs([H3, H4, H5, H6, H7]))
     # merge H1 and H2 to H12, then the rest of the list
=> merge(H12, merge(merge(H3, H4), merge-pairs([H5, H6, H7])))
     # merge H3 and H4 to H34, then the rest of the list
=> merge(H12, merge(H34, merge(merge(H5, H6), merge-pairs([H7]))))
     # merge H5 and H6 to H56, then the rest of the list
=> merge(H12, merge(H34, merge(H56, H7)))
     # switch direction, merge the last two resulting heaps, giving H567
=> merge(H12, merge(H34, H567))
     # merge the last two resulting heaps, giving H34567
=> merge(H12, H34567) 
     # finally, merge the first merged pair with the result of merging the rest
=> H1234567