Алгоритм K-Way Merge. Будет ли это решение O (n log k)?

Question

Таким образом, проблема состоит в том, чтобы объединить k отсортированных списков (предположим, что они отсортированы в порядке возрастания) в 1 список из n элементов, используя минимальную кучу. Теперь я нашел решение для него, но я не уверен, может ли он иметь время работы nlogk. Вот мой псевдокод, что вы, ребята, думаете?

Algorithm kWayMerge(S) 
    t ← 0 
    Result ← ∅ 
    while t ≤ n do 
     choosenHeap ← min(S1[1], … Sk[1]) 
     t ← t + 1 
     Result[t] ← DeleteMin(choosenHeap) 
    end loop 
end 

Function DeleteMin(H) 
    Min ← A[1] 
    A[1] ← A[size[H]] 
    size[H] ← size[H] - 1 
    DownHeap(H, 1) 
    return Min 
end 

Function DownHeap(A, t) 
    c ← 2*t 
    if c > size[A] then 
     return 
    if c+1 > size[A] && A[c] > A[c + 1] then 
     c ← c + 1 
    temp ← A[t] 
    A[t] ← A[c] 
    A[c] ← temp 
    DownHeap(A, c) 
end 

В основном мое решение для поиска K списки и найти Min вороха с наименьшим значением корня и поместить его в результирующий массив. В основном внешний цикл в kWayMerge будет повторяться n раз за счет удаления всех элементов из k отсортированных списков.

Answer 1

Ваш предложенный алгоритм известен как Ideal Merge technique for k-way merge, и на самом деле работает в О (п LOG (к)), предполагая, что мин-кучный реализуются со структурой логарифмических данных (например, binary heap.

• куча доступ Θ (п) раз, потому что каждый элемент вставлен и экстрагируют один раз.

• куча содержит, в каждой точке, в большинстве к (обратите внимание, что некоторые списки могут быть «исчерпаны» перед другими).

• Все остальные операции - постоянное время на элемент.

Таким образом, если каждый доступ к куче O (журнал (к «)), где к» является количество элементов в куче, то общее побережье О (п log (k)).

Answer 2

Мин имеет проточную время тоже и здесь его O (к)

так его O (NK) logk