درخت هیپ (Heap) و کاربردهای آن – به زبان ساده

هیپ حالت خاصی از ساختمان داده درخت باینری متعادل است که در آن کلید ریشه-گره با فرزندانش مقایسه شده و بر همین اساس مرتب می‌شود. اگر α فرزند به نام β داشته باشد، در این صورت:

key(α) ≥ key(β)

از آنجا که مقدار والد بزرگ‌تر از فرزند است، این مشخصات موجب ایجاد Max Heap می‌شود. بر اساس همین معیار، یک هیپ می‌تواند یکی از دو نوع زیر باشد:

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap – که مقدار گره ریشه کمتر یا مساوی یکی از فرزندانش باشد

Max-Heap – که مقدار گره ریشه بزرگ‌تر یا مساوی یکی از فرزندانش است.

هر دو درخت فوق با استفاده از ورودی و خروجی یکسانی ساخته شده‌اند.

الگوریتم ساخت Max-Heap

از مثال فوق برای نمایش چگونگی ایجاد یک مکس هیپ بهره می‌گیریم. این رویه با رویه ایجاد Min Heap مشابه است؛ اما در آن مورد، مقادیر کمینه به جای مقادیر بیشینه مورد استفاده قرار می‌گیرند.

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

• گام 1 – ایجاد یک گره جدید در انتهای هیپ
• گام 2 – انتساب مقدار جدید به گره
• گام 3 – مقایسه مقدار این گره فرزند با والدهایش
• گام 4 – اگر مقدار والد کمتر از فرزند باشد، در این صورت تعویض می‌شوند.
• گام 5 – گام‌های 3 و 4 تا زمانی که همه مشخصات هیپ برقرار شوند تداوم می‌یابند.

نکته – در بسیاری از الگوریتم‌های ساخت هیپ انتظار داریم که مقدار گره والد کمتر از مقدار گره فرزند باشد.

در ادامه ساخت مکس هیپ را با یک تصویر متحرک بررسی کنیم. فرض می‌کنیم ورودی ما همان است که در مثال‌های قبل بررسی کردیم.

الگوریتم حذف Max Heap

در این بخش الگوریتمی برای حذف از مکس هیپ ارائه می‌کنیم. عملیات Deletion در هیپ Max یا Min همواره در گره ریشه برای حذف مقدار بیشینه (یا کمینه) صورت می‌گیرد.

فیلم آموزش حل سوالات آزمون های استخدامی طراحی الگوریتم در فرادرس

کلیک کنید

• گام 1  – گره ریشه را حذف کن
• گام 2 – آخرین عنصر آخرین سطح را به ریشه جابجا کن.
• گام 3 – مقدار این گره فرزند را با والدهایش مقایسه کن.
• گام 4 – اگر مقدار والد کمتر از فرزند بود، جای آن‌ها را عوض کن.
• گام 5 – گام‌های 3 و 4 را تا زمانی که مشخصات هیپ برقرار است تکرار کن.

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

اگر این نوشته مورد توجه شما قرار گرفته است، پیشنهاد می‌کنیم موارد زیر را نیز بررسی کنید:

• آموزش ساختمان داده ها
• رویه‌های پایتون برای کد نویسی کارآمد: عملکرد، حافظه و قابلیت استفاده
• مجموعه آموزش‌های برنامه‌نویسی
• آموزش پیشرفته ساختمان داده (همراه با حل نمونه سوالات کنکور ارشد و دکتری)
• آموزش آرایه در ساختمان داده
• مجموعه آموزش‌های مهندسی نرم افزار
• آموزش طراحی و پیاده سازی زبان های برنامه سازی (مرور – تست کنکور ارشد)

==