نمایش مبدأ برای هرم دودویی

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

به این دلیل اینکه ترتیب فرزندان در هرم به‌طورمشخص نیست می‌توان جای آن‌ها را عوض کرد مگراینکه خاصیت ظاهری نقض شود.

== عملگرهای هرم ==

هردو عمل درج و حذف در هرم دودویی در زمان (O(log n انجام می‌شود.

=== درج ===

برای درج کردن الگوریتم به صورت زیر است:
# اضافه کردن عنصر جدید به سطح پایین هرم
# عنصر اضافه شده را با پدرش مقایسه کنید، اگر ترتیب آن‌ها درست بود الگوریتم متوقف می‌شود
# درغیراینصورت جای آن را با پدرش عوض می‌کنیم و سپس مرحله قبلی را تکرار می‌کنیم.

تعداد عملیات مورد نیاز به تعداد سطح‌هایی که عنصر جدید برای پیدا کردن مکان مناسب برای ارضا کردن ویژگی هرم باید طی کند بستگی دارد به همین دلیل به‌طور متوسط این عملیات در زمان (O(log n انجام می‌شود.

به عنوان مثال یک هرم بیشینه را در نظر بگیریم:
::[[پرونده:Heap add step1.svg|150px]]
حال می‌خواهیم گره با کلید ۱۵ را درج کنیم:
::[[پرونده:Heap add step2.svg|150px]]
با توجه به اینکه هنوز ویژگی هرم بیشینه رعایت نشده‌است باید جای جای ریشه با فرزند سمت راست عوض کرد.
::[[پرونده:Heap add step3.svg|150px]]

=== حذف ===
روش حذف کردن ریشه هرم و بازسازی هرم به منظور حفظ ویژگی آن پایین-هرم نامیده می‌شود که این روش به صورت زیر است:
# ریشه هرم را با آخرین عنصر آخرین سطح جابه‌جا کنید
# مقایسه کنید ریشه را با فرزندانش اگر ویژگی هرم برقرار بود الگوریتم متوقف می‌شود
# در غیراینصورت جای ان را با فرزندانش عوض کنید و مرحله قبلی را تکرار کنید.

به عنوان مثال می‌خواهیم گره با کلید ۱۱ را حذف کنیم:
::[[پرونده:Heap delete step0.svg|150px]]
۱۱ را حذف می‌کنیم و با ۴ جابه‌جا می‌کنیم
::[[پرونده:Heap remove step1.svg|150px]]
حال مرحله ۳ الگوریتم را انجام می‌دهیم
::[[پرونده:Heap remove step2.svg|150px]]

در بدترین حالت ریشه جدید باید تا پایین‌ترین سطح بیاید تا ویژگی هرم برقرار شود، این جمله معنی می‌دهد که عملیات حذف با ارتفاع درخت رابطه دارد که به‌طور متوسط (O(log n است.

=== ایجاد ===
یک هرم می‌تواند با درج‌های متوالی ساخته شود. پیچیدگی زمانی این کار (O(n log n، زیرا هر درج در زمان (O(log n صورت میگرد وعمل درج n با انجام می‌شود، اما این روش بهینه نیست. روش بهینه با قرار دادن عناصر به صروت دلخواه در یک درخت دودویی شروع می‌شود سپس از پایین‌ترین سطح شروع می‌کند و به سمت بالا حرکت می‌کند. ریشه هر زیردرخت رو به پایین را حرکت می‌دهد تا ویژگی هرم بازیابی شود. به دلیل اینکه ارتفاع درخت <math> \left\lfloor \lg (n) \right\rfloor</math> است، درست کردن ویژگی هرم همهٔ زیردرخت‌ها برابر است با:
:<math>
\begin{align}
\sum_{h=0}^{\lceil \lg n \rceil} \frac{n}{2^{h+1}}O(h) & =
O\left(n\sum_{h=0}^{\lceil \lg n \rceil} \frac{h}{2^{h + 1}}\right) \\
& \le O\left(n\sum_{h=0}^{\infty} \frac{h}{2^h}\right) \\
& = O(n)

\end{align}
</math>
که مقدار واقعی عبارت بالا برابر است با:
:<math> 2 n - 2 s_2 (n) - e_2 (n) </math>،<ref>{{citation
 | last1 = Suchenek | first1 = Marek A.
 | title = Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
 | doi = 10.3233/FI-2012-751
 | pages = 75–92
 | publisher = IOS Press
 | journal = Fundamenta Informaticae
 | volume = 120
 | issue = 1
 | year = 2012
 | url = http://www.deepdyve.com/lp/ios-press/elementary-yet-precise-worst-case-analysis-of-floyd-s-heap-50NW30HMxU}}.</ref>
که (s<sub>2</sub>(n برابر است با جمع همهٔ رقم‌های نماینده‌های دودویی n و (e<sub>2</sub>(n توان دو در فاکتوگیری اول n است.
تابع ساختن هرم‌بیشینه یک آرایه را به یک درخت دودویی که هرم بیشینه هست تبدیل می‌کند و از تابع '''Max-Heapify''' استفاده می‌کند. [[شبه‌کد|شبه کد]] به صورت زیر است:

{{چپ‌چین}}
 '''Build-Max-Heap''' (''A''){{سخ}}
 {{pad|2em}}''heap_length''[''A''] ← ''length''[''A'']{{سخ}}
 {{pad|2em}}'''for''' ''i'' ← ''floor''(''length''[''A'']/2) '''downto''' 1 '''do'''{{سخ}}
 {{pad|4em}}'''Max-Heapify'''(''A'', ''i'')
{{پایان چپ‌چین}}

== پیاده‌سازی هرم ==
[[پرونده:Binary tree in array.svg|300px|چپ|frame|A small complete binary tree stored in an array]]
[[پرونده:Binary Heap with Array Implementation.JPG|400px|بندانگشتی|چپ|Comparison between a binary heap and an array implementation.]]

هرم‌ها به‌طور رایج با آرایه پیاده‌سازی می‌شوند. یک درخت دودویی می‌تواند در یک آرایه ذخیره شود. هیچ فضایی برای [[اشاره‌گر (علوم رایانه)|اشاره‌گر]] نیاز نیست، درعوض گره فرزندان و پدر به وسیلهٔ حساب کردن شاخص‌های آرایه پیدا می‌شوند. با این ویژگی پیاده‌سازی هرم به صورت ساده انجام می‌شود. جزییات به موقعیت ریشه بستگی دارد که به نوبه خود به محدودیت [[زبان برنامه‌نویسی]] مورد استفاده برای پیاده‌سازی بستگی دارد. به‌طور خاص‌تر بعضی اوقات ریشه در مکان ۱ قرار می‌گیرد. n را تعداد عناصر هرم در نظر بگبرید و i را هم مقدار دلخواه [[اندیس (معدن)|اندیس]] آرایه، اگر ریشه را در اندیس صفر قرار دهیم انگاه اندیس هر عنصر به صورت زیر می‌شود:
* فرزندان <math>2i+1</math> و <math>2i+2</math>
* پدرشان <math>\lfloor \frac{i-1}{2} \rfloor</math>

اگر ریشه در اندیس ۱ قرار بگیرد، اندیس هر عنصر به صورت زیر می‌شود:
* فرزندان <math>2i+1</math> و <math>2i</math>
* پدرشان <math>\lfloor \frac{i}{2} \rfloor</math>

این پیاده‌سازی هم‌چنین برای استفاده به عنوان صف اولویت مناسب است. عملیات هرم‌بالا/هرم‌پایین می‌تواند در شرایط یک آرایه به صورت زیر اعلام شود: فرض کنید که ویژگی هرم نگه می‌دارد برای مشخصه‌های ''b'', ''b''+1, ... , ''e''. تابع غربال کردن به پایین ویژگی هرم را به''b''−1, ''b'', ''b''+1, ... , ''e'' گسترش می‌دهد، فقط اندیس ''i'' = ''b''−۱ می‌تواند این ویژگی را نقض کند. فرض کنید اندیس ''j'' بزرگترین بچه[ ''a''[''i'' در هرم بیشینه (کوچکترین فرزند در درخت کمینه) باشد. با جابه‌جا کردن [''a''[''i'' و [''a''[''j'' ویژگی هرم برای اندیس ''i'' برقرار می‌شود. در این مرحله تنها مسیله این است که ویژگی هرم برای اندیس ''j'' برقرار نباشد. تابع غربال کردن به پایین عملی می‌کند[[دم-بازگشتی]]را تا برای همه عناصر ویژگی هرم برقرار باشد.

تابع غربال کردن به پایین سریع عمل می‌کند. در هر مرحله فقط به دو مقایسه و یک جابه‌جایی نیاز دارد. مقدار شاخص در هر تکرار دوبرابر کار می‌کند، به‌طوری‌که تعداد مراحل حداکثر برابر است باlog<sub>2</sub> '' e''

برای یک هرم بزرگ و استفاده کردن از [[حافظه مجازی]] ذخیره کردن در آرایه به صورت بالا ناکارآمد است.(تقریباً) هر سطر که در یک [[صفحه (حافظه کامپیوتر)]] متفاوت است، هرم‌های دودویی هستند که زیردرخت‌ها را در یک حافظه منفرد نگه می‌دارند، تعداد حافظه‌های قابل دسترسی به بالا از عامل ده را کاهش می‌دهد.<ref>
Poul-Henning Kamp.
[http://queue.acm.org/detail.cfm?id=1814327 "You're Doing It Wrong"].
ACM Queue.
June 11, 2010.</ref>

عمل ادغام دو هرم دودویی در (''Θ(''n صورت می‌گیرد که n اندازه هرم است. بهتر است که شما به‌طور ساده دو آرایه هرم را ادغام کنید و سپس از حاصل یک هرم دودویی بسازید.<ref>Chris L. Kuszmaul.
[http://nist.gov/dads/HTML/binaryheap.html "binary heap"] {{Webarchive|url=https://web.archive.org/web/20080808141408/http://www.nist.gov/dads/HTML/binaryheap.html |date=۸ اوت ۲۰۰۸ }}

Dictionary of Algorithms and Data Structures, Paul E. Black, ed. , U.S. National Institute of Standards and Technology. 16 November 2009.</ref> یک هرم با ''n'' عنصر و یک هرم با ''k'' عنصر می‌توانند در (''O(log ''n'' log ''k با هم ادغام شوند..<ref>J. -R. Sack and T. Strothotte
[http://www.springerlink.com/content/k24440h5076w013q/ "An Algorithm for Merging Heaps"]{{پیوند مرده|date=فوریه ۲۰۲۰ |bot=InternetArchiveBot }},
Acta Informatica 22, 171-186 (1985).</ref> یک الگوریتم برای جداکردن یک هرم دودویی با ''n'' عنصر و تبدیل به دو هرم دودویی با ''n-k'' عنصر ''k'' عنصر، به‌ترتیب، براساس یک دیدگاه جدید هرم به عنوان مجموعه مرتب‌شده زیرهرم ارائه شد.<ref>. J. -R. Sack and T. Strothotte
[http://www.sciencedirect.com/science/article/pii/089054019090026E "A characterization of heaps and its applications"]
Information and Computation
Volume 86, Issue 1, May 1990, Pages 69–86.</ref> این الگوریتم به (''O(log ''n'' * log ''n مقایسه نیاز دارد. این دیدگاه جدید همچنین به‌طور مفهومی الگوریتم ساده برای ادغام دو هرم ارائه می‌دهد. وقتی که ادغام یک کار رایج است، پیاده‌سازی یک هرم متفاوت توصیه می‌شود، مانند [[هرم دوجمله‌ای]] که در (''O(log ''n ادغام می‌شود.

به علاوه یک هرم دودویی می‌تواند با یک داده‌ساختار درخت دودویی مرسوم پیاده‌سازی شود، اما یک نکته برای پیدا کردن عنصر مجاور آخرین سطح روی هرم دودویی وجود دارد. این عنصر می‌تواند به صورت [[الگوریتم|الگوریتمی]] پیدا شود یا با اضافه کردن اصلاعات اضافی به گره‌هاکه نخ نامیده می‌شود مانند اضافه کردن یک فیلد بعدی به هر گره پیدا شود. می‌توان با اصلاح ساختار هرم هر دو عنصر کوچکترین و بزرگترین در (''O(log ''n پیدا کرد.<ref name="sym">{{cite web
| url = http://cg.scs.carleton.ca/~morin/teaching/5408/refs/minmax.pdf
| author = Atkinson, M.D. , [[Jörg-Rüdiger Sack|J. -R. Sack]], N. Santoro, and T. Strothotte
| title = Min-max heaps and generalized priority queues.
| publisher = Programming techniques and Data structures. Comm. ACM, 29(10): 996–1000
| date = 1 October 1986
| access-date = ۱ فوریه ۲۰۱۴
| archive-date = ۲۷ ژانویه ۲۰۰۷
| archive-url = https://web.archive.org/web/20070127093845/http://cg.scs.carleton.ca/%7Emorin/teaching/5408/refs/minmax.pdf
| url-status = dead
}}</ref> برای اینکار ردیف‌های متاوب بین هرم [[بیشینه و کمینه]] را جایگزین می‌کنیم. این الگوریتم‌ها تقریباً متاوب هستند، اما در هر مرحله باید ردیف‌های متاوب را با مقایسه‌های متناوب در نظر بگیریم. کارایی این الگوریتم تقریباً مشابه جهت منفرد طبیعی هرم است. این ایده می‌تواند برای هرم-بیشینه-کمینه-میانه تعمیم پیذا کند.

== اشتقاق معادلات شاخص ==

در یک آرایه هرم، پدر و فرزندان می‌توانند با یک حساب ساده روی مشخصه (اندیس) آرایه پیدا شوند. در این بخش به بررسی معدلات مشتق شده هرم وقتی که اندیس ریشه در آرایه صفر است و یادداشت‌هایی وقتی اندیس ریشه در آرایه یک است را می‌پردازیم.

برای جلوگیری از ابهام، سطح را فاصله از ریشه معنی می‌کنیم، به‌طوری‌که خود ریشه در سطح صفر هست.

== گره‌های فرزندان ==

به‌طور عمومی گره که در اندیس ''i'' هست، فرزند سمت راست ان در اندیس''2i+۲'' هست.

گره ''i'' را در سطح ''L'' در نظر بگیرید، و توجه کنید که هر سطح ''l'' دقیقاً <math>2^l</math> گره شمامل می‌شود. به علاوه دقیقاً <math>2^{l + 1} - 1</math> گره در لایه‌های بالایی شامل می‌شوند. به دلیل اینکه ریشه در اندیس صفر هست ''k'' امین گره در اندیس <math>(k - 1)</math> ذخیره می‌شود. این مشاهدات را برای نتیجه در کنار هم قرار می‌دهیم تا عبارت زیر برای ''اندیس اخرین عنصر در لایه l بدست بیاید''
::<math>\text{last}(l) = (2^{l + 1} - 1) - 1 = 2^{l + 1} - 2</math>

''j'' را گره‌های بعد از گره ''i'' در نظر بگیرید، به‌طوری که:

::<math>\begin{alignat}{2}
i = & \quad \text{last}(L) - j\\
  = & \quad (2^{L + 1} -2) - j\\
\end{alignat}
</math>

هر کدام از گره‌های ''j'' باید دقیقاً دو فرزند داشته باشند، بنابراین باید وجود داشته باشد <math>2j</math> گره برای جداسازی <math>i</math>'s فرزند راست از انتهای خودش لایه (<math>L + 1</math>)

::<math>\begin{alignat}{2}
\text{right} = & \quad \text{last(L + 1)} -2j\\
             = & \quad (2^{L + 2} -2) -2j\\
             = & \quad 2(2^{L + 1} -2 -j) + 2\\
             = & \quad 2i + 2
\end{alignat}
</math>

به عنوان مورد نیاز.

توجه کنید که فرزند سمت چپ یک گره یک مکان قبل تر از فرزند سمت راست است بنابراین: <math>\text{left} = 2i + 1</math>.

اگر ریشه به جای اندیس صفر در اندیس یک باشد، اندیس آخرین گره در هر سطح برابر است با <math>2^{l + 1} - 1</math>. همچنین با استفاده از مطالب ذکر شده برای یک هرم با اندیس یک ریشه <math>\text{left} = 2i</math> و <math>\text{right} = 2i + 1</math>.

== گره پدر ==

هر گره یا فرزند سمت چپ یا فرزند سمت راست پدر خودش هست، بنابراین:
# <math>i = 2 \times (\text{parent}) + 1</math>
# <math>i = 2 \times (\text{parent}) + 2</math>

در نتیجه:

::<math>\text{parent} = \frac{i - 1}{2} \textbf{ or } \frac{i - 2}{2}</math>

حال عبارت <math>\left\lfloor \dfrac{i - 1}{2} \right\rfloor</math> را در نظر بگیرید.

اگر گره ''i'' فرزند سمت چپ باشد، به‌طور بدیهی این نتیجه بدست می‌اید، اگرچه، اگر گره ''i'' فرزند راست باشد این نتیجه درست است. در این مورد، <math>(i - 2)</math> باید زوج باشد بنابراین <math>(i - 1)</math> باید فرد باشد.

::<math>\begin{alignat}{2}
\left\lfloor \dfrac{i - 1}{2} \right\rfloor = & \quad \left\lfloor \dfrac{i - 2}{2} + \dfrac{1}{2} \right\rfloor\\
= & \quad \frac{i - 2}{2}\\
= & \quad \text{parent}
\end{alignat}
</math>

بنابراین، با صرف‌نظر از اینکه گره ''i'' فرزند سمت راست یا چپ است، پدر این گره با عبارت زیر حساب می‌شود:

::<math>\text{parent} = \left\lfloor \dfrac{i - 1}{2} \right\rfloor</math>

== مین-هیپ ==
مین-هیپ {{به انگلیسی|min-heap}} دارای ویژگی مین-هیپ است. در واقع برای هر گره <math>i</math> به جز ریشه، رابطهٔ زیر صدق می‌کند:
:<math>A[Parent(i)]<=A[i]</math>
کوچک‌ترین عضو هرم در ریشه قرار دارد. برای الگوریتم [[مرتب‌سازی هرمی]] از مکس هیپ استفاده می‌شود. مین هیپ معمولاً برای [[صف‌های اولویت]] مورد استفاده قرار می‌گیرد. 
[[پرونده:Min-heap.png|thumb|200px|مثالی از یک هرم مین هیپ]]



== جستارهای وابسته ==
* [[هرم]]
* [[مرتب‌سازی هرم]]

== منابع ==
* {{یادکرد|نویسنده =T. Cormen |کتاب = Introduction to Algorithms| ناشر =MIT Press |صفحه = 152-153|تاریخ ={{rle}}۱۰ نوامبر ۲۰۱۱ }}


{{پانویس}}

== پیوند به بیرون ==
* [http://people.ksp.sk/~kuko/bak/index.html Binary Heap Applet] by Kubo Kovac
* [https://web.archive.org/web/20040611075754/http://www.policyalmanac.org/games/binaryHeaps.htm Using Binary Heaps in A* Pathfinding]
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html Open Data Structures - Section 10.1 - BinaryHeap: An Implicit Binary Tree]

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