طابور الأولوية heapq
طابور لا يحترم الأقدمية: يخرج منه الأهم دائمًا. ⏱ نحو 30 دقيقة.
- تشرح طابور الأولوية وتقارن طرق تنفيذه.
- تشرح فكرة الكومة الصغرى وتمثيلها في قائمة.
- تستخدم
heappushوheappopوheapifyوnlargest. - تطبق الكومة على الجدولة واختيار أفضل
kعنصر.
١طابور يخرج منه الأهم لا الأقدم
في الطوارئ لا يُخدم المريض حسب وقت وصوله، بل حسب خطورة حالته. هذا طابور الأولوية Priority Queue: كل عنصر له أولوية، ونُخرج دائمًا الأعلى أولوية.
| التنفيذ | إضافة | إخراج الأصغر |
|---|---|---|
| قائمة عادية | O(1) | O(n): نبحث عن الأصغر |
| قائمة مرتبة | O(n): نُدرج في مكانه | O(1) |
| الكومة Heap | O(log n) | O(log n) |
الكومة توازن بين الاثنين، فهي الخيار الأفضل حين تتكرر الإضافة والإخراج معًا.
٢الكومة: شجرة في قائمة
عند الإضافة نضع العنصر في آخر القائمة ثم «يطفو» بالتبديل مع أبيه ما دام أصغر منه. وعند الإخراج نأخذ الجذر، ونضع آخر عنصر مكانه ثم «يغطس». كل منهما بعدد مستويات الشجرة: O(log n).
٣مكتبة heapq
import heapq er = [] # (الخطورة، الاسم): الأصغر أخطرheapq.heappush(er, (3, "التواء كاحل"))heapq.heappush(er, (1, "أزمة قلبية"))heapq.heappush(er, (2, "كسر"))heapq.heappush(er, (5, "زكام")) print("القائمة الداخلية:", er)while er: level, case = heapq.heappop(er) print("الآن:", case, "| الخطورة", level)
العناصر tuple: يقارن بايثون العنصر الأول (الأولوية) أولًا. و heapq كومة صغرى: يخرج الأصغر. ولكومة كبرى نخزن سالب الأولوية.
٤أشهر الاستخدامات
import heapq scores = [72, 95, 64, 88, 99, 51, 83, 90, 77, 60] # 1) أكبر 3 وأصغر 3: O(n log k)print(heapq.nlargest(3, scores))print(heapq.nsmallest(3, scores)) # 2) تحويل قائمة إلى كومة في المكان: O(n)h = list(scores)heapq.heapify(h)print("الأصغر:", h[0]) # 3) دمج قوائم مرتبة كثيرةprint(list(heapq.merge([1, 4, 9], [2, 3, 10], [5, 6])))
٥مثال: جدولة مهام الخادم
خادم ينفّذ المهام بالأولوية، وعند التساوي بترتيب الوصول. نضيف رقم وصول متسلسلًا في الـ tuple ليفصل بين المتساويين:
import heapq tasks = []arrival = 0def submit(priority, name): global arrival heapq.heappush(tasks, (priority, arrival, name)) arrival += 1 submit(2, "إرسال تقرير")submit(1, "دفع فاتورة")submit(2, "نسخ احتياطي")submit(3, "تنظيف الملفات المؤقتة")submit(1, "تسجيل دخول") while tasks: p, _, name = heapq.heappop(tasks) print(p, name)
توقّع وتحقّق
heapq.heappop يُخرج:
تعقيد heappush:
ابنا العقدة في الموقع i:
لكومة كبرى بـ heapq نخزن:
x.الخلاصة
- طابور الأولوية يُخرج الأهم أولًا.
- الكومة: إضافة وإخراج
O(log n)، والأصغر فيh[0]. heapqكومة صغرى، وللكبرى نخزن السالب.- (الأولوية، رقم الوصول، العنصر) لحل التساوي.
تحدٍّ برمجي: أسرع 3 متسابقين أثناء السباق
متوسطنتائج سباق تصل واحدة واحدة (الاسم، الزمن بالثواني). احتفظ بكومة كبرى حجمها 3 لأسرع ثلاثة دون ترتيب كل النتائج، ثم اطبعهم من الأسرع.
- خزّن (-الزمن، الاسم) لتصبح الكومة كبرى.
- إن زاد حجمها عن 3 أخرج الأبطأ بـ heappop.
- اطبع في الآخر الثلاثة من الأسرع: الاسم ثم الزمن.
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
import heapqresults = [("أحمد", 52.4), ("سالم", 49.8), ("فهد", 55.1), ("عمر", 48.9), ("ماجد", 50.2), ("زياد", 51.0)]
💡 تلميح 1
💡 تلميح 2
sorted(top, reverse=True) يرتب من الأسرع.حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
import heapqresults = [("أحمد", 52.4), ("سالم", 49.8), ("فهد", 55.1), ("عمر", 48.9), ("ماجد", 50.2), ("زياد", 51.0)] top = []for name, t in results: heapq.heappush(top, (-t, name)) if len(top) > 3: heapq.heappop(top) for neg_t, name in sorted(top, reverse=True): print(name, -neg_t)