Merge k Sorted Lists

Q: Qual è la complessità temporale di Merge k Sorted Lists?

Con un min-heap è O(N log k) , dove N è il numero totale di valori e k il numero di liste. Ogni valore viene inserito ed estratto una volta, e l’heap contiene al massimo k elementi. La memoria aggiuntiva è O(k) , oltre all’output.

Q: Perché non mettere insieme tutti i valori e ordinarli?

È corretto e richiede un tempo O(N log N) . Ignora il fatto che le liste sono già ordinate, quindi paga log N per ogni valore, mentre l'heap paga log k , e ha bisogno di avere tutti i valori in memoria contemporaneamente. L'heap può anche unire liste che arrivano come flussi.

DifficileHeap Lista concatenata

+10

Ricevi k elenchi di interi come righe di lists. Ogni riga è ordinata in ordine non decrescente, le righe possono avere lunghezze diverse e nessuna riga è vuota.

Uniscile in un unico elenco che contenga tutti i valori di tutte le righe, ordinati in ordine non decrescente, e restituiscilo. Un valore che appare più volte, in una riga o in più righe, apparirà altrettante volte nel risultato.

Funzione

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

listsinteger-2d-array: gli elenchi ordinati, uno per riga, di lunghezze eventualmente diverse
Restituisceinteger-array: tutti i valori di ogni riga, in un unico elenco ordinato

Vincoli

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length e tutte le righe insieme contengono al massimo 10⁴ valori
-10⁴ ≤ lists[i][j] ≤ 10⁴
Ogni riga è ordinata in ordine non decrescente.

Esempi

Input: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Output: [1, 2, 3, 4, 5, 6, 9, 10]
Spiegazione: Le righe iniziano con 2, 1 e 3, quindi 1 viene per primo. Le teste sono poi 2, 4 e 3, quindi segue 2, e così via. La terza riga termina dopo 5, lasciando 6, 9 e 10.

Input: lists = [[5], [-2, 5, 7], [0, 5]]
Output: [-2, 0, 5, 5, 5, 7]
Spiegazione: I tre 5 provengono da tre righe diverse e tutti e tre rimangono. Il numero negativo -2 viene prima di 0 nell’ordinamento.

Per approfondire

Trova l'intervallo più piccolo [a, b] che contiene un valore di ogni riga. Un heap delle teste delle righe più la testa più grande può farlo in O(N log k)?

Soluzione

Ogni riga è ordinata, quindi il valore inutilizzato più piccolo è sempre il primo valore inutilizzato di una riga, la sua testa. Esaminare tutte le k teste richiede k passaggi per ciascuno degli N valori. Un min-heap delle teste fornisce il valore più piccolo in O(log k), riducendo il totale da O(N·k) a O(N log k).

Confronta tutte le teste k per ogni valore

Corretto, ma non termina sui test più grandi

Intuizione

Usa un indice pos[r] all’inizio di ogni riga. A ogni round leggi tutte le teste, aggiungi il valore più piccolo e fai avanzare l’indice di quella riga: è la fase di fusione del merge sort, estesa da due liste a k. Nel primo esempio le teste iniziano con 2, 1 e 3, quindi esce 1 e la testa della seconda riga diventa 4.

Ognuno degli N valori richiede un passaggio su tutte le k righe. Con 10^4 righe contenenti un valore ciascuna, si arriva a 10^8 controlli delle righe.

Algoritmo

Imposta pos[r] = 0 per ogni riga e conta i valori: N.
Ripeti N volte: esamina ogni riga in cui pos[r] è ancora al suo interno e ricorda la riga con l’elemento iniziale più piccolo.
Aggiungi quell’elemento iniziale al risultato e incrementa di 1 il pos di quella riga.
Restituisci il risultato.

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 delle k teste

Intuizione

Dopo ogni estrazione cambia solo una testa, eppure la scansione rilegge tutti gli k. Un min-heap mantiene in cima le teste con i valori più piccoli. Associa a ogni testa la sua riga, così dopo aver estratto (value, row) sai da quale riga inserire il valore successivo. L'heap contiene sempre una voce per ogni riga con valori rimanenti, quindi il suo elemento in cima è il valore inutilizzato più piccolo.

Nel primo esempio l'heap inizia con 2, 1 e 3. Estrai 1, inserisci 4. Estrai 2, inserisci 6. Estrai 3, inserisci 5. Estrai 4, inserisci 10. Estrai 5: la terza riga è esaurita, quindi non viene inserito nulla. Estrai 6, inserisci 9, poi estrai 9 e 10.

Ogni valore entra ed esce una volta e l'heap non contiene mai più di k voci: 2N operazioni di O(log k). Con N = k = 10^4 sono meno di 3 × 10^5 passaggi. L'heap richiede memoria O(k).

Algoritmo

Inserisci (lists[r][0], r) per ogni riga r in un min-heap ordinato per valore.
Finché l'heap non è vuoto, estrai la coppia più piccola (value, r) e aggiungi value al risultato.
Se la riga r ha un valore successivo, inseriscilo insieme a r.
Restituisci il risultato quando l'heap è vuoto.

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

Trappole e casi limite

Inserire solo i valori. Dopo un'estrazione non puoi sapere quale riga avanzare. Memorizza la riga insieme al valore.
Usare per errore un max-heap. C++ priority_queue e Rust BinaryHeap mettono in cima l'elemento più grande; usa greater<> o Reverse.
Inserire tutti i valori all'inizio. Il risultato è comunque ordinato, ma l'heap cresce fino a N elementi e il lavoro diventa O(N log N).
Leggere oltre la fine di una riga corta. Nel primo esempio la terza riga contiene due valori, quindi controlla che ci sia un valore successivo prima di inserirlo.
Eliminare i duplicati. I tre 5 nel secondo esempio sono valori distinti e devono comparire tutti nel risultato.

Domande frequenti3

Qual è la complessità temporale di Merge k Sorted Lists?

Con un min-heap è O(N log k), dove N è il numero totale di valori e k il numero di liste. Ogni valore viene inserito ed estratto una volta, e l’heap contiene al massimo k elementi. La memoria aggiuntiva è O(k), oltre all’output.

Perché non mettere insieme tutti i valori e ordinarli?

È corretto e richiede un tempo O(N log N). Ignora il fatto che le liste sono già ordinate, quindi paga log N per ogni valore, mentre l'heap paga log k, e ha bisogno di avere tutti i valori in memoria contemporaneamente. L'heap può anche unire liste che arrivano come flussi.

Riesci a unire k liste ordinate senza un heap?

Sì, con la tecnica del divide et impera. Unisci le liste a coppie con l’unione di due liste, poi unisci i risultati a coppie, e così via: log k passaggi che toccano ogni valore una volta, quindi O(N log k). Unire le liste una dopo l’altra in un risultato che cresce è più lento, O(N·k), perché i valori iniziali vengono copiati di nuovo a ogni unione.

def mergeKLists(lists):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

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