Montón: proporcione un algoritmo de tiempo para fusionar listas ordenadas en una lista ordenada

15

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 kO(nlgk)knk

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 nknnk

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 )O(k)+O(k)+O(n(k+2lgk))O(nk+nlgk)O(nk)O(k)O(n)O(nlgk)

ramgorur
fuente

Respuestas:

13

El propósito del montón es darle el mínimo, por lo que no estoy seguro de cuál es el propósito de este ciclo for for j := 2 to k.

Mi opinión sobre el pseudocódigo:

lists[k][?]      // input lists
c = 0            // index in result
result[n]        // output
heap[k]          // stores index and applicable list and uses list value for comparison
                 // if i is the index and k is the list
                 //   it has functions - insert(i, k) and deleteMin() which returns i,k
                 // the reason we use the index and the list, rather than just the value
                 //   is so that we can get the successor of any value

// populate the initial heap
for i = 1:k                   // runs O(k) times
  heap.insert(0, k)           // O(log k)

// keep doing this - delete the minimum, insert the next value from that list into the heap
while !heap.empty()           // runs O(n) times
  i,k = heap.deleteMin();     // O(log k)
  result[c++] = lists[k][i]
  i++
  if (i < lists[k].length)    // insert only if not end-of-list
    heap.insert(i, k)         // O(log k)

La complejidad del tiempo total es, por lo tanto,O(klogk+n2logk)=O(nlogk)

También puede, en lugar de deleteMiny insert, tener un getMin( ) y un ( ), lo que reducirá el factor constante, pero no la complejidad.O ( log k )O(1)incrementIndexO(logk)

Ejemplo:
(usando el valor en lugar del índice y el índice y el montón de la lista representados como una matriz ordenada para mayor claridad)

Input: [1, 10, 15], [4, 5, 6], [7, 8, 9]

Initial heap: [1, 4, 7]

Delete 1, insert 10
Result: [1]
Heap: [4, 7, 10]

Delete 4, insert 5
Result: [1, 4]
Heap: [5, 7, 10]

Delete 5, insert 6
Result: [1, 4, 5]
Heap: [6, 7, 10]

Delete 6, insert nothing
Result: [1, 4, 5, 6]
Heap: [7, 10]

Delete 7, insert 8
Result: [1, 4, 5, 6, 7]
Heap: [8, 10]

Delete 8, insert 9
Result: [1, 4, 5, 6, 7, 8]
Heap: [9, 10]

Delete 9, insert nothing
Result: [1, 4, 5, 6, 7, 8, 9]
Heap: [10]

Delete 10, insert 15
Result: [1, 4, 5, 6, 7, 8, 9, 10]
Heap: [15]

Delete 15, insert nothing
Result: [1, 4, 5, 6, 7, 8, 9, 10, 15]
Heap: []

Done
Dukeling
fuente
supongamos que tiene estas listas para fusionar, list [1] = [1, 10, 15], list [2] = [4, 5, 6] y list [3] = [7, 8, 9]. En la primera iteración, el valor del montón será 1 y luego su algoritmo insertará 10 en el montón, pero 10 es el valor más grande de todas las listas. ¿Cómo evitará eso?
ramgorur
@ramgorur No importa que haya 10 en el montón. 4,5,6,7,8 y 9 se procesarán antes, ya que siempre obtenemos el valor más pequeño del montón y seguimos reemplazando los valores eliminados con el siguiente elemento de la misma lista. Respuesta editada con ejemplo.
Dukeling
bueno, si este es el caso, no tenemos que recordar la misma lista para el siguiente elemento empujado. Podemos elegir una lista aleatoria cada vez y poner el siguiente elemento en el montón, lo que supuestamente también dará el mismo resultado, ¿estoy en lo cierto? ¿O hay alguna otra razón especial para seguir el mismo argumento de lista ?
ramgorur
Al eliminar 4, si elige una lista aleatoria, puede terminar insertando 8, por lo que será el montón [7, 8, 10], desde el cual insertará en 7lugar de 5en el conjunto de resultados, lo que será incorrecto.
Dukeling
El comentario de @ AshwaniGautam sobre la otra respuesta es acertado: la creación del montón inicialmente se puede hacer a tiempo . O(k)
Raphael
13

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:

  1. Coloque los primeros elementos de las listas en un montón mínimo de tamaño . Recuerde que para cada elemento de la lista al que pertenece. ( )k l m O ( k lg k )HklmO(klgk)
  2. Para de a hacer: 1 ni1n
    • Extraiga el mínimo de y guárdelo en el ( )mHresult[i]O(lgk)
    • Inserte el sucesor directo de en (si lo hay) en ( )mlmHO(lgk)

El tiempo de ejecución es obviamente en y el algoritmo ordena correctamente el .O(klgk+nortelgk)=O(nortelgk)rmistult

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.yormistultHyormistult[1 ..yo]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 generalrmistultHrmistultr1lr1l[1]r1r1l[1]<r1r1elemento más pequeño Obviamente, el mínimo de todos los primeros elementos es el que se inserta en el .rmistult

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 queyoryoHHmetrollHrmistultryometroll está ordenado, y por lo tanto, las reservas invariantes.

Al finalizar, tenemos el correctamente ordenado.rmistult[1 ..norte]

Marca Cornelius
fuente
En realidad, la mayor complejidad del tiempo sería O (K + 2 * NlogK) = O (NlogK) . O (K) es más estricto que O (KlogK), al hacer un montón. Consulte esto para obtener más aclaraciones.
Ashwani Gautam
O(k)O(klogk)k