هیپ (Heap)
هیپ Min و Max: قاعده هیپ، heapify، صف اولویت‌دار و ماژول heapq پایتون
هیپ چیست؟
هیپ (Heap) درخت دودویی تام (Complete)ی است با قاعده:
- Max-Heap: هر والد بزرگ‌تر یا مساوی فرزندانش ← بزرگ‌ترین همیشه در ریشه
- Min-Heap: هر والد کوچک‌تر یا مساوی فرزندانش ← کوچک‌ترین همیشه در ریشه
توجه: هیپ مرتب‌سازی کامل نیست! فقط تضمین می‌کند ریشه، extreme باشد.
هیپ با آرایه
چون هیپ درخت تام است، می‌توان آن را در آرایه ذخیره کرد (بدون اشاره‌گر!):
برای گره در اندیس i:
- والد: (i - 1) // 2
- فرزند چپ: 2i + 1
- فرزند راست: 2i + 2عملیات و پیچیدگی‌ها
| عملیات | پیچیدگی | توضیح |
|---|---|---|
| پیدا کردن min/max | O(1) | همیشه ریشه! |
| درج (push) | O(log n) | اضافه به انتها + sift-up |
| حذف ریشه (pop) | O(log n) | آخرین به ریشه + sift-down |
| ساخت هیپ از آرایه | O(n) | heapify — از پایین به بالا |
sift-up و sift-down
- sift-up: بعد از درج، عنصر جدید با والدش مقایسه و در صورت لزوم بالا می‌رود
- sift-down: بعد از حذف ریشه، آخرین عنصر به ریشه می‌رود و با مناسب‌ترین فرزند جابه‌جا می‌شود تا جای درستش را پیدا کند
صف اولویت‌دار (Priority Queue)
مهم‌ترین کاربرد هیپ: صفی که عنصر با بالاترین اولویت اول خارج می‌شود (نه ترتیب ورود!). مثال‌ها:
- بیمارستان: بیمار بحرانی اول ویزیت می‌شود (نه اولین رسیده)
- سیستم‌عامل: پردازش با اولویت بالا اول اجرا
- الگوریتم دایکسترا: شهر با کمترین فاصله اول پردازش
- الگوریتم A* در بازی‌ها
heapq در پایتون
ماژول heapq هیپ مین را روی list پیاده‌سازی می‌کند:
import heapq
heap = []
heapq.heappush(heap, 5) # درج O(log n)
smallest = heapq.heappop(heap) # حذف کوچک‌ترین O(log n)برای Max-Heap، مقادیر را منفی کنید یا از heapq.nlargest استفاده کنید.
نکته: اگر فقط «بزرگ‌ترین/کوچک‌ترین» می‌خواهید، هیپ بهترین است؛ اگر «همه داده مرتب» می‌خواهید، مرتب‌سازی یا BST.
جمع‌بندی
- هیپ = درخت تام + قاعده والد-فرزند
- ریشه همیشه min یا max — دسترسی O(1)
- درج/حذف O(log n) با sift-up/down
- پایه صف اولویت‌دار و الگوریتم‌های گراف
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.