probar el algoritmo que usa min-heap para combinar k listas ordenadas

Question

Estoy leyendo CLRS y tuve algún problema con el ejercicio 6.5-8.

Dé un O (n lg k) -Tiempo algoritmo para combinar k ordenados listas en una sola lista ordenada, donde n es el número total de elementos en todas las entradas listas. (Pista: utilizar un min0heap para k vías fusión.)

La solución es, como dice todo el mundo,

1) construir un elemento k min-montón usando el primer elemento de las listas K,

2) extraer-min() para obtener el elemento más pequeño de la pila y añadirlo a la lista de resultados,

3) recoger el siguiente elemento de la misma lista como el que acaba de extraer a partir de el montón Insertarlo en el montón y volver 2).

Entiendo que el tiempo es O (n lg k), pero no obtengo la corrección de la opción en el paso 3). Es parece obvio, pero ¿hay alguna prueba formal?

Answer 1

El principal impulso de la prueba de corrección es que el menor elemento restante es siempre el que se extraerá. La clave invariante en apoyo de esta afirmación es que la cola de prioridad contiene, para cada lista, el elemento menos restante de esa lista. A partir de esta invariante, se deduce que, dado que el elemento menos restante es también el elemento menos restante de su lista, es devuelto por extract-min.

Tenemos que elegir un elemento de la misma lista en la parte 3 para mantener la invariante de que cada lista tiene su elemento menos en la cola. De lo contrario, podríamos tener una situación como

1 2 
3 4 

donde si tiramos 1 de la cola inicial que contiene 1 y 3 y reemplazarlo con 4, la próxima extracción será de 3, lo que está mal.