المكتبة العربية لعلوم الحاسوب
مرحباً بالخوارزميات › الأكوام (Heaps) 10 / 19 السابق التالي

تمارين

مراجعة المفاهيم

كيف تتغير الكومة بعد إدراج العدد 10؟

تمثّل المصفوفة [9, 7, 8, 3, 5] كومة عظمى. والآن أدخل العدد 10.

  1. أضف 10 أولاً إلى نهاية المصفوفة. فما قيمة عقدة أبيه؟
  2. بدءاً من العقدة الجديدة، نفّذ تعديل الكومة من الأسفل إلى الأعلى، واكتب المصفوفة بعد كل تبديل.
  3. ما العنصر العلوي النهائي للكومة؟ وكم عدد التبديلات الإجمالي؟

الإجابة

  1. بعد إضافة 10 يصبح فهرسه 5، ومن ثمّ فهرس أبيه ⌊(5−1)/2⌋=2\lfloor(5-1)/2\rfloor=2. وقيمة عقدة الأب تساوي 8.

  2. بما أن 10 أكبر من 8، تصبح المصفوفة بعد التبديل الأول [9, 7, 10, 3, 5, 8]. وبما أن 10 أكبر أيضاً من أبيه 9، تصبح المصفوفة بعد التبديل الثاني [10, 7, 9, 3, 5, 8]. وقد وصلت القيمة 10 الآن إلى العقدة الجذرية، فاكتمل تعديل الكومة.

  3. العنصر العلوي النهائي هو 10، ويحدث تبديلان إجمالاً.

التحقق من علاقات الأب والابن في كومة صغرى

تمثّل المصفوفة [1, 4, 3, 7, 6, 2] شجرة ثنائية كاملة. وفي الكومة الصغرى، يجب ألا تكون أي عقدة أب أكبر من أبنائها. وبالنسبة إلى الفهرس ii، يكون فهرسا الابن الأيسر والأيمن 2i+12i+1 و2i+22i+2 على الترتيب.

  1. ما فهرستا وقيمتا ابني الفهرس 2؟
  2. قيمة العقدة عند الفهرس 2 هي 3. فهل تخالف قاعدة الكومة الصغرى مع ابنها؟ وإن كان الأمر كذلك، فما العنصران الواجب تبديلهما؟
  3. بناءً على إجابتك عن السؤال 2، اكتب المصفوفة بعد التبديل إن كانت القاعدة قد خُولفت؛ وإلا فاشرح سبب عدم الحاجة إلى تبديل. وأخيراً، تحقق من علاقات الأب والابن المتبقية.

الإجابة

  1. الابن الأيسر للفهرس 2 يقع عند الفهرس 5 وقيمته 2. أما فهرس الابن الأيمن فهو 6، لكن طول المصفوفة 6، لذا لا وجود للابن الأيمن.

  2. قيمة الأب 3 أكبر من قيمة الابن 2، وهذا يخالف قاعدة الكومة الصغرى. وينبغي تبديل العنصرين عند الفهرسین 2 و5.

  3. بعد التبديل تصبح المصفوفة [1, 4, 2, 7, 6, 3]. ولنتحقق من كل علاقة: 1 ≤ 4، 1 ≤ 2؛ 4 ≤ 7، 4 ≤ 6؛ و2 ≤ 3. ولم يعد أي أب أكبر من أبنائه، فتحققت قاعدة الكومة الصغرى.

الاحتفاظ بأكبر ثلاثة أعداد باستخدام كومة صغرى

للاحتفاظ بأكبر 3 أعداد من تدفّق البيانات [4, 1, 7, 3, 8]، حافظ على كومة صغرى لا تحتوي على أكثر من 3 عناصر.

أدرِج الأعداد الثلاثة الأولى أولاً في الكومة الصغرى بالترتيب. وبعد أن تمتلئ الكومة، لكل عدد جديد: إن كان أكبر من العنصر العلوي، فاحذف العنصر العلوي وأدرج العدد الجديد؛ وإلا فاترك الكومة دون تغيير.

بعد قراءة كل عدد، اكتب الأعداد المحتفظ بها في الكومة والعنصر العلوي. واكتب الأعداد المحتفظ بها على هيئة مجموعة؛ ولا حاجة إلى ذكر ترتيبها في مصفوفة الكومة.

الإجابة

تكون النتيجة بعد قراءة كل عدد كما يلي:

العدد المقروء الأعداد المحتفظ بها العنصر العلوي
4 {4} 4
1 {1, 4} 1
7 {1, 4, 7} 1
3 {3, 4, 7} 3
8 {4, 7, 8} 4

بعد امتلاء الكومة، يكون عنصرها العلوي أصغر الأعداد المحتفظ بها حالياً. ولا يستبدل العدد الجديد العنصر العلوي إلا إذا كان أكبر منه. والمجموعة النهائية {4, 7, 8} تحتوي بالضبط على أكبر 3 أعداد.

تمارين برمجية

إيجاد العنصر الأكبر بالمرتبة k في مصفوفة

بمعطى مصفوفة أعداد صحيحة nums وعدد صحيح kk، حيث 1≤k≤n1 \le k \le n و nn هو طول المصفوفة، أعد العنصر الذي سيظهر في الموضع kk لو رُتّبت المصفوفة من الأكبر إلى الأصغر.

احسب العناصر المكررة بصورة منفصلة. على سبيل المثال، ثاني أكبر عنصر في [5, 5, 2] يبقى 5. واستخدم كومة صغرى لا تحتوي على أكثر من kk عنصر.

تلميحات

  1. العنصر الأكبر بالمرتبة k هو أصغر الأعداد بين أكبر k عدداً
  2. أدرِج كل عدد في الكومة الصغرى، واحذف أصغر قيمة كلما تجاوز حجم الكومة k
  3. بعد انتهاء الاجتياز، تحتوي الكومة على أكبر k عدداً، ويكون عنصرها العلوي هو الجواب

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

السابق ملخص التالي الرسم البياني