2.38. قوائم الانتظار ذات الأولوية

قائمة الانتظار ذات الأولوية هي حاوية تعرف دائماً أيُّ عناصرها هو الأصغر (أو الأكبر) دون فرز المحتوى بأكمله. تنفّذ heapq واحدة في MicroPython باستخدام list عادية كوسيلة تخزين وخوارزمية شجرية تُسمى min-heap للإبقاء على العنصر الأصغر في الفهرس 0.

2.38.1. النموذج الذهني

إن min-heap هي قائمة مرتبة بحيث يكون العنصر عند كل فهرس أصغر من أو مساوياً للعناصر عند الفهرسين 2*i + 1 و 2*i + 2. هذا الترتيب يجعل ثلاث عمليات منخفضة الكلفة:

• إيجاد العنصر الأصغر -- فهو موجود عند heap[0]. عملية بحث واحدة بالفهرس، دون أي مسح.

• إضافة عنصر -- يصعد عبر الشجرة، مقارناً نفسه بأبٍ واحد في كل مستوى. ألف عنصر تكلّف نحو عشر مقارنات؛ ومليون تكلّف نحو عشرين.

• إزالة العنصر الأصغر -- المسار نفسه بالعكس، وبالعدد القليل ذاته من المقارنات.

القائمة ليست مفروزة. والتكرار عليها يعطي العناصر بترتيب اعتباطي. وحده heap[0] مضمونٌ أن يكون الأصغر.

2.38.2. الدوال الثلاث في MicroPython

تكشف heapq في MicroPython عن ثلاث دوال بالضبط:

• heapq.heappush() -- يُدرج عنصراً مع الحفاظ على ثابتية الكومة سليمة.

• heapq.heappop() -- يزيل العنصر الأصغر ويعيده.

• heapq.heapify() -- يعيد ترتيب قائمة موجودة لتصبح كومة في مكانها.

هذه هي الواجهة الكاملة. أما heappushpop و heapreplace و nlargest و nsmallest و merge الموجودة في CPython فهي غير متوفرة؛ وتوضّح الأنماط أدناه كيفية بناء الشائع منها يدوياً.

البدء من الصفر:

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, 5)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 3)
>>> heap
[1, 5, 3]
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
3
>>> heapq.heappop(heap)
5

البدء من بيانات موجودة:

>>> samples = [5, 1, 3, 2, 4]
>>> heapq.heapify(samples)
>>> samples
[1, 2, 3, 5, 4]
>>> heapq.heappop(samples)
1

تمرّ عملية heapify على كل عنصر مرة واحدة وهي أسرع بشكل ملحوظ من دفع العناصر نفسها واحداً تلو الآخر.

2.38.3. أكبر N عبر تدفق

استخدام طبيعي لقائمة الانتظار ذات الأولوية: تتبّع أكبر N عنصر في تدفق لا يمكنك قراءته إلا مرة واحدة.

الحيلة هي الإبقاء على min-heap بحجم N. كل قيمة جديدة تُدفع؛ وإذا تجاوز حجم الكومة N، أسقِط العنصر الأصغر. والعنصر الأصغر موجود دائماً عند heap[0]، لذا تكفي مقارنة واحدة لتحديد ما إذا كان يُحتفظ بكل عنصر وارد أو يُتجاهل:

def top_n_brightest(readings, n):
    heap = []
    for r in readings:
        if len(heap) < n:
            heapq.heappush(heap, r)
        elif r > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, r)
    return sorted(heap, reverse=True)

لا تتجاوز الكومة أبداً الحجم N، لذا تكلّف كل قيمة واردة العدد القليل نفسه من المقارنات مهما طال التدفق. وعملية sorted النهائية هي الخطوة الوحيدة التي تعتمد كلفتها على N مباشرة.

2.38.4. الأحداث المجدولة

إن قائمة انتظار ذات أولوية من صفوف (deadline, payload) هي الصيغة المعيارية لمجدول الأحداث. تُقارَن الصفوف معجمياً، لذا يطفو الصف ذو الموعد النهائي الأصغر إلى القمة تلقائياً:

import heapq
import time

queue = []
heapq.heappush(queue, (time.time() + 5, 'check sensors'))
heapq.heappush(queue, (time.time() + 1, 'blink LED'))
heapq.heappush(queue, (time.time() + 3, 'send heartbeat'))

while queue:
    deadline, task = queue[0]
    now = time.time()
    if now < deadline:
        time.sleep(deadline - now)
    heapq.heappop(queue)
    run(task)

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

counter = 0
def schedule(deadline, task):
    global counter
    counter += 1
    heapq.heappush(queue, (deadline, counter, task))

الآن أصبح سلوك الأصغر-موعداً-أولاً سليماً، وتُحَلّ حالات التعادل بالعدّاد فتُنفَّذ المهام المجدولة أبكر أولاً، ولا يحتاج task إلى أن يكون قابلاً للمقارنة.

2.38.5. ما الذي لا توفّره لك heapq

بعض الأنماط التي تبدو وكأنها ينبغي أن تعمل، لكنها لا تعمل:

• إن التكرار for x in heap لا يعطي مخرجات مفروزة -- فالترتيب الأساسي للقائمة هو تخطيط شجرة الكومة. ولاستهلاك الكومة بالترتيب، استخدم heappop حتى تفرغ.

• لا توجد طريقة لتغيير أولوية عنصر موجود مسبقاً في الكومة. والحل المعتاد هو دفع الأولوية الجديدة كمدخل جديد ووسم القديم على أنه ملغى (تجاوزه عند ظهوره).

• تخزّن الكومة مراجع إلى عناصرها، لا نُسخاً منها. وتعديل عنصر بعد دفعه قد يكسر ثابتية الكومة. استخدم قيماً غير قابلة للتغيير (أرقام، صفوف) كمفتاح للمقارنة.

إن min-heap على قائمة عادية هي الأداة المناسبة لأي سؤال من نوع "ما الأصغر" أو "ما الأكثر إلحاحاً" على جهاز مدمج صغير. ثلاث دوال، وقائمة واحدة، وتتكفّل الكومة بالباقي.