مسألة أعلى k

سنستعرض في هذه المسألة أولاً حلين مباشرين نسبياً، ثم حلاً أكثر كفاءة قائماً على الكومة.

الطريقة 1: الاختيار التكراري

يمكننا إجراء $k$ جولة من الاجتياز كما يوضح الشكل أدناه، فنستخرج في كل جولة العناصر $1^{st}$ و$2^{nd}$ و$\dots$ و$k^{th}$ الأكبر، بتعقيد زمني $O(nk)$.

لا تناسب هذه الطريقة إلا الحالة $k \ll n$، لأنه عندما يقترب $k$ من $n$ يقترب التعقيد الزمني من $O(n^2)$، وهو ما يجعل الكفاءة منخفضة جداً.

الطريقة 2: الترتيب

كما يوضح الشكل أدناه، يمكننا أولاً ترتيب المصفوفة nums، ثم إعادة العناصر $k$ الواقعة في أقصى اليمين، بتعقيد زمني $O(n \log n)$.

من الواضح أن هذه الطريقة تبذل جهداً أكبر من اللازم، لأننا نحتاج فقط إلى إيجاد أكبر $k$ عنصر بدلاً من ترتيب العناصر الأخرى.

الطريقة 3: الكومة

يمكننا حل مسألة أعلى k بكفاءة أكبر باستخدام كومة، كما يوضح الشكل أدناه.

1. نهيّئ كومة صغرى، حيث يكون العنصر الأعلى في الكومة هو الأصغر.
2. ندرج أولاً العناصر $k$ الأولى من المصفوفة في الكومة بالتتابع.
3. بدءاً من العنصر $(k + 1)^{th}$، إذا كان العنصر الحالي أكبر من العنصر الأعلى في الكومة، نحذف العنصر الأعلى من الكومة وندرج العنصر الحالي فيها.
4. بعد اكتمال الاجتياز، تحتوي الكومة على أكبر $k$ عنصر.

وتكون شيفرة المثال كما يلي:

يُجري ما مجموعه $n$ جولة من الإدراج والحذف في الكومة، ويكون الحد الأقصى لطول الكومة $k$، لذا يكون التعقيد الزمني $O(n \log k)$. وهذه الطريقة عالية الكفاءة؛ فعندما يكون $k$ صغيراً يقترب التعقيد الزمني من $O(n)$، وعندما يكون $k$ كبيراً لا يتجاوز التعقيد الزمني $O(n \log n)$.

وإضافة إلى ذلك، تلائم هذه الطريقة تدفّقات البيانات الديناميكية. فمع وصول بيانات جديدة، يمكننا مواصلة صيانة العناصر في الكومة، بما يتيح التحديث الديناميكي لأكبر $k$ عنصر.