معرفی کتابخانه heapq در پایتون

کتابخانهٔ استاندارد heapq در پایتون مجموعهٔ توابعی برای کار با ساختار دادهٔ heap (هیپ) فراهم می‌کند. این پیاده‌سازی به‌صورت min-heap بر روی لیست پایتون انجام می‌شود؛ یعنی کوچک‌ترین عنصر همیشه در اندیس صفر قرار دارد. heapq برای مسائل مرتب‌سازی جزئی، صف‌های اولویت و یافتن بزرگ‌ترین/کوچک‌ترین k عنصر بسیار مناسب و کارا است.

ویژگی‌ها و کاربردهای معمول

• حفظ سریع کوچک‌ترین عنصر (O(1) برای خواندن)
• افزودن و حذف ریشه با هزینهٔ O(log n)
• تبدیل یک لیست به heap با هزینهٔ O(n) (عملکرد خطی)
• توابع کمکی مثل nlargest، nsmallest و merge برای کار با مجموعه‌های مرتب

توابع پایه‌ای

• heapq.heapify(x)
• heapq.heappush(heap, item)
• heapq.heappop(heap)
• heapq.heappushpop(heap, item)
• heapq.heapreplace(heap, item)
• heapq.nlargest(n, iterable, key=None)
• heapq.nsmallest(n, iterable, key=None)
• heapq.merge(*iterables)

عملکرد زمانی — جدول خلاصه

مثال‌های پایه‌ای

import heapq

data = [5, 1, 8, 3, 2]
heapq.heapify(data)
heapq.heappush(data, 0)
smallest = heapq.heappop(data)
print(smallest, data)

در این مثال ابتدا لیست به‌صورت heap در می‌آید. سپس 0 وارد heap شده و کوچک‌ترین عنصر با heappop حذف و برگردانده می‌شود. خروجی نشان می‌دهد که همیشه کوچک‌ترین مقدار در ابتدا قرار دارد.

یافتن بزرگ‌ترین یا کوچک‌ترین k عنصر

import heapq
nums = [7, 2, 5, 3, 9, 1, 4]
top3 = heapq.nlargest(3, nums)
bottom2 = heapq.nsmallest(2, nums)
print(top3, bottom2)

توابع nlargest و nsmallest برای انتخاب k المان استفاده می‌شوند. زمانی که k بسیار کوچک‌تر از اندازهٔ مجموعه باشد، این توابع معمولاً از الگوریتم heap استفاده می‌کنند (پیچیدگی ≈ O(n log k)) که از مرتب‌سازی کامل کاراتر است.

استفاده از heap به‌عنوان max-heap

heapq به‌صورت پیش‌فرض min-heap است. برای شبیه‌سازی max-heap معمول‌ترین روش استفاده از علامت منفی برای اعداد است یا استفاده از تاپل/کلاس‌هایی که ترتیب را معکوس می‌کنند.

import heapq

# روش منفی کردن برای اعداد
nums = [1, 3, 5, 2, 4]
max_heap = []
for n in nums:
    heapq.heappush(max_heap, -n)

max_val = -heapq.heappop(max_heap)
print(max_val)

در این نمونه با منفی‌کردن هر عدد، کوچک‌ترین عدد منفی معادل بزرگ‌ترین مقدار اصلی می‌شود. هنگام pop مجدداً منفی را برمی‌گردانیم تا مقدار اصلی بازیابی شود.

# روش کلاس/تاپل برای اشیاء پیچیده‌تر
import heapq
from dataclasses import dataclass

@dataclass(order=True)
class Item:
    priority: int
    name: str

items = [Item(5,'a'), Item(1,'b'), Item(3,'c')]
# اگر بخواهیم بیشترین priority را اول ببینیم، می‌توانیم از -priority استفاده کنیم:
pq = []
for it in items:
    heapq.heappush(pq, (-it.priority, it))

highest = heapq.heappop(pq)[1]
print(highest)

در حالت کار با اشیاء، معمول است که اولویت را در یک تاپل قرار دهیم تا ترتیب قابل مقایسه شود؛ استفاده از -priority ترتیب معکوس (max-heap) را می‌دهد.

الگوریتم‌ها و نکات عملیاتی

• heapq.heapify سریع‌تر از push کردن تک‌تک عناصر است (O(n) در مقابل O(n log n)).
• heapq.heappushpop(heap, item) سریع‌تر از heappush سپس heappop در مواردی که قرار است مقدار جدید وارد و کوچک‌ترین حذف شود؛ زیرا تنها یک جابه‌جایی لازم دارد.
• heapq.heapreplace(heap, item) مقدار کوچک‌ترین را حذف می‌کند و بلافاصله مقدار جدید را جایگزین می‌کند. تفاوت با heappushpop در ترتیب اجراست (pushpop ابتدا push انجام می‌دهد سپس pop).
• heapq.merge دنباله‌های مرتب را به صورت lazy (تنبل) ادغام می‌کند و حافظهٔ اضافی کمی مصرف می‌کند؛ برای ادغام چند فایل بزرگ مرتب مناسب است.

مثال merge

import heapq

a = [1,4,7]
b = [2,5,8]
c = [3,6,9]

for v in heapq.merge(a,b,c):
    print(v, end=' ')

heapq.merge سه لیست مرتب را به ترتیب صعودی ادغام می‌کند و یک iterator برمی‌گرداند؛ این روش بهتر از الحاق و سپس مرتب‌سازی مجدد است وقتی که هر رشته قبلاً مرتب است.

موارد کاربرد واقعی و نکات حرفه‌ای

• صف‌های اولویت در الگوریتم‌هایی مثل Dijkstra یا A* (در مسائل گراف و مسیر یابی).
• پیاده‌سازی سریع top-k نتایج در تحلیل داده (مثلاً یافتن 100 مقالهٔ پربازدید از میلیون‌ها رکورد).
• ادغام جریانات مرتب (log merge، پردازش دسته‌ای داده‌ها).

نکتهٔ مهم: heapq تنها تضمین می‌کند که عنصر صفر کوچک‌ترین است؛ بقیهٔ عناصر heap مرتب نیستند (فقط ساختار heap برقرار است). اگر به همواره مرتب بودن کل مجموعه نیاز دارید بهتر است از sorted list یا سایر ساختارها استفاده کنید.

رعایت نکات ظریف و خطاهای رایج

• heapq از مقایسهٔ عناصر استفاده می‌کند، بنابراین اگر اشیاء قابل مقایسه نباشند باید کلید (priority) را به‌صورت تاپل اضافه کنید.
• برای حفظ ترتیب پایدار (stable) هنگام یکسان بودن اولویت‌ها می‌توان از شمارندهٔ افزایشی استفاده کرد: (priority, count, item).
• کتابخانهٔ heapq به‌صورت ذاتی thread-safe نیست؛ برای استفادهٔ هم‌زمان از آن در محیط چندریسمانی باید از قفل (Lock) استفاده کنید یا از queue.PriorityQueue بهره ببرید.

نمونهٔ پیشرفته — صف اولویت با ثبات

import heapq
import itertools

pq = []
counter = itertools.count()  # شمارندهٔ افزایشی برای پایداری

def push(pq, priority, item):
    heapq.heappush(pq, (priority, next(counter), item))

def pop(pq):
    return heapq.heappop(pq)[2]

push(pq, 1, 'taskA')
push(pq, 1, 'taskB')
push(pq, 0, 'taskC')

print(pop(pq))  # taskC
print(pop(pq))  # taskA (یا taskB بر اساس ترتیب وارد شدن)

در این الگو با اضافه‌کردن شمارنده، هنگام مساوی‌بودن اولویت ترتیبِ ورود حفظ می‌شود که در سیستم‌های صف‌اولویت بسیار سودمند است.

جمع‌بندی و منابع جایگزین

heapq یک ابزار سبک، سریع و استاندارد برای کار با صف‌های اولویت و عملیات top-k در پایتون است. اگر نیاز به قابلیت‌های بیشتر مثل حذف عناصر میانی از heap یا ساختارهای موازی دارید، می‌توانید از کتابخانه‌هایی مانند sortedcontainers، heapdict یا queue.PriorityQueue استفاده کنید. در اغلب کاربردهای معمولِ استخراج کوچک‌ترین/بزرگ‌ترین و ادغام دنباله‌ها، heapq راهکاری ساده و کارا ارائه می‌دهد.

لطفاً از کمبود ها و مشکلات این محتوا برای ما بنویسید

ارسال