الكومة وقوائم الأولوية
ما هي الكومة؟
الكومة هي شجرة ثنائية كاملة حيث يفي كل والد بخاصية الكومة - إما أصغر دائمًا (min-heap) أو دائمًا أكبر (max-heap) من أبنائها. "مكتمل" يعني أن كل مستوى ممتلئ باستثناء المستوى الأخير، الذي يتم ملؤه من اليسار إلى اليمين.
1 Min-heap
/ \
3 5
/ \
7 4
ولأنه مكتمل، نقوم بتخزينه في مصفوفة مسطحة - دون الحاجة إلى مؤشرات. بالنسبة للفهرس i: الطفل الأيسر = 2i + 1، الطفل الأيمن = 2i + 2، الأصل = (i - 1) // 2.
مين-هيب مقابل ماكس-هيب
| عقار | مين كومة | ماكس الكومة | |----------|---------|----------| | الجذر | أصغر عنصر | العنصر الأكبر | | الوالدين ≥ الأطفال؟ | ✅ نعم | ❌ لا (≥) | | استخراج يعطي | الحد الأدنى | الحد الأقصى |
بايثون heapq هو min-heap بشكل افتراضي. بالنسبة إلى الكومة القصوى، قم بإلغاء القيم عند الإدراج ونفيها مرة أخرى عند الاستخراج.
إدراج واستخراج - خطوة بخطوة
إدراج - اضغط حتى النهاية، ثم فقاعة لأعلى (قم بالتبديل مع العنصر الرئيسي عندما تكون أصغر):
import heapq
h = [1, 3, 5, 7]
heapq.heappush(h, 2) # h becomes [1, 2, 5, 7, 3]
استخرج الحد الأدنى - قم بتبديل الجذر بالعنصر الأخير، ثم انتقل إلى العنصر الأخير، ثم غربل (قم بالتبديل مع العنصر الأصغر):
smallest = heapq.heappop(h) # returns 1
يتم تشغيل كلتا العمليتين في O(log n) لأن ارتفاع الشجرة هو log n.
Heapify - بناء كومة في O(n)
يؤدي استدعاء heapq.heapify(arr) إلى تحويل القائمة إلى كومة في O(n)، وليس O(n log n). إنه يعمل من الأسفل إلى الأعلى، ويغربل كل عقدة غير ورقية. هذه واحدة من نتائج التعقيد الأكثر إثارة للدهشة في علوم الكمبيوتر.
مناقشة
تسجيل الدخول للانضمام إلى النقاش