Merge k Sorted Lists

Q: מהי סיבוכיות הזמן של מיזוג k רשימות ממוינות?

בעזרת ערימת מינימום, סיבוכיות הזמן היא O(N log k) , כאשר N הוא המספר הכולל של הערכים ו- k הוא מספר הרשימות. כל ערך נדחף ונשלף פעם אחת, והערימה מכילה לכל היותר 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]
הסבר: השורות מתחילות ב־2, 1 ו־3, לכן 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.

שאלת המשך

מצא את הטווח הקטן ביותר [a, b] שמכיל ערך מכל שורה. האם ערמת ראשי השורות יחד עם הראש הגדול ביותר יכולה לעשות זאת ב-O(N log k)?

פתרון

כל שורה ממוינת, לכן הערך הלא־משומש הקטן ביותר הוא תמיד הערך הלא־משומש הראשון של אחת השורות — הראש שלה. סריקת כל k הראשים עולה k צעדים לכל אחד מ־N הערכים. ערימת מינימום של הראשים מספקת את הקטן ביותר ב־O(log k), וכך העלות הכוללת יורדת מ־O(N·k) ל־O(N log k).

השווה את כל k הראשים עבור כל ערך

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

שמור אינדקס pos[r] בתחילת כל שורה. בכל סבב קוראים את כל הראשים, מוסיפים את הקטן ביותר ומקדמים את האינדקס של אותה שורה: שלב המיזוג של מיון מיזוג, המורחב משתי רשימות ל־k רשימות. בדוגמה הראשונה הראשים מתחילים בערכים 2, 1 ו־3, ולכן 1 יוצא והראש של השורה השנייה הופך ל־4.

כל אחד מ־N הערכים דורש מעבר על כל k השורות. עם 10^4 שורות שבכל אחת מהן ערך אחד, מדובר ב־10^8 בדיקות של שורות.

אלגוריתם

הגדר pos[r] = 0 עבור כל שורה וספור את הערכים, N.
חזור על הפעולה N פעמים: בדוק כל שורה שבה pos[r] עדיין נמצא בתוכה וזכור את השורה שהראש שלה הוא הקטן ביותר.
הוסף את הראש הזה לתוצאה והוסף 1 ל-pos של אותה שורה.
החזר את התוצאה.

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. ערימת מינימום שומרת את הראשים כך שהקטן ביותר נמצא למעלה. תייגו כל ראש עם השורה שלו, כדי שאחרי שליפת (value, row) תדעו מאיזו שורה לדחוף את הערך הבא. הערימה תמיד מכילה כניסה אחת לכל שורה שנותרו בה ערכים, ולכן הערך שבראשה הוא הערך הקטן ביותר שטרם נעשה בו שימוש.

בדוגמה הראשונה הערימה מתחילה עם 2, 1 ו-3. שולפים את 1 ודוחפים את 4. שולפים את 2 ודוחפים את 6. שולפים את 3 ודוחפים את 5. שולפים את 4 ודוחפים את 10. שולפים את 5: השורה השלישית מוצתה, ולכן לא מכניסים דבר. שולפים את 6 ודוחפים את 9, ואז שולפים את 9 ואת 10.

כל ערך נכנס ויוצא פעם אחת, והערימה לעולם אינה מכילה יותר מ-k כניסות: 2N פעולות של O(log k). כאשר N = k = 10^4, מדובר בפחות מ-3 × 10^5 צעדים. הערימה צורכת זיכרון של O(k).

אלגוריתם

דחפו את (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

מלכודות ומקרי קצה

דחיפה של ערכים בלבד. אחרי שליפה אי אפשר לדעת איזו שורה לקדם. יש לשמור את השורה יחד עם הערך.
שימוש בטעות בערימת מקסימום. ‏C++ priority_queue ו-Rust BinaryHeap שמות את הערך הגדול ביותר בראש; יש להשתמש ב-greater<> או ב-Reverse.
דחיפה של כל הערכים בהתחלה. התוצאה עדיין ממוינת, אבל הערימה גדלה ל-N איברים והעבודה הופכת ל-O(N log N).
קריאה מעבר לסוף של שורה קצרה. בדוגמה הראשונה יש בשורה השלישית שני ערכים, לכן יש לבדוק אם יש ערך נוסף לפני שדוחפים.
השמטת כפילויות. שלושת ערכי ה-5 בדוגמה השנייה הם ערכים נפרדים, וכולם צריכים להיכלל בתוצאה.

שאלות נפוצות3

מהי סיבוכיות הזמן של מיזוג k רשימות ממוינות?

בעזרת ערימת מינימום, סיבוכיות הזמן היא O(N log k), כאשר N הוא המספר הכולל של הערכים ו-k הוא מספר הרשימות. כל ערך נדחף ונשלף פעם אחת, והערימה מכילה לכל היותר k איברים. הזיכרון הנוסף הוא O(k), מלבד הפלט.

למה לא לשים את כל הערכים יחד ולמיין אותם?

זה נכון ולוקח זמן O(N log N). הפתרון מתעלם מכך שהרשימות כבר ממוינות, ולכן הוא משלם log N עבור כל ערך, בעוד שהתור משלם log k, והוא צריך את כל הערכים בזיכרון בו־זמנית. התור יכול גם למזג רשימות שמגיעות כזרמים.

האם אפשר למזג k רשימות ממוינות בלי ערימת מינימום?

כן, באמצעות הפרד ומשול. ממזגים את הרשימות בזוגות בעזרת מיזוג של שתי רשימות, ואז ממזגים את התוצאות בזוגות, וכן הלאה: log k סבבים שבכל אחד מהם נוגעים בכל ערך פעם אחת, ולכן O(N log k). מיזוג הרשימות בזו אחר זו לתוצאה הולכת וגדלה הוא איטי יותר, O(N·k), משום שערכים מוקדמים מועתקים שוב בכל מיזוג.

def mergeKLists(lists):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

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

הפלט הצפוי

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