Merge k Sorted Lists

Q: Wie hoch ist die Zeitkomplexität beim Zusammenführen von k sortierten Listen?

Mit einem Min-Heap beträgt die Laufzeit 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, daher kostet jede Operation O(log k) . Der zusätzliche Speicherbedarf beträgt O(k) , zusätzlich zur Ausgabe.

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

Das ist richtig und benötigt O(N log N) Zeit, was für kleine Eingaben in Ordnung ist. Dabei wird ignoriert, dass die Listen bereits sortiert sind: Für jeden Wert fällt daher ein Aufwand von log N an, während der Heap nur log k benötigt, und alle Werte müssen gleichzeitig im Speicher sein. Mit dem Heap lassen sich außerdem Listen zusammenführen, die als Datenströme ankommen – mit dem Sortieren ist das nicht möglich.

SchwerHeap Verkettete Liste

+10

Du erhältst k Listen von Ganzzahlen 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 oder mehreren Zeilen, kommt entsprechend oft im Ergebnis vor.

Funktion

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

listsinteger-2d-array: die sortierten Listen, eine pro Zeile, die möglicherweise unterschiedlich lang sind
Gibt zurückinteger-array: alle Werte aus allen Zeilen 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: Der kleinste Wert insgesamt ist 1, der erste Wert der zweiten Zeile. Danach beginnen die Zeilen mit 2, 4 und 3, also kommt als Nächstes 2 und so weiter. Die dritte Zeile endet nach 5, sodass am Schluss 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. Die negative Zahl -2 wird vor 0 sortiert.

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Finde den kleinsten Bereich [a, b], der mindestens einen Wert aus jeder Zeile enthält. Kann derselbe Heap der Zeilenköpfe zusammen mit dem bisher größten Kopf ihn in O(N log k) finden?

Lösung

Jede Zeile ist sortiert, daher ist der kleinste noch nicht verwendete Wert immer der erste ungenutzte Wert einer Zeile. Die ganze Aufgabe besteht darin, N Mal den kleinsten von k Zeilenanfängen zu finden, wobei N die Anzahl der Werte ist. Das Durchsuchen aller Zeilenanfänge kostet pro Wert k Schritte. Ein Min-Heap hält die Zeilenanfänge sortiert und liefert das kleinste Element in O(log k), wodurch sich der Gesamtaufwand von O(N·k) auf O(N log k) reduziert. In der klassischen Form ist jede Liste eine verkettete Liste; hier ist jede Zeile ein Array, und ein Index pro Zeile übernimmt die Aufgabe des Zeigerknotens.

Vergleiche für jeden Wert alle k Köpfe

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

Idee

Behalte einen Index pro Zeile, pos[r], der auf den ersten Wert der Zeile r zeigt, den du noch nicht verwendet hast: den Kopf der Zeile. Der kleinste noch nicht verwendete Wert muss einer dieser Köpfe sein. Innerhalb der Zeile r befindet sich jeder noch nicht verwendete Wert an oder hinter pos[r], und die Zeile ist sortiert, also ist keiner davon kleiner als der Kopf.

Suche also den kleinsten Kopf, indem du jede Zeile betrachtest, die noch Werte enthält, füge ihn hinzu und rücke den Index dieser Zeile um eine Position weiter. Wiederhole das, bis alle N Werte ausgegeben sind. Das ist der Zusammenführungsschritt von Merge Sort, erweitert von zwei Listen auf k.

Im ersten Beispiel lauten die Köpfe anfangs 2, 1 und 3, also wird zuerst 1 ausgegeben und der Kopf der zweiten Zeile wird zu 4. Dann 2 (Köpfe 2, 4, 3), dann 3 (Köpfe 6, 4, 3), dann 4 und dann 5, wodurch die dritte Zeile geleert wird. In den letzten drei Runden werden nur noch 6 und 10, dann 9 und 10, dann nur noch 10 verglichen.

Die Kosten betragen k Vergleiche für jeden der N Werte. Bei 10^4 Zeilen mit jeweils einem Wert sind das 10^8 Vergleiche. C, Java oder JavaScript schaffen das in weniger als einer Sekunde, Python braucht jedoch mehr als zehn Sekunden, und wenn man sowohl N als auch k verdoppelt, wird jede Sprache viermal langsamer. Die Verschwendung wird im Ablauf sichtbar: Nach jeder Auswahl hat sich nur ein Kopf geändert, dennoch liest die nächste Runde wieder alle k Köpfe.

Algorithmus

Setze pos[r] = 0 für jede Zeile und zähle die Werte, N.
Wiederhole N Mal: Sieh dir jede Zeile an, in 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

Der Scan liest k Köpfe erneut ein, um den kleinsten zu finden, obwohl sich seit der letzten Runde nur ein Kopf geändert hat. Dafür eignet sich ein Min-Heap genau: Er enthält eine Menge von Zahlen, wobei die kleinste oben liegt, und sowohl das Entnehmen des obersten Elements als auch das Hinzufügen einer Zahl kostet O(log size).

Lege den ersten Wert jeder Zeile in den Heap und versehe jeden mit seiner Zeilennummer. Wiederhole dann: Entnimm das kleinste Paar (value, row), füge value an und füge, falls diese Zeile einen weiteren Wert hat, diesen mit derselben Kennzeichnung hinzu. Der Heap enthält immer genau einen Eintrag für jede Zeile, in der noch Werte stehen: ihren Kopf. Daher ist das oberste Element der kleinste noch nicht verwendete Wert insgesamt. Das ist die Regel des Scans, nur schneller umgesetzt.

Verfolge das erste Beispiel mit Zeilen, die ab 0 nummeriert sind. Der Heap beginnt mit 2 (Zeile 0), 1 (Zeile 1) und 3 (Zeile 2). Entnimm 1 und füge den nächsten Wert aus Zeile 1 hinzu: 4. Entnimm 2 und füge 6 aus Zeile 0 hinzu. Entnimm 3 und füge 5 aus Zeile 2 hinzu. Entnimm 4 und füge 10 hinzu. Entnimm 5: Zeile 2 ist aufgebraucht, also wird nichts hinzugefügt und der Heap schrumpft auf 6 und 10. Entnimm 6 und füge 9 hinzu. Entnimm 9 und dann 10. Das Ergebnis ist [1, 2, 3, 4, 5, 6, 9, 10].

Jeder Wert kommt einmal in den Heap und verlässt ihn einmal wieder, und der Heap enthält nie mehr als k Einträge. Daher kostet jede dieser 2N Operationen O(log k). Bei N = k = 10^4 sind das etwa 2 × 10^4 × 14, also weniger als 3 × 10^5 Schritte, gegenüber 10^8 beim Scan. Der Heap benötigt O(k) Speicher, niemals O(N), weil er einen Kopf pro Zeile speichert und nicht die dahinterliegenden Werte.

In mehreren Versionen wird der Heap von Hand aufgebaut: in einem Array aus Zeilennummern, geordnet nach dem Kopf der jeweiligen Zeile. Die Kinder von Platz i befinden sich an den Positionen 2i+1 und 2i+2 (in Lua und R, wo ab 1 gezählt wird, an den Positionen 2i und 2i+1). Das spart ebenfalls Arbeit: Nachdem der Kopf der obersten Zeile entnommen wurde, ist der nächste Wert der Zeile nicht kleiner. Deshalb bleibt die Zeile oben und wird einmal nach unten verschoben, statt erst ein Element zu entnehmen und anschließend eines hinzuzufügen.

Algorithmus

Füge für jede Zeile r das Paar (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 zum Ergebnis hinzu.
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

Die Heap-Logik ist kurz. Die meisten Fehler entstehen dadurch, was in den Heap gelangt und wie er geordnet ist.

Vergessen, woher ein Wert stammt. Wenn der Heap nur einzelne Werte enthält, kannst du nach einem Entnehmen nicht erkennen, welche Zeile weitergeführt werden muss. Speichere die Zeile zusammen mit dem Wert.
Aus Versehen einen Max-Heap verwenden. C++ priority_queue und Rust BinaryHeap platzieren das größte Element oben; verwende greater<> oder Reverse. Java PriorityQueue und Python heapq liefern bereits das kleinste Element.
Gleichstände in Python heapq. Wenn zwei Werte gleich sind, geht der Tupelvergleich zum zweiten Element über. Eine Zeilennummer lässt sich problemlos vergleichen, ein verketteter Listenknoten hingegen nicht, und die klassische Version stürzt bei gleichen Werten ab. Setze eine Zeilennummer oder einen Zähler an die zweite Stelle.
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 wird zu O(N log N). Behalte einen Kopf pro Zeile.
Über das Ende einer kurzen Zeile hinaus lesen. Zeilen haben unterschiedliche Längen. Prüfe daher, ob eine Zeile einen nächsten Wert hat, bevor du ihn einfügst.
Duplikate verwerfen. Gleiche Werte aus verschiedenen Zeilen sind separate Werte, und alle gehören ins Ergebnis.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität beim Zusammenführen von k sortierten Listen?

Mit einem Min-Heap beträgt die Laufzeit 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, daher kostet jede Operation O(log k). Der zusätzliche Speicherbedarf beträgt O(k), zusätzlich zur Ausgabe.

Warum nicht alle Werte zusammenfügen und sortieren?

Das ist richtig und benötigt O(N log N) Zeit, was für kleine Eingaben in Ordnung ist. Dabei wird ignoriert, dass die Listen bereits sortiert sind: Für jeden Wert fällt daher ein Aufwand von log N an, während der Heap nur log k benötigt, und alle Werte müssen gleichzeitig im Speicher sein. Mit dem Heap lassen sich außerdem Listen zusammenführen, die als Datenströme ankommen – mit dem Sortieren ist das nicht möglich.

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

Ja, durch Teile und Herrsche. Führe die Listen paarweise mit dem Zusammenführen zweier Listen zusammen, dann die Ergebnisse paarweise usw. Es gibt log k Runden, und in jeder Runde wird jeder Wert einmal berücksichtigt, daher beträgt die Laufzeit ebenfalls O(N log k). Die Listen nacheinander in ein wachsendes Ergebnis einzufügen, ist langsamer: Die frühen Werte werden bei jedem Zusammenführen erneut kopiert, was sich zu O(N·k) summiert.

Warum benötigt der Heap nur den Kopf jeder Liste?

Jede Liste ist sortiert, daher ist ihr erster ungenutzter Wert der kleinste noch verbleibende Wert. Der kleinste Wert unter allen Listen ist folglich der kleinste ihrer ersten Werte, und kein weiter hinten in einer Liste stehender Wert kann kleiner sein. Wenn ein erster Wert entfernt wird, wird der nächste Wert derselben Liste zum ersten Wert dieser Liste und nimmt seinen Platz im Heap ein.

Python

def mergeKLists(lists):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

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