Lo más probable es que esta pregunta se haga antes. Es del problema 6.5-8 de CLRS (2nd Ed)
Proporcione un algoritmo de tiempo para fusionar listas ordenadas en una lista ordenada, donde es el número total de elementos en todas las listas de entrada. (Pista: Utilice un min-montón para fusión -way.)k n k
Como hay listas ordenadas y un total de valores, supongamos que cada lista contiene números , además cada una de las listas está ordenada en orden estrictamente ascendente, y los resultados también se almacenarán en orden ascendente orden.n n
Mi pseudocódigo se ve así:
list[k] ; k sorted lists
heap[k] ; an auxiliary array to hold the min-heap
result[n] ; array to store the sorted list
for i := 1 to k ; O(k)
do
heap[i] := GET-MIN(list[i]) ; pick the first element
; and keeps track of the current index - O(1)
done
BUILD-MIN-HEAP(heap) ; build the min-heap - O(k)
for i := 1 to n
do
array[i] := EXTRACT-MIN(heap) ; store the min - O(logk)
nextMin := GET-MIN(list[1]) ; get the next element from the list 1 - O(1)
; find the minimum value from the top of k lists - O(k)
for j := 2 to k
do
if GET-MIN(list[j]) < nextMin
nextMin := GET-MIN(list[j])
done
; insert the next minimum into the heap - O(logk)
MIN-HEAP-INSERT(heap, nextMin)
done
Mi complejidad general se convierte en . No pude encontrar ninguna manera de evitar el bucle dentro del bucle para encontrar el siguiente elemento mínimo de las listas k. ¿Hay alguna otra forma de evitarlo? ¿Cómo obtener un algoritmo ?O ( k ) O ( n ) O ( n lg k )
4
, si elige una lista aleatoria, puede terminar insertando8
, por lo que será el montón[7, 8, 10]
, desde el cual insertará en7
lugar de5
en el conjunto de resultados, lo que será incorrecto.En primer lugar, creo que su suposición de que todas las listas que tienen entradas no es válida si el tiempo de ejecución del algoritmo depende de la longitud de la lista más larga .n / k
En cuanto a su problema, el siguiente algoritmo debería hacer el truco:
El tiempo de ejecución es obviamente en y el algoritmo ordena correctamente el .O ( k lgk + n lgk ) = O ( n lgk ) r e s u l t
Prueba (o al menos, una idea para una prueba). Considere el siguiente bucle invariante: el elemento -ésimo para insertar en el es siempre el mínimo del montón mínimo en el paso y, por lo tanto, el se ordena correctamente después de la iteración -ésima.yo r e s u l t H yo r e s u l t [ 1 .. i ] yo
Esto es cierto antes de la primera iteración: Primero, mostramos que el primer elemento para insertar en el está en : Supongamos hacia una contradicción que el primer elemento para insertar en el (es decir, el elemento más pequeño en general, ) fue No es un primer elemento. Luego, en la lista que contiene , el primer elemento debe ser distinto de (como se supone, no es un primer elemento). Como están ordenados nuestras listas, tenemos incluso , pero esto es una contradicción, ya que elegimos ser la generalr e s u l t H r e s u l t r1 l r1 l [ 1 ] r1 r1 l [ 1 ] < r1 r1 elemento más pequeño Obviamente, el mínimo de todos los primeros elementos es el que se inserta en el .r e s u l t
La invariante se mantiene después de una iteración: procedemos de la misma manera. Suponga que el elemento -ésima para insertar (llaman ) no estaban en . Por construcción, tiene como máximo un elemento de cada lista, y una vez que contiene un elemento de una lista , todos sus predecesores en ya se extrajeron de y (por hipótesis) se insertaron correctamente en el . Por lo tanto, se supone que es el sucesor de algún elemento en la lista . Pero esto es, como arriba, una contradicción, ya queyo ryo H H metro l l H r e s u l t ryo metro l l está ordenado, y por lo tanto, las reservas invariantes.
Al finalizar, tenemos el correctamente ordenado.r e s u l t [ 1 .. n ]
fuente