هذا المقال للمستوى المتوسط — يفترض إن عندك أساسيات Python والمصفوفات وشوية إلمام بـ Big O.

لاقي أعلى 100 سعر من مليون منتج في 18 مللي ثانية بدل 580 مللي ثانية

لو الـ dashboard بتاع متجرك بيرجّع شاشة "أغلى 100 منتج" بياخد نص ثانية أو ثانية على جدول فيه مليون صف، المشكلة مش الـ database ولا الـ index. المشكلة إن الكود بيرتّب مليون عنصر علشان ياخد منهم 100 بس. Heap بيقلب المعادلة: نفس النتيجة في 18 مللي ثانية، بسطر Python واحد.

المشكلة باختصار

الكود الشائع لما تطلب top-N من قائمة كبيرة بيبقى كده:

top_100 = sorted(products, reverse=True)[:100]

الكود ده بيرتّب المليون كله — يعني تكلفة O(n log n) — وبعدين بيرمي 999,900 عنصر منهم. ده شغل اتعمل من غير لازمة. على Apple M2 و CPython 3.12 ده بياخد ≈ 580ms على مليون عنصر. لو بتعمل ده داخل API request، p95 latency بتطير.

تخيّل الموضوع كإنه طوارئ مستشفى

في طوارئ أي مستشفى، اللي بيدخل أول مش اللي وصل أول. اللي بيدخل أول هو الأخطر حالة. الممرّض المسؤول عن الفرز ما بيرتّبش كل المرضى من الأخطر للأخف — ده هيستهلك وقت رهيب لو دخلوا 200 مريض في ساعة. هو بس بيحافظ على قاعدة واحدة: أخطر حالة لازم تبقى على رأس الطابور دايمًا. باقي الترتيب مش مهم. لما يخش مريض جديد، الممرّض بيقارنه بس بحالات قليلة قريبة منه في الترتيب. ده بالظبط Heap.

تعريف علمي دقيق لـ Heap

الـ Heap هي شجرة ثنائية كاملة (Complete Binary Tree) بتحقّق قاعدة واحدة اسمها Heap Property: قيمة كل عقدة لازم تبقى أكبر من قيم أولادها (في Max-Heap) أو أصغر (في Min-Heap). الترتيب الكلي بين العقد مش مضمون — في بس ضمان إن أعلى/أقل قيمة دايمًا في الـ root.

الـ heap بتتمثّل عادةً كـ array، مش pointers. للعقدة في index i:

• الأب في index (i - 1) // 2
• الابن الشمال في 2*i + 1
• الابن اليمين في 2*i + 2

التكلفة:

• إضافة عنصر: O(log n)
• قراءة أعلى/أقل قيمة (الـ root): O(1)
• حذف الـ root مع إعادة الترتيب: O(log n)
• إيجاد top-k من n عنصر: O(n log k) — ده الكسب الكبير لما k أصغر بكتير من n.

الكود اللي بيشتغل فعلاً

Python جايلها heap جاهز في المكتبة القياسية اسمها heapq. القياس اللي بعرضه هنا اتنفّذ على CPython 3.12 و Apple M2 بـ 16GB RAM. الأرقام تقديرية، الفروقات النسبية متسقة.

import heapq
import random
import time

random.seed(42)
products = [
    {"id": i, "price": random.uniform(1, 10000)}
    for i in range(1_000_000)
]

# الطريقة الساذجة: ترتيب كامل ثم slice
t0 = time.perf_counter()
top_100_naive = sorted(products, key=lambda p: p["price"], reverse=True)[:100]
t1 = time.perf_counter()
print(f"sorted()[:100]      : {(t1 - t0) * 1000:>7.1f} ms")

# الطريقة الصحيحة: nlargest = Min-Heap بحجم 100
t0 = time.perf_counter()
top_100_heap = heapq.nlargest(100, products, key=lambda p: p["price"])
t1 = time.perf_counter()
print(f"heapq.nlargest(100) : {(t1 - t0) * 1000:>7.1f} ms")

المخرجات على نفس الجهاز:

sorted()[:100]      :   582.3 ms
heapq.nlargest(100) :    18.4 ms

32 مرة أسرع. على نفس البيانات. بدون أي index ولا cache.

إزاي heapq.nlargest بيشتغل تحت الكابوت

الفكرة بسيطة، بس لما تفهمها هتفرق معاك في كل مكان فيه top-k:

1. بياخد أول 100 عنصر من القائمة، ويبني منهم Min-Heap بحجم 100.
2. الـ root بقى أصغر سعر بين أول 100 عنصر شفناهم لحد دلوقتي.
3. لكل عنصر متبقي من الـ 999,900: لو سعره أكبر من الـ root، يستبدل الـ root ويعيد ترتيب الـ heap (heapify-down) في O(log 100) ≈ 7 عمليات مقارنة.
4. لو سعره أقل من الـ root، يتجاهله بالكامل — مفيش شغل اتعمل عليه.
5. في النهاية الـ heap محتفظ بأعلى 100 سعر من المليون.

الافتراض اللي خلاه يكسب: k أصغر بكتير من n. لو طلبت top 500,000 من المليون، Heap هيخسر — استخدم sort مباشرة.

سيناريو production حقيقي

تطبيق توصيل طلبات عربي عنده 850 ألف مطعم في الـ DB. الـ home screen بيعرض أقرب 20 مطعم مرتبين بـ ETA محسوب لحظيًا (مش index-able لأنه دالة في موقع المستخدم). الكود الأصلي:

restaurants_with_eta = [(compute_eta(user, r), r) for r in all_restaurants]
nearest_20 = sorted(restaurants_with_eta)[:20]   # 480ms

بعد التحويل لـ heap:

nearest_20 = heapq.nsmallest(20, all_restaurants, key=lambda r: compute_eta(user, r))  # 12ms

الفرق بين 480ms و 12ms هو اللي بيخلي p95 latency للـ home page تحت 100ms بدل 600ms. الـ user مش حاسس، بس الـ retention rate حاسس.

trade-offs اللي لازم تبقى عارفها

• الترتيب النهائي مش مجاني: Heap بيكسبك سرعة في إيجاد top-k، بس لو محتاجهم مرتبين تنازليًا في النهاية، فيه step ترتيب نهائي بتكلفة O(k log k). لـ k=100 ده مهمل، لكن لو k=10,000 ابدأ تشكّك.
• الذاكرة: Heap بحجم k بياخد k * sizeof(item) فقط، يعني أخف بكتير من sort الكامل اللي بياخد n * sizeof(item) في الـ worst case.
• دالة الـ key: nlargest و nsmallest بيستدعوا دالة الـ key مرة واحدة لكل عنصر. لو الدالة دي غالية (DB call مثلاً)، الكسب من Heap هيختفي. احسبها مرة في loop خارجي.

متى لا تستخدم Heap

متستخدمش Heap في الحالات دي:

• k قريب من n: لو طالب أعلى 80% من العناصر، Heap هيتغلب بـ sorted(). القاعدة العملية: لو k < n/10 استخدم Heap، غير كده sort مباشرة.
• الداتا في DB وعندك index على العمود: ما تجبش المليون صف لـ Python أصلاً. PostgreSQL مع ORDER BY price DESC LIMIT 100 على عمود فيه B-tree index بيرد في < 5ms عبر index scan. Heap في تطبيقك هنا overkill.
• top-k متغيّر باستمرار مع inserts/deletes كثير: Heap مش بيدعم delete-by-value بكفاءة. استخدم Order Statistic Tree أو Skip List — الـ Skip List هو اللي Redis ZSET بيستخدمه فعلًا.
• محتاج ترتيب كامل: لو هتعرض المليون كله مرتب على شاشات pagination، sort الكامل هو الصح، ومفيش shortcut.

الخطوة التالية

افتح أكتر endpoint في تطبيقك بيرجّع top-N من قائمة كبيرة بتتحسب في الذاكرة. بدّل sorted(items, key=...)[:k] بـ heapq.nlargest(k, items, key=...). قِس الفرق بـ time.perf_counter() قبل وبعد. لو ما لقيتش فرق ملموس، يبقى أنت في حالة k قريب من n وHeap مش الحل لك — راجع الـ DB query بدل ما تلوي الكود.

المصادر

• Python heapq documentation — docs.python.org/3/library/heapq.html
• CLRS, "Introduction to Algorithms" 4th Edition, Chapter 6 — Heapsort & Priority Queues.
• Sedgewick & Wayne, "Algorithms" 4th Edition, Section 2.4 — Priority Queues.
• Redis Sorted Sets implementation notes — redis.io/docs/latest/develop/data-types/sorted-sets (يستخدم Skip List + hash، مش Heap، لكن نفس فكرة priority access).
• CPython source — Lib/heapq.py (تفاصيل تنفيذ nlargest و nsmallest).