هرم جفت‌شده کیست؟ توضیح بده.
یک هرم جفت شده یک نوع داده ساختار هیپ با پیاده‌سازی نسبتاً ساده و عملکرد سرشکن شدهٔ عالی معرفی شده توسط Micheal Fredman، Robert Sedgewick، Daniel Sleator و Robert Tarjan در سال ۱۹۸۶ می‌باشد. هرمهای جفت شده ساختمان‌های درختی چند راهه می‌باشند که مانند هرم مرتب شده‌اند و می‌توانند هرمهای فیبوناچی ساده شده در نظر گرفته شوند. آن‌ها انتخابات قوی برای پیاده‌سازی الگوریتم‌هایی مانند الگوریتم پریم در نظر گرفته می‌شوند و از توابع زیر پیروی می‌کنند (با فرض اینکه مین-هیپ باشند):تحلیل پیچیدگی زمانی هرمهای جفت شده ابتدا از درختان اسپلی الهام گرفته شده بود. اوردر سرشکن شدهٔ هر حذف کمینه است و عملیات "پیدا کردن حداقل،" "ادغام "و درج در سرشکن شدهٔ انجام می‌گیرد.تعیین زمان دقیق مجانبی هرمهای جفت شده زمانی که یک عملیات کاهش کلید نیاز است کمی دشوار می‌باشد. در ابتدا به صورت تجربی حدس می‌زدند که زمان پیچیدگی این عملیات باشداما Fredman ثابت کرد که زمان سرشکن هر "کاهش کلید" برای توالی برخی عملیات حداقل formula_1 است.با استفاده از متدهای مختلف استدلال استهلاکی Pettie پس از آن ثابت کرد که "درج کردن "و "کاهش-کلید" همه در formula_2 سرشکن می‌شوند که برابر formula_3 است. بعد از مدتی Elmasry یک نوع هرم جفت شده معرفی کرد که کاهش کلید آن به صورت سرشکن در formula_4 انجام می‌شود و سایر عملیات مطابق هیپ فیبوناچی استاما formula_5 برای داده ساختار اصلی درست نیست. اما این یک سؤال بی جواب است که سرشکن formula_3 برای "کاهش-کلید" و formula_7 برای "درج کردن" را می‌توان به طور همزمان داشت یا خیر.اگر چه این بدتر از دیگر الگوریتم‌های صف اولویت مانند هیپ فیبوناچی است که انجام "کاهش کلیدشان "در سرشکن formula_7 است ولی در عمل بسیار عالی می‌باشند. Stasko و VitterMoret و 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 &lt; 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) == ۰ return Empty elsif length(l) == ۱ return l[0] else return merge(merge(l[0], l[1]), merge-pairs(l[2.. ]))که این در واقع ادغام دو طرفه چپ به راست و راست به چپ را پیاده‌سازی می‌کند:merge-pairs([H1, H2, H3, H4, H5, H6, H7]) =&gt; merge(merge(H1, H2), merge-pairs([H3, H4, H5, H6, H7])) # merge H1 and H2 to H12, then the rest of the list =&gt; merge(H12, merge(merge(H3, H4), merge-pairs([H5, H6, H7]))) # merge H3 and H4 to H34, then the rest of the list =&gt; merge(H12, merge(H34, merge(merge(H5, H6), merge-pairs([H7])))) # merge H5 and H6 to H56, then the rest of the list =&gt; merge(H12, merge(H34, merge(H56, H7))) # switch direction, merge the last two resulting heaps, giving H567 =&gt; merge(H12, merge(H34, H567)) # merge the last two resulting heaps, giving H34567 =&gt; merge(H12, H34567) # finally, merge the first merged pair with the result of merging the rest =&gt; H1234567