نمایش مبدأ برای هرم جفت‌شده

یک '''هرم جفت شده''' یک نوع [[ساختمان داده‌ها|داده ساختار]] [[هیپ]] با پیاده‌سازی نسبتاً ساده و عملکرد سرشکن شدهٔ عالی معرفی شده توسط Micheal Fredman، Robert Sedgewick، Daniel Sleator و Robert Tarjan در سال ۱۹۸۶ می‌باشد.<ref name="FSST">{{Cite journal|url=http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf|title=The pairing heap: a new form of self-adjusting heap|last2=Sedgewick|first2=Robert|journal=Algorithmica|issue=1|doi=10.1007/BF01840439|year=1986|volume=1|pages=111–129|last3=Sleator|first3=Daniel D.|last4=Tarjan|first4=Robert E.|last1=Fredman|first1=Michael L.|author1-link=Michael Fredman|author2-link=Robert Sedgewick (computer scientist)|author3-link=Daniel Sleator|author4-link=Robert Tarjan}}</ref> هرمهای جفت شده ساختمان‌های درختی چند راهه می‌باشند که مانند هرم مرتب شده‌اند و می‌توانند هرمهای فیبوناچی ساده شده در نظر گرفته شوند. آن‌ها انتخابات قوی برای پیاده‌سازی الگوریتم‌هایی مانند [[الگوریتم پریم]] در نظر گرفته می‌شوند<ref name="mehlhorn">{{Cite book|url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/MinimumSpanningTrees.pdf|title=Algorithms and Data Structures: The Basic Toolbox|last2=Sanders|first2=Peter|publisher=Springer|year=2008|page=231|last1=Mehlhorn|first1=Kurt|author1-link=Kurt Mehlhorn|author2-link=Peter Sanders (computer scientist)}}</ref> و از توابع زیر پیروی می‌کنند (با فرض اینکه مین-هیپ باشند):
* ''پیدا کردن کمینه'': به سادگی به آیتم بالای هرم برمی‌گردیم.
* ''ادغام'': دو ریشه را با یک دیگر مقایسه می‌کنیم ریشهٔ کوچکتر ریشهٔ اصلی می‌شود و ریشهٔ بزرگتر و زیردرخت آن فرزند این ریشهٔ اصلی می‌شوند.
* ''درج'': یک هرم برای عنصر درج شده ساخته و آن را با هرم اصلی ادغام می‌کنیم.
* ''کاهش کلید'' (اختیاری): زیرهرمی که ریشه اش این کلید است را حذف می‌کنیم کلید را با یک کلید کوچکتر جایگزین می‌کنیم سپس نتیجه را دوباره با هرم اصلی ادغام می‌کنیم.
* ''حذف مینیمم'': ریشه را حذف کرده و زیرهرمهایش را با یکدیگر ادغام می‌کنیم. استراتژی‌های مختلفی به کار گرفته می‌شوند.
تحلیل پیچیدگی زمانی هرمهای جفت شده ابتدا از [[درخت اسپلی|درختان اسپلی]] الهام گرفته شده بود.<ref name="FSST"/> اوردر سرشکن شدهٔ هر حذف کمینه {{ریاضی|''O''(log ''n'')}} است و عملیات ''پیدا کردن حداقل،'' ''ادغام ''و درج در سرشکن شدهٔ {{ریاضی|''O''(1)}} انجام می‌گیرد.<ref name="Iacono2">{{Cite conference|last=Iacono|first=John|title=Improved upper bounds for pairing heaps|url=http://john2.poly.edu/papers/swat00/paper.pdf|doi=10.1007/3-540-44985-X_5|pages=63–77|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|conference=Proc. 7th Scandinavian Workshop on Algorithm Theory|volume=1851|year=2000|isbn=978-3-540-67690-4|arxiv=1110.4428|accessdate=۶ مه ۲۰۱۶|archiveurl=https://web.archive.org/web/20121224200500/http://john2.poly.edu/papers/swat00/paper.pdf|archivedate=۲۴ دسامبر ۲۰۱۲|dead-url=yes}}</ref>

تعیین زمان دقیق مجانبی هرمهای جفت شده زمانی که یک عملیات کاهش کلید نیاز است کمی دشوار می‌باشد. در ابتدا به صورت تجربی حدس می‌زدند که زمان پیچیدگی این عملیات {{ریاضی|''O''(1)}} باشد<ref name="StaskoVitter">{{Citation|title=Pairing heaps: experiments and analysis|year=1987|last1=Stasko|last2=Vitter|first1=John T.|first2=Jeffrey S.|author-link=John Stasko|author2-link=Jeffrey Vitter|journal=Communications of the ACM|volume=30|issue=3|pages=234–249|doi=10.1145/214748.214759|id={{citeseerx|10.1.1.106.2988}}}}</ref>
اما Fredman ثابت کرد که زمان سرشکن هر ''کاهش کلید'' برای توالی برخی عملیات حداقل <math>\Omega(\log\log n)</math> است.<ref name="Fredman">{{Cite journal|url=http://wwwens.uqac.ca/azinflou/Fichiers840/EfficiencyPairingHeap.pdf|title=On the efficiency of pairing heaps and related data structures|last=Fredman|first=Michael L.|journal=Journal of the ACM|issue=4|doi=10.1145/320211.320214|year=1999|volume=46|pages=473–501|author-link=Michael Fredman|access-date=۶ مه ۲۰۱۶|archive-url=https://web.archive.org/web/20110721051135/http://wwwens.uqac.ca/azinflou/Fichiers840/EfficiencyPairingHeap.pdf|archive-date=۲۱ ژوئیه ۲۰۱۱|dead-url=yes}}</ref>
با استفاده از متدهای مختلف استدلال استهلاکی Pettie پس از آن ثابت کرد که ''درج کردن ''و ''کاهش-کلید'' همه در <math>O(2^{2\sqrt{\log\log n}})</math> سرشکن می‌شوند که برابر <math>o(\log n)</math> است.<ref name="Pettie">{{Citation|last=Pettie|first=Seth|title=[[Symposium on Foundations of Computer Science|Proc. 46th Annual IEEE Symposium on Foundations of Computer Science]]|year=2005|pages=174–183|contribution=Towards a final analysis of pairing heaps|contribution-url=http://www.eecs.umich.edu/~pettie/papers/focs05.pdf|doi=10.1109/SFCS.2005.75|isbn=0-7695-2468-0}}</ref> بعد از مدتی Elmasry یک نوع هرم جفت شده معرفی کرد که کاهش کلید آن به صورت سرشکن در <math>O(\log \log n)</math> انجام می‌شود و سایر عملیات مطابق [[هیپ فیبوناتچی|هیپ فیبوناچی]] است<ref name="Elmasry">{{Citation|last=Elmasry|first=Amr|title=[[Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms]]|year=2009|pages=471–476|contribution=Pairing heaps with <math>O(\log \log n)</math> decrease cost|contribution-url=http://www.siam.org/proceedings/soda/2009/SODA09_052_elmasrya.pdf|doi=10.1137/1.9781611973068.52|accessdate=۶ مه ۲۰۱۶|archive-date=۱۸ اكتبر ۲۰۱۲|archive-url=https://web.archive.org/web/20121018164450/http://siam.org/proceedings/soda/2009/SODA09_052_elmasrya.pdf|url-status=dead}}</ref>
اما <math>\Theta(\log\log n)</math> برای داده ساختار اصلی درست نیست.<ref name="Iacono2"/><ref name="Pettie"/> اما این یک سؤال بی جواب است که سرشکن <math>o(\log n)</math> برای ''کاهش-کلید'' و <math>O(1)</math> برای ''درج کردن'' را می‌توان به طور همزمان داشت یا خیر.<ref name="LST">{{Citation|title=Proceedings of the 16th Workshop on Algorithm Engineering and Experiments|year=2014|last1=Larkin|last2=Sen|last3=Tarjan|first1=Daniel H.|first2=Siddhartha|first3=Robert E.|author3-link=Robert Tarjan|pages=61–72|contribution=A back-to-basics empirical study of priority queues|arxiv=1403.0252|doi=10.1137/1.9781611973198.7}}</ref>

اگر چه این بدتر از دیگر الگوریتم‌های صف اولویت مانند [[هیپ فیبوناتچی|هیپ فیبوناچی]] است که انجام ''کاهش کلیدشان ''در سرشکن <math>O(1)</math> است ولی در عمل بسیار عالی می‌باشند. Stasko و Vitter<ref name="StaskoVitter"/>
Moret و shapiro<ref name="MoretShapiro">{{Citation|title=[[Workshop on Algorithms and Data Structures|Proc. 2nd Workshop on Algorithms and Data Structures]]|year=1991|last1=Moret|last2=Shapiro|first1=Bernard M. E.|first2=Henry D.|series=Lecture Notes in Computer Science|volume=519|pages=400–411|contribution=An empirical analysis of algorithms for constructing a minimum spanning tree|publisher=Springer-Verlag|doi=10.1007/BFb0028279|isbn=3-540-54343-0|id={{citeseerx|10.1.1.53.5960}}}}</ref>
و larkin و sen و Tarjan<ref name="LST"/>
روی هرمهای جفت شده و سایر ساختمان‌های دادهٔ هرم آزمایش‌هایی انجام دادند. آنها به این نتیجه رسیدند که هرمهای جفت شده اغلب در عمل سریع تر از [[هرم دودویی|هیپ‌های دودویی]] مبتنی بر آرایه و [[هیپ دی تایی]] و تقریباً همیشه عملاً سریع ترند نسبت به دیگر هرمهای مبتنی بر [[اشاره‌گر (علوم رایانه)|اشاره گر]] از جمله ساختارهای داده‌ای مثل [[هیپ فیبوناتچی|هیپ فیبوناچی]] که به لحاظ نظری کارآمد ترند.

== ساختار ==
یک هرم جفت شده یا یک هرم خالی است یا یک جفت متشکل از یک ریشه و احتمالاً یک لیست خالی از هرمهای جفت شده. برای ویژگی ترتیب هرمها نیاز است که ریشه هیچ‌کدام از زیرهرمهای این هرم کوچکتر از ریشهٔ خود هرم نباشند. این توصیف صرفاً یک هرم تابعی را می‌دهد که از کاهش کلید پشتیبانی نمی‌کند.
{{چپ‌چین}}
 type PairingHeap[Elem] = Empty | Heap(elem: Elem, subheaps: List[PairingHeap[Elem]])
{{پایان چپ‌چین}}
یک پیاده‌سازی بر اساس اشاره گر برای ماشین‌های رم می‌توان ارائه داد که از کاهش کلید پشتیبانی می‌کند. این پیاده‌سازی در هر گره سه اشاره گر دارد: یکی به اولین فرزندش، یکی به برادرش و یکی به پدرش. همچنین اشاره به پدر می‌تواند حذف شود اگر برگ‌ها به جای فرزند به ریشه اشاره کنند و یک پرچم برای برگ‌ها گذاشته شود تا تشخیص داده شوند؛ که این یک ساختار جمع و جور تر است با همان سربار قبلی.<ref name="FSST"/>

== عملیات‌ها ==
=== پیدا کردن مینیمم ===
تابع پیدا کردن مینیمم فقط ریشهٔ هرم را برمی‌گرداند:
 {{چپ‌چین}}
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) == ۰
  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])
 => 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

{{پایان چپ‌چین}}

== منابع ==
{{پانویس|30em}}

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

[[رده:هرم‌ها (علوم رایانه)]]
[[رده:داده ساختارهای استهلاکی]]