Tas - Donner un algorithme de temps pour fusionner listes triées en une seule liste triée

15

Très probablement, cette question est posée avant. C'est du problème 6.5-8 de CLRS (2nd Ed) -

Donnez un algorithme de temps pour fusionner listes triées en une seule liste triée, où est le nombre total d'éléments dans toutes les listes d'entrée. (Astuce: utilisez un min-tas pour la fusion -way.)k n kO(nlgk)knk

Comme il y a listes triées et un total de valeurs, supposons que chaque liste contient des nombres , de plus chacune des listes est triée dans un ordre strictement croissant et les résultats seront également stockés dans l'ordre croissant commande.n nknnk

Mon pseudo-code ressemble à ceci -

    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

Ma complexité globale devient . Je n'ai pas pu trouver de moyen d'éviter la boucle à l'intérieur de la boucle pour trouver l'élément minimum suivant à partir de k listes. Y a-t-il un autre moyen de contourner? Comment obtenir un algorithme ?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
la source

Réponses:

13

Le but du tas est de vous donner le minimum, donc je ne sais pas quel est le but de cette boucle for - for j := 2 to k.

Ma vision du pseudo-code:

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 complexité temporelle totale est doncO(klogk+n2logk)=O(nlogk)

Vous pouvez également, au lieu de deleteMinet insert, avoir un getMin( ) et un ( ), ce qui réduira le facteur constant, mais pas la complexité.O(1)incrementIndexO(logk)

Exemple:
(en utilisant la valeur plutôt que l'index et l'index de liste et le tas représentés comme un tableau trié pour plus de clarté)

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
la source
disons que vous avez ces listes à fusionner, liste [1] = [1, 10, 15], liste [2] = [4, 5, 6] et liste [3] = [7, 8, 9]. À la première itération, la valeur du tas sera 1 et ensuite votre algorithme insérera 10 dans le tas, mais 10 est la plus grande valeur de toutes les listes - comment allez-vous éviter cela?
ramgorur
@ramgorur Peu importe que 10 soient dans le tas. 4,5,6,7,8 et 9 seront tous traités avant, car nous obtenons toujours la plus petite valeur du tas et continuons à remplacer les valeurs supprimées par l'élément suivant de la même liste. Réponse modifiée avec exemple.
Dukeling
eh bien, si c'est le cas, nous n'avons pas besoin de nous souvenir de la même liste pour la prochaine poussée d'élément. Nous pouvons choisir une liste aléatoire à chaque fois et pousser l'élément suivant en tas - ce qui donnera également le même résultat, ai-je raison? Ou existe-t-il une autre raison particulière de suivre le même argument de liste ?
ramgorur
Lors de la suppression 4, si vous choisissez une liste aléatoire, vous pouvez finir par insérer 8, ainsi le tas sera [7, 8, 10], à partir duquel vous insérerez 7plutôt que 5dans le jeu de résultats, ce qui sera faux.
Dukeling
@ Le commentaire d'AshwaniGautam sur l'autre réponse est pertinent: la création initiale du tas peut se faire dans le temps . O(k)
Raphael
13

Tout d'abord, je pense que votre hypothèse de toutes les listes ayant entrées n'est pas valide si le temps d'exécution de l'algorithme dépend de la longueur de la liste la plus longue .n/k

Quant à votre problème, l'algorithme suivant devrait faire l'affaire:

  1. HklmO(klgk)
  2. i1n
    • mHresult[i]O(lgk)
    • Insérez le successeur direct de dans l m (le cas échéant) dans H ( O ( lg k ) )mlmHO(lgk)

Le temps d'exécution est évidemment dans et l'algorithme trie correctement r e s u l t .O(klgk+nlgk)=O(nlgk)result

Preuve (ou du moins, une idée de preuve). Considérez l'invariant de boucle suivant: Le -ème élément à insérer dans r e s u l t est toujours le minimum du min-tas H à l'étape i et donc, r e s u l t [ 1 .. i ] est correctement trié après la i- ème itération.iresultHiresult[1..i]i

resultHresultr1lr1l[1]r1r1un premier élément). Comme nos listes sont toutes triées, nous avons même , mais c'est une contradiction, car nous avons choisi r 1 pour être le plus petit élément global . Évidemment, le minimum de tous les premiers éléments est celui à insérer dans r e s u l t .l[1]<r1r1result

iriHHmllHresultrimll

result[1..n]

Marque Cornelius
la source
En fait, la complexité temporelle plus serrée serait O (K + 2 * NlogK) = O (NlogK) . O (K) est lié plus étroitement que O (KlogK), lors de la création d'un tas. Reportez - vous à cela pour plus de précisions.
Ashwani Gautam
O(k)O(klogk)k