Merge k Sorted Lists

Q: Wie hoch ist die Zeitkomplexität von Merge k Sorted Lists?

Mit einem Min-Heap beträgt der Aufwand O(N log k) , wobei N die Gesamtzahl der Werte und k die Anzahl der Listen ist. Jeder Wert wird einmal eingefügt und entfernt, und der Heap enthält höchstens k Einträge. Der zusätzliche Speicherbedarf beträgt neben der Ausgabe O(k) .

Q: Warum nicht alle Werte zusammenfügen und sortieren?

Das ist korrekt und benötigt O(N log N) Zeit. Dabei wird ignoriert, dass die Listen bereits sortiert sind: Pro Wert fallen log N statt log k wie beim Heap an, und alle Werte müssen gleichzeitig im Speicher liegen. Mit dem Heap lassen sich außerdem Listen zusammenführen, die als Streams eintreffen.

SchwerHeap Verkettete Liste

+10

Du erhältst k Listen mit ganzen Zahlen als Zeilen von lists. Jede Zeile ist in nicht absteigender Reihenfolge sortiert, die Zeilen können unterschiedlich lang sein, und keine Zeile ist leer.

Führe sie zu einer Liste zusammen, die jeden Wert aus jeder Zeile enthält, in nicht absteigender Reihenfolge sortiert ist, und gib sie zurück. Ein Wert, der mehrmals vorkommt, in einer Zeile oder in mehreren, erscheint entsprechend oft im Ergebnis.

Funktion

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

listsinteger-2d-array: die sortierten Listen, eine pro Zeile, möglicherweise mit unterschiedlicher Länge
Gibt zurückinteger-array: alle Werte aus jeder Zeile in einer sortierten Liste

Einschränkungen

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length, und alle Zeilen zusammen enthalten höchstens 10⁴ Werte
-10⁴ ≤ lists[i][j] ≤ 10⁴
Jede Zeile ist in nicht absteigender Reihenfolge sortiert.

Beispiele

Eingabe: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Ausgabe: [1, 2, 3, 4, 5, 6, 9, 10]
Erklärung: Die Zeilen beginnen mit 2, 1 und 3, also kommt 1 zuerst. Die Köpfe sind dann 2, 4 und 3, also folgt 2 und so weiter. Die dritte Zeile endet nach 5, sodass 6, 9 und 10 übrig bleiben.

Eingabe: lists = [[5], [-2, 5, 7], [0, 5]]
Ausgabe: [-2, 0, 5, 5, 5, 7]
Erklärung: Die drei 5er stammen aus drei verschiedenen Zeilen und alle drei bleiben erhalten. Der negative Wert -2 wird vor 0 sortiert.

Weiterführende Frage

Finde den kleinsten Bereich [a, b], der einen Wert aus jeder Zeile enthält. Kann ein Heap der Zeilenköpfe plus des größten Kopfes das in O(N log k) leisten?

Lösung

Jede Zeile ist sortiert, daher ist der kleinste noch nicht verwendete Wert immer der erste noch nicht verwendete Wert einer Zeile, also ihr Kopf. Das Durchsuchen aller k Köpfe kostet für jeden der N Werte k Schritte. Ein Min-Heap der Köpfe liefert den kleinsten Wert in O(log k), wodurch sich der Gesamtaufwand von O(N·k) auf O(N log k) verringert.

Vergleiche für jeden Wert alle k Köpfe

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Halte am Anfang jeder Zeile einen Index pos[r] bereit. In jeder Runde liest du alle Zeilenköpfe, fügst den kleinsten Wert hinzu und rückst den Index dieser Zeile weiter: der Zusammenführungsschritt von Merge-Sort, erweitert von zwei Listen auf k. Im ersten Beispiel beginnen die Zeilenköpfe mit 2, 1 und 3, also wird 1 ausgegeben und der Kopf der zweiten Zeile wird zu 4.

Jeder der N Werte erfordert einen Durchlauf über alle k Zeilen. Bei 10^4 Zeilen mit je einem Wert ergibt das 10^8 Zeilenprüfungen.

Algorithmus

Setze pos[r] = 0 für jede Zeile und zähle die Werte, N.
Wiederhole dies N Mal: Betrachte jede Zeile, bei der pos[r] noch innerhalb der Zeile liegt, und merke dir die Zeile, deren erstes Element am kleinsten ist.
Füge dieses erste Element zum Ergebnis hinzu und erhöhe pos dieser Zeile um 1.
Gib das Ergebnis zurück.

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

Min-Heap der k Köpfe

Idee

Nach jeder Entnahme ändert sich nur ein Kopf, dennoch liest der Scan alle k erneut. Ein Min-Heap hält den kleinsten Wert ganz oben. Kennzeichne jeden Kopf mit seiner Zeile, damit du nach dem Entnehmen von (value, row) weißt, welchen nächsten Wert dieser Zeile du einfügen musst. Der Heap enthält immer einen Eintrag pro Zeile, in der noch Werte übrig sind, sodass sein oberster Wert der kleinste noch nicht verwendete Wert ist.

Im ersten Beispiel startet der Heap mit 2, 1 und 3. Entnimm 1, füge 4 ein. Entnimm 2, füge 6 ein. Entnimm 3, füge 5 ein. Entnimm 4, füge 10 ein. Entnimm 5: Die dritte Zeile ist aufgebraucht, daher wird nichts eingefügt. Entnimm 6, füge 9 ein, dann entnimm 9 und 10.

Jeder Wert wird einmal eingefügt und einmal entnommen, und der Heap enthält nie mehr als k Einträge: 2N Operationen mit O(log k). Bei N = k = 10^4 sind das weniger als 3 × 10^5 Schritte. Der Heap benötigt O(k) Speicher.

Algorithmus

Füge für jede Zeile r (lists[r][0], r) in einen Min-Heap ein, der nach Werten geordnet ist.
Solange der Heap nicht leer ist, entferne das kleinste Paar (value, r) und füge value an das Ergebnis an.
Wenn Zeile r einen nächsten Wert hat, füge ihn zusammen mit r ein.
Gib das Ergebnis zurück, sobald der Heap leer ist.

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

Stolperfallen und Grenzfälle

Nur Werte einfügen. Nach einer Entnahme kannst du nicht erkennen, welche Zeile weitergeführt werden soll. Speichere die Zeile zusammen mit dem Wert.
Aus Versehen einen Max-Heap verwenden. C++ priority_queue und Rust BinaryHeap legen das größte Element nach oben; verwende greater<> oder Reverse.
Alle Werte gleich zu Beginn einfügen. Das Ergebnis ist zwar weiterhin sortiert, aber der Heap wächst auf N Einträge an und der Aufwand beträgt O(N log N).
Über das Ende einer kurzen Zeile hinaus lesen. Im ersten Beispiel enthält die dritte Zeile zwei Werte. Prüfe also vor dem Einfügen, ob ein nächster Wert vorhanden ist.
Duplikate weglassen. Die drei 5er im zweiten Beispiel sind separate Werte und gehören alle ins Ergebnis.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Merge k Sorted Lists?

Mit einem Min-Heap beträgt der Aufwand O(N log k), wobei N die Gesamtzahl der Werte und k die Anzahl der Listen ist. Jeder Wert wird einmal eingefügt und entfernt, und der Heap enthält höchstens k Einträge. Der zusätzliche Speicherbedarf beträgt neben der Ausgabe O(k).

Warum nicht alle Werte zusammenfügen und sortieren?

Das ist korrekt und benötigt O(N log N) Zeit. Dabei wird ignoriert, dass die Listen bereits sortiert sind: Pro Wert fallen log N statt log k wie beim Heap an, und alle Werte müssen gleichzeitig im Speicher liegen. Mit dem Heap lassen sich außerdem Listen zusammenführen, die als Streams eintreffen.

Kannst du k sortierte Listen ohne einen Heap zusammenführen?

Ja, mit Teile und herrsche. Führe die Listen paarweise mit dem Merge zweier Listen zusammen, dann die Ergebnisse paarweise usw.: log k Runden, in denen jeder Wert einmal verarbeitet wird, also O(N log k). Die Listen nacheinander in ein wachsendes Ergebnis einzufügen, ist langsamer, O(N·k), da frühe Werte bei jedem Merge erneut kopiert werden.

def mergeKLists(lists):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe

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