Heap - forneça um algoritmo de tempo

15

Provavelmente, essa pergunta já foi feita antes. É do problema do CLRS (2nd Ed) 6.5-8 -

Dê um algoritmo de tempo O(nlgk) para mesclar k listas classificadas em uma lista classificada, em que n é o número total de elementos em todas as listas de entrada. (Dica: use um min-heap para mesclar -way.)k

Como existem listas ordenadas e o total de valores, vamos assumir que cada lista contém nnknnk , além disso, cada uma das listas é classificada em ordem estritamente crescente, e os resultados também serão armazenados em ordem crescente.

Meu pseudo-código se parece com isso -

    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

Minha complexidade geral se torna . Não consegui encontrar nenhuma maneira de evitar oloop O ( k ) dentro do O ( n )O(k)+O(k)+O(n(k+2lgk))O(nk+nlgk)O(nk)O(k)O(n)loop para encontrar o próximo elemento mínimo das listas k. Existe alguma outra maneira de contornar? Como obter um algoritmo ?O(nlgk)

ramgorur
fonte

Respostas:

13

O objetivo do heap é fornecer o mínimo, então não tenho certeza de qual é o objetivo desse loop for - for j := 2 to k.

Minha opinião sobre o pseudo-có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)

A complexidade total do tempo é, portanto, O(klogk+n2logk)=O(nlogk)

Você também pode, em vez de deleteMine insert, ter um getMin( ) e um ( O ( log k ) ), o que reduzirá o fator constante, mas não a complexidade.O(1)incrementIndexO(logk)

Exemplo:
(usando valor em vez de índice e lista índice e heap representados como uma matriz classificada para maior clareza)

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
fonte
digamos que você tenha essas listas para mesclar, lista [1] = [1, 10, 15], lista [2] = [4, 5, 6] e lista [3] = [7, 8, 9]. Na primeira iteração, o valor do heap será 1 e, em seguida, seu algoritmo inserirá 10 no heap, mas 10 é o maior valor de todas as listas - como você evitará isso?
ramgorur
@ramgorur Não importa que 10 esteja na pilha. 4,5,6,7,8 e 9 serão processados ​​antes, pois sempre obtemos o menor valor do heap e continuamos substituindo os valores excluídos pelo próximo item da mesma lista. Resposta editada com exemplo.
Dukeling
bem, se esse for o caso, não precisamos lembrar a mesma lista para o próximo envio de elemento. Podemos escolher uma lista aleatória todas as vezes e colocar o próximo elemento no heap - o que também dará o mesmo resultado, certo? Ou existe algum outro motivo especial para seguir o mesmo argumento da lista ?
ramgorur
Ao excluir 4, se você escolher uma lista aleatória, poderá acabar inserindo 8, portanto, o heap será [7, 8, 10], do qual você inserirá, e 7não 5no conjunto de resultados, o que estará errado.
Dukeling
O comentário de @ AshwaniGautam na outra resposta é adequado: a criação da pilha inicialmente pode ser feita a tempo . O(k)
Raphael
13

Antes de tudo, acho que sua suposição de que todas as listas possuem entradas não é válida se o tempo de execução do algoritmo depender do tamanho da lista mais longa .n/k

Quanto ao seu problema, o seguinte algoritmo deve fazer o truque:

  1. Colocar os primeiros elementos das listas em um min-montão de tamanho k . Lembre-se de cada elemento da listaHk a que pertence. ( O ( k lg k ) )lmO(klgk)
  2. Para de 1 a n faça: i1n
    • Extrai-se a mínima a partir de H e armazená-lo no r e s u l T [mHresult[i]O(lgk)
    • Insira o sucessor direto de em l m (se houver) em HmlmHO(lgk)

O(klgk+nlgk)=O(nlgk)result

iresultHiresult[1..i]i

resultHresultr1lr1l[1]r1r1l[1]<r1r1result

iriHHmllHresultrimll

result[1..n]

Cornelius Brand
fonte
Na verdade, a menor complexidade do tempo seria O (K + 2 * NlogK) = O (NlogK) . O (K) é mais restrito que O (KlogK), ao fazer um Heap. Consulte isso para mais esclarecimentos.
Ashwani Gautam
O(k)O(klogk)k