dimostrare l'algoritmo che utilizza il min-heap per unire k liste ordinate

Question

Sto leggendo CLRS e ho avuto qualche problema con l'esercizio 6.5-8.

Invia un O (n lg k) algoritmo con tempo di fondere k ordinate liste in uno lista ordinata, dove n è il numero totale di elementi in tutti gli ingressi elenchi. (Suggerimento: usare un min0heap per k-way fusione.)

La soluzione è, come tutti dicono,

1) costruire un k-elemento min-heap utilizzando il primo elemento delle liste k,

2) estrarre-min() per ottenere l'elemento più piccolo dal mucchio e aggiungerlo alla lista dei risultati,

3) raccogliere l'elemento successivo da alla medesima lista come quella che abbiamo appena estratto dalla il mucchio. Inseriscilo nell'heap e goto 2).

Posso capire che il tempo è O (n lg k), ma non ho la correttezza della scelta nel passaggio 3). È sembra ovvio ma c'è qualche prova formale?

Answer 1

La spinta principale della dimostrazione della correttezza è che l'elemento meno rimanente è sempre quello da estrarre. L'invariante di chiave a supporto di questa affermazione è che la coda di priorità contiene, per ogni lista, l'ultimo elemento rimasto da quella lista. Da questo invariante, ne consegue che, dal momento che il minimo elemento rimanente è anche l'elemento minimo rimanente dall'elenco, viene restituito da extract-min.

Abbiamo bisogno di scegliere un elemento dalla stessa lista nella parte 3 per mantenere l'invariante che ogni lista ha il suo minimo elemento nella coda. Altrimenti, si potrebbe avere una situazione come

1 2 
3 4 

dove se saremo 1 dalla coda iniziale contenente 1 e 3 e sostituirlo con 4, la prossima estrazione sarà 3, che è errata.