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

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

לוגיקת הערימה קצרה. רוב הבאגים נובעים ממה שמכניסים לערימה ומהסדר שלה.

שוכחים מאיפה הגיע ערך. אם הערימה מכילה ערכים בלבד, אי אפשר לדעת איזו שורה לקדם אחרי שליפה. שומרים את השורה יחד עם הערך.
משתמשים בטעות בערימת מקסימום. C++ priority_queue ו-Rust BinaryHeap מציבות את הערך הגדול ביותר בראש; משתמשים ב-greater<> או ב-Reverse. ב-Java, PriorityQueue וב-Python, heapq כבר מספקות את הערך הקטן ביותר.
תיקו ב-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]