Heap بالعربي للمستوى المتوسط: لاقي أعلى 100 سعر من مليون منتج في 18ms

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

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

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

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 لأنه دالة في موقع المستخدم). الكود الأصلي:

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

الفرق بين 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).