آموزش ماژول heapq و صف‌های اولویت در پایتون

سطح مقدماتی (Beginner Level)

ماژول heapq در پایتون ابزاری قدرتمند برای کار با ساختار داده‌ای به نام Heap (تپه یا پشته) است. این ماژول الگوریتم صف اولویت (Priority Queue) را پیاده‌سازی می‌کند. در پایتون، Heap به صورت پیش‌فرض یک Min-Heap است؛ به این معنی که کوچک‌ترین عنصر همیشه در اندیس 0 (ریشه) قرار می‌گیرد.

برخلاف لیست‌های معمولی که برای مرتب‌سازی آن‌ها نیاز به هزینه زمانی بالا داریم، heapq به ما اجازه می‌دهد همیشه به کوچک‌ترین آیتم با کمترین هزینه دسترسی داشته باشیم.

۱. تبدیل لیست به Heap (تابع heapify)

برای استفاده از قابلیت‌های Heap، ابتدا باید لیست خود را به ساختار Heap تبدیل کنیم. تابع heapify() لیست را به صورت درجا (In-place) تغییر می‌دهد تا شرط Heap برقرار شود.

نکته: در Min-Heap، هر والد از فرزندان خود کوچک‌تر یا مساوی است.

Python

python

        # نمایش ساختار درختی (شبه کد برای درک بهتر)
#      1
#    /   \
#   2     5
#  / \   /
# 20 10 8
      

۲. اضافه و حذف کردن عناصر (heappush و heappop)

برای حفظ ساختار Heap هنگام اضافه یا کم کردن داده‌ها، نباید از append یا pop معمولی لیست استفاده کنید.

heappush(heap, item): آیتم را اضافه کرده و ساختار Heap را مرتب می‌کند.
heappop(heap): کوچک‌ترین آیتم (ریشه) را حذف کرده و برمی‌گرداند.

مثال اول: اضافه کردن داده

Python

مثال دوم: برداشتن کوچک‌ترین داده

Python

سطح پیشرفته (Professional Level)

در سطح حرفه‌ای، heapq فقط برای پیدا کردن مینیمم نیست؛ بلکه برای مدیریت صف‌های وظایف (Task Scheduling)، بهینه‌سازی جستجوها و مدیریت حافظه در الگوریتم‌های حریصانه (Greedy Algorithms) کاربرد حیاتی دارد.

۱. توابع nlargest و nsmallest

اگر نیاز دارید $K$ عنصر بزرگ‌تر یا کوچک‌تر یک لیست عظیم را پیدا کنید، استفاده از sorted() و اسلایس کردن ([:n]) بسیار کند است چون کل لیست را مرتب می‌کند ($O(N \log N)$). توابع nlargest و nsmallest این کار را بسیار بهینه‌تر انجام می‌دهند.

Python

۲. صف اولویت (Priority Queue) با تاپل‌ها

یکی از کاربردهای اصلی Heap، ساخت صف اولویت است. در پایتون، هنگام مقایسه تاپل‌ها، ابتدا عنصر اول مقایسه می‌شود. بنابراین می‌توانیم داده‌ها را به صورت (priority, value) ذخیره کنیم.

نکته: چون پایتون Min-Heap است، عدد کمتر به معنی اولویت بالاتر (اجرای زودتر) است.

Python

۳. شبیه‌سازی Max-Heap

پایتون به صورت پیش‌فرض Max-Heap ندارد. برای اینکه بزرگ‌ترین عدد را در ریشه داشته باشیم (یا اولویت‌های بالاتر با عدد بزرگتر مشخص شوند)، یک تکنیک رایج قرینه کردن مقادیر (ضرب در -1) هنگام ذخیره‌سازی است.

Python

۴. بهینه‌سازی با heappushpop و heapreplace

این توابع برای زمانی که می‌خواهید اندازه Heap را ثابت نگه دارید بسیار کارآمد هستند (مثلاً نگهداری ۱۰ رکورد برتر).

heappushpop(heap, item): آیتم را اضافه کرده و سپس کوچک‌ترین را حذف می‌کند (سریع‌تر از دو دستور جدا).
heapreplace(heap, item): ابتدا کوچک‌ترین را حذف کرده و سپس آیتم جدید را اضافه می‌کند.

python

        # Static comparison showing logic flow
def maintain_top_k(new_item, current_top_k):
    # اگر آیتم جدید بزرگتر از کوچکترین عضوِ لیست برترین‌هاست
    if new_item > current_top_k[0]:
        # جایگزین کن (کوچکترین قبلی حذف می‌شود)
        heapq.heapreplace(current_top_k, new_item)
      

Python

۵. ادغام چندین لیست مرتب (merge)

اگر چندین لیست مرتب شده دارید و می‌خواهید آن‌ها را در یک لیست مرتب واحد ادغام کنید، heapq.merge این کار را بدون بارگذاری همه داده‌ها در حافظه (به صورت Iterator) انجام می‌دهد.

Python