Merge k Sorted Lists

Q: ما هو التعقيد الزمني لدمج k قوائم مرتبة؟

باستخدام كومة صغرى، يكون التعقيد O(N log k) ، حيث إن N هو العدد الإجمالي للقيم و k هو عدد القوائم. تُضاف كل قيمة إلى الكومة وتُزال منها مرة واحدة، وتحتوي الكومة على k عناصر كحد أقصى، لذا تستغرق كل عملية O(log k) . تبلغ الذاكرة الإضافية O(k) ، باستثناء ذاكرة المخرجات.

Q: لماذا لا نضع كل القيم معًا ونرتبها؟

هذا صحيح، ويستغرق زمنًا قدره O(N log N) ، وهو مناسب للمدخلات الصغيرة. لكنه يتجاهل أن القوائم مرتبة بالفعل، لذا يدفع تكلفة log N لكل قيمة، بينما يدفع الكومة تكلفة log k ، كما يتطلب وجود جميع القيم في الذاكرة في الوقت نفسه. ويمكن للكومة أيضًا دمج القوائم التي تصل على هيئة تدفقات، وهو ما لا يمكن للفرز فعله.

صعبالكومة القائمة المترابطة

+10

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

ادمجها في قائمة واحدة تضم كل القيم من جميع الصفوف، مرتبة ترتيبًا غير تنازلي، ثم أعدها. تظهر القيمة التي تتكرر عدة مرات، في صف واحد أو في عدة صفوف، بهذا العدد من المرات في النتيجة.

الدالة

mergeKLists(lists: integer-2d-array) → integer-array

listsinteger-2d-array: القوائم المرتبة، قائمة واحدة في كل صف، وقد تكون بأطوال مختلفة
تُرجعinteger-array: كل القيم من كل صف، في قائمة واحدة مرتبة

القيود

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length، وتحتوي جميع الصفوف معًا على 10⁴ قيمة كحد أقصى
-10⁴ ≤ lists[i][j] ≤ 10⁴
كل صف مرتب ترتيبًا غير تنازلي.

أمثلة

المدخلات: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
المخرجات: [1, 2, 3, 4, 5, 6, 9, 10]
الشرح: أصغر قيمة على الإطلاق هي 1، وهي القيمة الأولى في الصف الثاني. بعدها تبدأ الصفوف بالقيم 2 و4 و3، لذا يأتي 2 تاليًا، وهكذا. ينتهي الصف الثالث بعد 5، لتتبقى القيم 6 و9 و10 في النهاية.

المدخلات: lists = [[5], [-2, 5, 7], [0, 5]]
المخرجات: [-2, 0, 5, 5, 5, 7]
الشرح: تأتي قيم 5 الثلاث من ثلاثة صفوف مختلفة، وتبقى جميعها. يُرتَّب العدد السالب -2 قبل 0.

+14 اختبارات مخفية عند الإرسال

سؤال إضافي

اعثر على أصغر نطاق [a, b] يحتوي على قيمة واحدة على الأقل من كل صف. هل يمكن استخدام الكومة نفسها لرؤوس الصفوف، بالإضافة إلى أكبر رأس حتى الآن، لإيجاد هذا النطاق في O(N log k)؟

الحل

كل صف مرتب، لذا فإن أصغر قيمة لم تُستخدم بعد تكون دائمًا أول قيمة غير مستخدمة في أحد الصفوف. تتمثل المشكلة كلها في العثور على أصغر رأس من بين k صفوف، وذلك N مرة، حيث إن N هو عدد القيم. يتطلب فحص جميع الرؤوس k خطوة لكل قيمة. تحافظ كومة صغرى على ترتيب الرؤوس وتُخرج أصغرها في O(log k)، مما يخفض الإجمالي من O(N·k) إلى O(N log k). في الصيغة الكلاسيكية، تكون كل قائمة قائمة مترابطة؛ أما هنا فكل صف مصفوفة، ويؤدي فهرس لكل صف وظيفة مؤشر العقدة.

قارن جميع الرؤوس k لكل قيمة

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

احتفِظ بفهرس واحد لكل صف، pos[r]، يشير إلى أول قيمة في الصف r لم تستخدمها بعد: رأس الصف. لا بد أن تكون أصغر قيمة غير مستخدمة بين هذه الرؤوس. داخل الصف r، تقع كل قيمة غير مستخدمة عند pos[r] أو بعده، والصف مرتب، لذا لا توجد قيمة منها أصغر من الرأس.

لذا اعثر على أصغر رأس بالنظر إلى كل صف لا تزال فيه قيم، وأضِفه، ثم حرّك فهرس ذلك الصف خطوة واحدة إلى الأمام. كرّر ذلك حتى تُخرَج جميع القيم N. هذه هي خطوة الدمج في الترتيب بالدمج، بعد توسيعها من قائمتين إلى k.

في المثال الأول، تكون الرؤوس في البداية 2 و1 و3، لذا تُخرَج 1 أولًا ويصبح رأس الصف الثاني 4. ثم 2 (الرؤوس 2 و4 و3)، ثم 3 (الرؤوس 6 و4 و3)، ثم 4، ثم 5، مما يُفرغ الصف الثالث. تقارن الجولات الثلاث الأخيرة بين 6 و10 فقط، ثم 9 و10، ثم 10 وحدها.

تبلغ الكلفة k مقارنة لكل قيمة من القيم N. مع 10^4 صفوف، في كل منها قيمة واحدة، يعني ذلك 10^8 مقارنة. تنجزها C أو Java أو JavaScript في أقل من ثانية، لكن Python تحتاج إلى أكثر من عشر ثوانٍ، ومضاعفة كل من N وk تجعل كل لغة أبطأ بأربعة أضعاف. يظهر الهدر في تتبّع التنفيذ: بعد كل اختيار، يتغير رأس واحد فقط، ومع ذلك تقرأ الجولة التالية الرؤوس k كلها مجددًا.

الخوارزمية

عيّن pos[r] = 0 لكل صف، واحسب عدد القيم، N.
كرّر N مرة: افحص كل صف لا يزال pos[r] ضمنه، وتذكّر الصف الذي يكون رأسه أصغر قيمة.
أضف ذلك الرأس إلى النتيجة، وزِد pos لذلك الصف بمقدار 1.
أعِد النتيجة.

def mergeKLists(lists):
    pos = [0] * len(lists)  # pos[r]: index of the first unused value in row r
    total = sum(len(row) for row in lists)
    merged = []
    for _ in range(total):
        best = -1  # the row whose head is the smallest so far
        for r in range(len(lists)):
            if pos[r] < len(lists[r]) and (best == -1 or lists[r][pos[r]] < lists[best][pos[best]]):
                best = r
        merged.append(lists[best][pos[best]])
        pos[best] += 1
    return merged

كومة صغرى من الرؤوس k

الفكرة

تعيد عملية المسح قراءة k من الرؤوس للعثور على الأصغر، مع أن رأسا واحدا فقط قد تغيّر منذ الجولة السابقة. وتُنشأ كومة صغرى لهذا الغرض بالضبط: فهي تحتفظ بمجموعة من الأعداد، ويكون أصغرها في الأعلى، وتكلفة كل من أخذ العنصر الأعلى وإضافة عدد هي O(log size).

ضع القيمة الأولى من كل صف في الكومة، مع وسم كل قيمة برقم صفها. ثم كرر: أخرج أصغر زوج (value, row)، وألحِق value، وإذا كان في ذلك الصف قيمة أخرى، فأضفها مع الوسم نفسه. تحتوي الكومة دائما على مدخل واحد بالضبط لكل صف ما زالت فيه قيم، وهو رأسه، لذا يكون العنصر الأعلى هو أصغر قيمة غير مستخدمة إجمالا. إنها قاعدة المسح نفسها، لكن بإجابة أسرع.

تتبّع المثال الأول مع ترقيم الصفوف بدءا من 0. تبدأ الكومة بالقيم 2 (الصف 0)، و1 (الصف 1)، و3 (الصف 2). أخرج 1 وأضف القيمة التالية في الصف 1، وهي 4. أخرج 2 وأضف 6 من الصف 0. أخرج 3 وأضف 5 من الصف 2. أخرج 4 وأضف 10. أخرج 5: انتهت قيم الصف 2، لذا لا يُضاف شيء، وتتقلص الكومة لتضم 6 و10. أخرج 6 وأضف 9. أخرج 9، ثم 10. النتيجة هي [1, 2, 3, 4, 5, 6, 9, 10].

تدخل كل قيمة إلى الكومة مرة واحدة وتخرج منها مرة واحدة، ولا تحتوي الكومة أبدا على أكثر من k مدخلات، لذا تكلف كل واحدة من تلك العمليات البالغ عددها 2N زمنا مقداره O(log k). عندما يكون N = k = 10^4، يكون المجموع نحو 2 × 10^4 × 14، أي أقل من 3 × 10^5 خطوة، مقارنة بـ 10^8 للمسح. تستخدم الكومة ذاكرة مقدارها O(k)، وليس أبدا O(N)، لأنها تحتفظ برأس واحد لكل صف ولا تحتفظ بالقيم التي تليه.

تنشئ عدة تطبيقات الكومة يدويا في مصفوفة من أرقام الصفوف المرتبة وفقا لرأس كل صف، حيث يكون ابنا الخانة i في 2i+1 و2i+2 (وفي 2i و2i+1 في Lua وR، اللتين تبدآن العد من 1). ويوفر ذلك العمل أيضا: فبعد أخذ رأس الصف الموجود في الأعلى، لا تكون قيمة الصف التالية أصغر، لذا يبقى الصف في الأعلى ويهبط مرة واحدة، بدلا من إخراجه ثم إضافته من جديد.

الخوارزمية

أضِف (lists[r][0], r) لكل صف r إلى كومة صغرى مرتبة حسب القيمة.
ما دامت الكومة غير فارغة، أخرج أصغر زوج (value, r) وأضِف value إلى النتيجة.
إذا كان للصف r قيمة تالية، فأضِفها مع r.
أعِد النتيجة عندما تصبح الكومة فارغة.

import heapq


def mergeKLists(lists):
    # The heap holds one (value, row) pair per row that still has values: that row's head.
    heap = [(row[0], r) for r, row in enumerate(lists)]
    heapq.heapify(heap)
    nxt = [1] * len(lists)  # nxt[r]: index of row r's next value, not yet in the heap
    merged = []
    while heap:
        value, r = heapq.heappop(heap)  # the smallest head of all rows
        merged.append(value)
        if nxt[r] < len(lists[r]):
            heapq.heappush(heap, (lists[r][nxt[r]], r))  # row r's new head takes its place
            nxt[r] += 1
    return merged

أخطاء شائعة وحالات حدّية

منطق الكومة بسيط. تأتي معظم الأخطاء مما يُضاف إلى الكومة ومن ترتيبها.

نسيان مصدر القيمة. إذا كانت الكومة تحتوي على قيم مجردة، فلن تتمكن من معرفة الصف الذي يجب تقديمه بعد إخراج عنصر. خزّن الصف مع القيمة.
استخدام كومة عظمى عن طريق الخطأ. يضع كلٌّ من priority_queue في C++ وBinaryHeap في Rust أكبر قيمة في الأعلى؛ استخدم greater<> أو Reverse. أما PriorityQueue في Java وheapq في Python، فيضعان أصغر قيمة في الأعلى تلقائيًا.
التعادلات في heapq في Python. عندما تتساوى قيمتان، تنتقل مقارنة الصفوف إلى العنصر الثاني. يمكن مقارنة رقم الصف دون مشكلة، لكن لا يمكن مقارنة عقدة قائمة مترابطة، والنسخة التقليدية تتعطل عند تساوي القيم. ضع رقم صف أو عدّادًا في الموضع الثاني.
إضافة كل القيم في البداية. سيظل الترتيب صحيحًا، لكن الكومة ستكبر لتضم N عنصرًا، وستصبح العملية O(N log N). احتفظ بعنصر الرأس لكل صف.
القراءة بعد نهاية صف قصير. تختلف أطوال الصفوف، لذا تحقق من وجود قيمة تالية في الصف قبل إضافتها.
إسقاط القيم المكررة. القيم المتساوية القادمة من صفوف مختلفة هي قيم منفصلة، ويجب أن تُضم كلها إلى الناتج.

أسئلة شائعة4

ما هو التعقيد الزمني لدمج k قوائم مرتبة؟

باستخدام كومة صغرى، يكون التعقيد O(N log k)، حيث إن N هو العدد الإجمالي للقيم وk هو عدد القوائم. تُضاف كل قيمة إلى الكومة وتُزال منها مرة واحدة، وتحتوي الكومة على k عناصر كحد أقصى، لذا تستغرق كل عملية O(log k). تبلغ الذاكرة الإضافية O(k)، باستثناء ذاكرة المخرجات.

لماذا لا نضع كل القيم معًا ونرتبها؟

هذا صحيح، ويستغرق زمنًا قدره O(N log N)، وهو مناسب للمدخلات الصغيرة. لكنه يتجاهل أن القوائم مرتبة بالفعل، لذا يدفع تكلفة log N لكل قيمة، بينما يدفع الكومة تكلفة log k، كما يتطلب وجود جميع القيم في الذاكرة في الوقت نفسه. ويمكن للكومة أيضًا دمج القوائم التي تصل على هيئة تدفقات، وهو ما لا يمكن للفرز فعله.

هل يمكنك دمج قوائم مرتبة عددها k دون استخدام كومة؟

نعم، باستخدام أسلوب «قسّم تسُد». ادمج القوائم اثنتين اثنتين باستخدام دمج قائمتين، ثم ادمج النتائج اثنتين اثنتين، وهكذا. هناك log k جولات، وفي كل جولة تُعالَج كل قيمة مرة واحدة، لذا يكون التعقيد أيضًا O(N log k). أما دمج القوائم واحدة تلو الأخرى في نتيجة آخذة في النمو فهو أبطأ: إذ تُنسخ القيم المبكرة مجددًا في كل عملية دمج، ما يؤدي إلى تعقيد إجمالي قدره O(N·k).

لماذا لا يحتاج الكومة إلا إلى رأس كل قائمة؟

كل قائمة مرتبة، لذا فإن أول قيمة غير مستخدمة فيها هي أصغر قيمة متبقية. ولذلك، فإن أصغر قيمة بين جميع القوائم هي الأصغر بين رؤوسها، ولا يمكن لأي قيمة أعمق في قائمة أن تتفوق عليها. عندما يُزال أحد الرؤوس، تصبح القيمة التالية في القائمة نفسها رأس تلك القائمة وتحل محله في الكومة.

Python

def mergeKLists(lists):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

lists = [[2, 6, 9], [1, 4, 10], [3, 5]]

المتوقع

[1, 2, 3, 4, 5, 6, 9, 10]