پیاده‌سازی مرتب‌سازی هرمی (Heap Sort) در پایتون

در ادامه‌ی مباحث الگوریتم‌های پیشرفته و جستجو در پایتون، پس از بررسی مرتب‌سازی ادغامی و جستجوی دودویی، نوبت به یکی از هوشمندانه‌ترین روش‌های مرتب‌سازی یعنی مرتب‌سازی هرمی (Heap Sort) می‌رسد. این الگوریتم با بهره‌گیری از ساختار داده‌ای «هرم»، تعادلی عالی بین کارایی زمانی و مصرف بهینه‌ی حافظه ایجاد می‌کند.

معرفی الگوریتم مرتب‌سازی هرمی

مرتب‌سازی هرمی یک الگوریتم مرتب‌سازی مبتنی بر مقایسه است که از ساختار داده‌ای هرم (Heap) استفاده می‌کند. هرم در واقع یک درخت دودویی کامل است که ویژگی خاصی به نام «ویژگی هرم» را حفظ می‌کند. در یک Max-Heap، مقدار هر گره بزرگتر یا مساوی فرزندانش است و در نتیجه، بزرگ‌ترین عنصر همیشه در ریشه قرار دارد.

اهمیت آموزشی Heap Sort

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

• کارایی حافظه: برخلاف مرتب‌سازی ادغامی (Merge Sort)، این الگوریتم «درجا» (In-place) است و به حافظه جانبی زیادی نیاز ندارد.
• تضمین زمان: در بدترین حالت نیز پیچیدگی زمانی آن از مرتبه‌ی $O(n\log n)$O(nlogn) فراتر نمی‌رود.
• آموزش ساختار داده: پیاده‌سازی آن درک عمیقی از درخت‌های دودویی و نحوه نمایش آن‌ها در قالب لیست (آرایه) ایجاد می‌کند.

منطق و مراحل اجرای الگوریتم

الگوریتم مرتب‌سازی هرمی در دو مرحله‌ی کلی اجرا می‌شود:

1. ساخت هرم (Build Heap): لیست نامرتب به یک Max-Heap تبدیل می‌شود تا بزرگ‌ترین عنصر در ابتدای لیست قرار گیرد.
2. استخراج و مرتب‌سازی: عنصر ریشه (بزرگ‌ترین مقدار) با آخرین عنصر لیست جابه‌جا شده و از هرم خارج می‌شود. سپس ساختار هرم برای باقی‌مانده عناصر بازسازی (Heapify) می‌شود. این کار تا زمانی که تمام عناصر مرتب شوند ادامه می‌یابد.

تحلیل پیچیدگی زمانی و فضایی

یکی از نقاط قوت Heap Sort، پایداری عملکرد آن است:

• پیچیدگی زمانی (بدترین، بهترین و متوسط): همگی $O(n\log n)$O(nlogn) هستند. این ثبات باعث می‌شود در سیستم‌هایی که زمان پاسخ‌دهی حساس است، به آن اعتماد کرد.
• پیچیدگی فضایی: برخلاف Merge Sort که به فضای اضافی $O\left(n\right)$ نیاز دارد، این الگوریتم دارای پیچیدگی فضایی $O\left(1\right)$ است که آن را برای سیستم‌های با محدودیت حافظه ایده‌آل می‌کند.

مقایسه مفهومی با سایر الگوریتم‌ها

• در برابر Merge Sort: هر دو $O(n\log n)$ هستند، اما Heap Sort فضای کمتری می‌گیرد. با این حال، Merge Sort در دنیای واقعی معمولاً سریع‌تر است و «پایدار» (Stable) محسوب می‌شود (ترتیب عناصر یکسان را حفظ می‌کند)، در حالی که Heap Sort پایدار نیست.
• در برابر Quick Sort: مرتب‌سازی سریع در حالت میانگین بسیار سریع‌تر است، اما در بدترین حالت به $O\left(n^2\right)$ می‌رسد. Heap Sort تضمین می‌کند که هرگز به چنین کاهشی در عملکرد دچار نشود.

کاربردهای عملی

• صف‌های اولویت (Priority Queues): یکی از مهم‌ترین کاربردهای ساختار هرم.
• سیستم‌های بلادرنگ (Real-time Systems): به دلیل تضمین زمان اجرا در بدترین حالت.
• الگوریتم Introsort: بسیاری از کتابخانه‌های استاندارد (مانند ++C) از ترکیبی از Quick Sort و Heap Sort استفاده می‌کنند تا هم سرعت و هم امنیت زمانی را فراهم کنند.

جمع‌بندی

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

کلیدواژه ها : مرتب‌سازی هرمی-Heap Sort-ساختار داده هرم-Heap Data Structure-الگوریتم‌های پیشرفته-Advanced algorithms-پایتون-Python-تحلیل پیچیدگی-Complexity analysis-مرتب‌سازی درجا-In-place sorting-درخت دودویی-Binary tree