Python/heapq

تقدّم هذه الوحدة وسيلة لاستخدام خوارزمية طابور الكومة heap queue والتي تعرف كذلك بخوارزمية طابور الأولوية priority queue.

الكومات Heaps هي مشجّرات ثنائية binary trees تمتلك كل عقدة أبوية parent node فيها قيمة تكون أصغر من أو مساوية لأي قيمة أخرى في العقد البنوية children.

تستخدم الوحدة مصفوفات تكون فيها heap[k] <= heap[2*k+1]‎ و heap[k] <= heap[2*k+2]‎ لجميع قيم k، ويبدأ عدّ العناصر من الصفر. ولغرض المقارنة، تُعدّ العناصر غير الموجودة ما لا نهائية. أما أهمّ خصائص الكومة هو أنّ أصغر عنصر فيها هو الجذر دائمًا، ويعبر عنه heap[0]‎.

جدير بالذكر أنّ الواجهة البرمجية الخاصة بهذه الوحدة تختلف عن خوارزميات الكومة التي ترد في الكتب الدراسية من ناحيتين:

أ - تستخدم هذه الوحدة فهرسة تبدأ من الصفر، وهذا يجعل العلاقة بين الفهرس الخاص بعقدة وفهارس العقد المتفرّعة عنها أقل وضوحًا ولكنّها أكثل ملائمة؛ وذلك لأنّ لغة بايثون تعتمد عملية الفهرسة التي تبدأ من الصفر.

ب - تعيد الدالة pop()‎ في هذه الوحدة العنصر الأصغر وليس الأكبر (يسمى في الكتب الدراسية "min-heap"، والشائع هو استخدام "max heap" في الكتب الدراسية لأنّه أكثر ملائمة لعمليات الفرز الموقعية).

يتيح وجها الاختلاف هذان على النظر إلى الكومة على أنّها قائمة بايثون عادية دون أي مفاجئات: فالتعبير heap[0]‎ يمثّل أصغر عنصر، ويحافظ التعبير heap.sort()‎ على الكومة ثابتة.

يمكن إنشاء الكومة إمّا عن طريق استخدام قائمة تأخذ القيمة الأولية []، أو يمكن تحويل قائمة ذات عناصر إلى كومة باستخدام الدالة heapify()‎.

دوال الوحدة heapq

تقدّم وحدة heapq الدوال التالية:

الدالة heappush()‎

تدرج الدالة القيمة item إلى الكومة heap، مع الحفاظ على ثبات الكومة.

الدالة heappop()‎

تحذف الدالة وتعيد أصغر عنصر في الكومة heap، مع الحفاظ على ثبات الكومة.

الدالة heappushpop()‎

تضيف الدالة العنصر المعطى إلى الكومة، ثم تحذف وتعيد أصغر عنصر في الكومة.

الدالة heapify()‎

تحوّل الدالة القائمة المعطاة إلى كومة، في نفس المكان، وفي زمن خطي linear time.

الدالة heapreplace()‎

تحذف الدالة وتعيد أصغر عنصر في الكومة، وتضيف كذلك العنصر الجديد المعطى.

الدالة heapmerge()‎

تدمج الدالة عدة مدخلات مفروزة في مخرج مفرد مفروز.

الدالة nlargest()‎

تعيد الدالة قائمة تضمّ n من أكبر العناصر في مجموعة البيانات dataset المعرّفة بواسطة المكرَّرات.

الدالة nsmallest()‎

تعيد الدالة قائمة تضمّ n من أصغر العناصر في مجموعة البيانات dataset المعرّفة بواسطة المكرَّرات.

أمثلة بسيطة

يمكن إنجاز عملية heapsort عن طريق دفع كل القيم إلى الكومة ثم حذف القيمة الصغرى في كل مرة:

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

هذه العملية مشابهة للتعبير sorted(iterable)‎ ولكنّها ليس مستقرّة مثلها.

يمكن لعناصر الكومة أن تكون صفوفًا، ويفيد هذا في إسناد قيم المقارنة (مثل أولويات المهام) إلى جانب العنصر الرئيسي الذي يجري تعقبه:

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

ملاحظات على خوارزمية طابور ألأولوية

ابور الأولوية هو من الاستخدامات الشائعة للكومات، ولكن استخدام هذه الخوارزمية ينطوي على عدد من التحديات:

• استقرارية عملية الفرز: كيف يمكن الحصول على مهمّتين لهما نفس الأولوية وتعادان بنفس ترتيب إضافتها؟
• المقارنة الصفية Tuple comparison للأزواج (priority, task) غير صالحة إن كانت الألولويات متساوية، وكانت المهام لا تمتلك ترتيب مقارنة افتراضي.
• إن حدث تغيير في أولوية إحدى المهمّات، فكيف يمكن حينئذ نقل المهمّة إلى الموقع الجديد في الكومة؟
• أو إن كان يجب حذف إحدى المهمّات المعلّقة pending، فكيف يمكن العثور على تلك المهمّة وحذفها من الطابور؟

يمكن التغلب على التحدّيين الأولين بتخزين العناصر كقائمة ثلاثية، تتضمن الأولوية وتعداد العنصر والمهمّة. يفيد تعداد العنصر هنا في التغلب على مشكلة تساوي الأولوية بين مهمّتين حيث تعاد المهمّتان حسب ترتيب الإضافة، وإذا علمنا أنّه لا يمكن لعنصرين أن يمتلكا نفس التعداد، فإنّه لن تعُقد مقارنة صفّية مباشرة بين مهمّتين على الإطلاق.

هناك حل آخر لمشكلة عدم القدرة على مقارنة المهمّام وتتلخّص في إنشاء صنف تغليف wrapper class يتجاهل المهمّة ويقارن الأولويات فقط:

‎from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

تتمحور بقية المشاكل حول العثور على المهامّ المعلقة وتغيير أولويتها أو حذفها من الكومة نهائيًا. يمكن العثور على مهمّة معينة بواسطة قاموس يشير إلى عنصر معين في الكومة.

ولكن حذف العنصر أو تغيير أولويته لا يخلو من صعوبة؛ ذلك لأنّه قد يؤدي إلى إفساد بنية الكومة الثابتة. من الحلول المحتملة لهذه المشكلة هو تعليم العنصر على أنّه عنصر محذوف وإضافة عنصر جديد يمتلك الأولوية المعدّلة:

pq = []                         # قائمة بالعناصر المرتّبة في الكومة
entry_finder = {}               # ربط المهام بالعناصر
REMOVED = '<removed-task>'      # عنصر يحلّ محل المهمّة المحذوفة
counter = itertools.count()     # تعداد تسلسل فريد

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

مصادر

صفحة Heap queue algorithm في توثيق بايثون الرسمي.