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 e rimosso una volta, e l'heap contiene al massimo k elementi, quindi ogni operazione costa O(log k) . La memoria aggiuntiva è O(k) , oltre all'output.

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

È corretto e richiede un tempo O(N log N) , il che va bene per input piccoli. 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, cosa che l'ordinamento non può fare.

DifficileHeap Lista concatenata

+10

Ricevi k liste di numeri 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'unica lista che contenga tutti i valori di tutte le righe, ordinati in ordine non decrescente, e restituiscila. Un valore che compare più volte, in una riga o in più righe, compare 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: Il valore più piccolo in assoluto è 1, il primo valore della seconda riga. Dopo di esso, le righe iniziano con 2, 4 e 3, quindi il successivo è 2, e così via. La terza riga termina dopo 5, lasciando 6, 9 e 10 alla fine.

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 valore negativo -2 viene prima di 0 nell’ordinamento.

+14 test nascosti all’invio

Per approfondire

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

Soluzione

Ogni riga è ordinata, quindi il valore più piccolo che nessuno ha ancora usato è sempre il primo valore inutilizzato di una riga. L’intero problema consiste nel trovare il più piccolo tra le k teste delle righe, per N volte, dove N è il numero di valori. Esaminare tutte le teste richiede k passaggi per ogni valore. Un min-heap mantiene le teste ordinate e restituisce il valore più piccolo in O(log k), riducendo il costo totale da O(N·k) a O(N log k). Nella forma classica, ogni lista è una lista concatenata; qui ogni riga è un array e un indice per riga svolge il ruolo del puntatore al nodo.

Confronta tutte le teste k per ogni valore

Corretto, ma non termina sui test più grandi

Intuizione

Mantieni un indice per ogni riga, pos[r], che punta al primo valore della riga r che non hai ancora usato: la testa della riga. Il più piccolo tra tutti i valori non ancora usati deve essere una di queste teste. All'interno della riga r, ogni valore non ancora usato si trova in corrispondenza o dopo pos[r] e la riga è ordinata, quindi nessuno di essi è più piccolo della testa.

Trova quindi la testa più piccola esaminando ogni riga che contiene ancora valori, aggiungila e avanza di una posizione l'indice di quella riga. Ripeti finché non sono stati estratti tutti gli N valori. Questo è il passaggio di fusione del merge sort, esteso da due liste a k.

Nel primo esempio, le teste iniziano con 2, 1 e 3, quindi viene estratto prima 1 e la testa della seconda riga diventa 4. Poi tocca a 2 (teste: 2, 4, 3), poi a 3 (teste: 6, 4, 3), poi a 4, poi a 5, che svuota la terza riga. Negli ultimi tre passaggi si confrontano solo 6 e 10, poi 9 e 10, poi soltanto 10.

Il costo è di k confronti per ciascuno degli N valori. Con 10^4 righe composte da un solo valore ciascuna, si arriva a 10^8 confronti. C, Java o JavaScript riescono a completarli in meno di un secondo, ma Python impiega più di dieci secondi; inoltre, raddoppiare sia N sia k rende ogni linguaggio quattro volte più lento. Lo spreco è evidente nella traccia: dopo ogni scelta è cambiata una sola testa, eppure il passaggio successivo le legge di nuovo tutte e k.

Algoritmo

Imposta pos[r] = 0 per ogni riga e conta i valori, N.
Ripeti N volte: guarda ogni riga con pos[r] ancora al suo interno e ricorda la riga la cui testa è la più piccola.
Aggiungi quella testa 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

La scansione rilegge k teste per trovare la più piccola, anche se dall’ultimo ciclo è cambiata una sola testa. Un min-heap serve proprio a questo: contiene un insieme di numeri con il più piccolo in cima, e sia estrarre il valore in cima sia aggiungere un numero costa O(log size).

Inserisci nell’heap il primo valore di ogni riga, contrassegnato con il numero della riga. Poi ripeti: estrai la coppia più piccola (value, row), aggiungi value e, se quella riga ha un altro valore, inseriscilo con lo stesso contrassegno. L’heap contiene sempre esattamente una voce per ogni riga che ha ancora valori: la sua testa; quindi il valore in cima è il più piccolo valore inutilizzato in assoluto. È la regola della scansione, ma applicata più rapidamente.

Segui il primo esempio numerando le righe a partire da 0. L’heap inizia con 2 (riga 0), 1 (riga 1) e 3 (riga 2). Estrai 1 e inserisci il valore successivo della riga 1, 4. Estrai 2 e inserisci 6 dalla riga 0. Estrai 3 e inserisci 5 dalla riga 2. Estrai 4 e inserisci 10. Estrai 5: la riga 2 è esaurita, quindi non viene inserito nulla e l’heap si riduce a 6 e 10. Estrai 6 e inserisci 9. Estrai 9, poi 10. Il risultato è [1, 2, 3, 4, 5, 6, 9, 10].

Ogni valore entra nell’heap una volta e ne esce una volta, e l’heap non contiene mai più di k voci, quindi ciascuna di queste 2N operazioni costa O(log k). Con N = k = 10^4, sono circa 2 × 10^4 × 14, meno di 3 × 10^5 passaggi, contro i 10^8 della scansione. L’heap usa O(k) memoria, mai O(N), perché conserva una testa per riga e non i valori che seguono.

Diverse versioni costruiscono l’heap manualmente, in un array di numeri di riga ordinati in base alla testa di ogni riga, con i figli della posizione i alle posizioni 2i+1 e 2i+2 (alle posizioni 2i e 2i+1 in Lua e R, che contano a partire da 1). Questo fa anche risparmiare lavoro: dopo aver estratto la testa della riga in cima, il valore successivo della riga non è minore, quindi la riga rimane in cima e scende di una volta, invece di eseguire un’estrazione seguita da un inserimento.

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

La logica dell'heap è breve. La maggior parte dei bug dipende da cosa viene inserito nell'heap e dall'ordine che viene usato.

Dimenticare da dove proviene un valore. Se l'heap contiene solo valori, dopo un'estrazione non puoi sapere quale riga far avanzare. Memorizza la riga insieme al valore.
Usare per errore un max-heap. C++ priority_queue e Rust BinaryHeap mettono in cima il valore più grande; usa greater<> o Reverse. Java PriorityQueue e Python heapq restituiscono già il valore più piccolo.
Parità in Python heapq. Quando due valori sono uguali, il confronto delle tuple passa al secondo elemento. Un numero di riga si può confrontare senza problemi, ma un nodo di lista concatenata no, e la versione classica va in errore quando i valori sono uguali. Inserisci al secondo posto un numero di riga o un contatore.
Inserire ogni valore all'inizio. L'ordinamento è comunque corretto, ma l'heap cresce fino a contenere N elementi e il lavoro diventa O(N log N). Mantieni un elemento in testa per ogni riga.
Leggere oltre la fine di una riga corta. Le righe hanno lunghezze diverse, quindi verifica che una riga abbia un valore successivo prima di inserirlo.
Eliminare i duplicati. I valori uguali provenienti da righe diverse sono valori distinti e devono essere tutti inclusi nel risultato.

Domande frequenti4

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 e rimosso una volta, e l'heap contiene al massimo k elementi, quindi ogni operazione costa O(log k). La memoria aggiuntiva è O(k), oltre all'output.

Perché non mettere tutti i valori insieme e ordinarli?

È corretto e richiede un tempo O(N log N), il che va bene per input piccoli. 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, cosa che l'ordinamento non può fare.

Riesci a fondere k liste ordinate senza usare un heap?

Sì, con la strategia divide et impera. Unisci le liste a coppie usando l'unione di due liste, poi unisci i risultati a coppie e così via. Ci sono log k passaggi e ogni passaggio coinvolge ogni valore una volta, quindi la complessità è anche O(N log k). Unire le liste una dopo l'altra in un risultato che cresce è più lento: i valori iniziali vengono copiati di nuovo a ogni unione, per una complessità complessiva di O(N·k).

Perché l'heap ha bisogno solo della testa di ogni lista?

Ogni lista è ordinata, quindi il suo primo valore non utilizzato è il più piccolo tra quelli rimasti. Il valore più piccolo tra tutte le liste è quindi il più piccolo tra le loro teste, e nessun valore più in profondità in una lista può superarlo. Quando una testa viene rimossa, il valore successivo della stessa lista diventa la testa di quella lista e prende il suo posto nell'heap.

Python

def mergeKLists(lists):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

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