объединить k списков с o (nlogk) - PullRequest
Новая
       15

объединить k списков с o (nlogk)

0 голосов
/ 26 июня 2010

Является ли время работы алгоритма Merge O ( n log k )?

  • k количество списков.
  • n - общее количество элементов во всех списках ( n = n 1 + n 2 + ... + n k ). 
algorithm MakingAHalf(List_Of_Lists)
    if List_Of_Lists.size() = 1
        return the only list in List_Of_Lists
    else
        split List_Of_Lists into two halfs (First_Half and Second_Half)
    MakingAHalf(First_Half)
    MakingAHalf(Second_Half)
    Merge(First_Half, Second_Half, Min_Heap)

algorithm Merge(First_Half, Second_Half, Min_Heap)   //T(n) = O(n log k)?
    while First_Half  is not empty and First_Second is not empty do
        if First_Half.first().element() < Second_Half.first().element() then
            Insert(Min_Heap, First_Half.remove(First_Half.first()))
        else
            Insert(Min_Heap, Second_Half.remove(Second_Half.first())  
    while First_Half is not empty do
        Insert(Min_Heap, First_Half.remove(First_Half.first()) 
    while Second_Half is not empty do
        Insert(Min_Heap, Second_Half.remove(Second_Half.first())

algorithm Insert(A, key)
    A[n+1] <-- key
    while (i > 1) and (A[i] > A[[i/2]]) do
        swap A[i] and A[[i/2]]
        i <-- i - 1

Ответы [ 2 ]

1 голос
/ 26 июня 2010

Глядя на ваш код, кажется, что вы очень озадачены тем, что такое minHeaps. Код, который у вас есть, совершенно неправильный, и говорить о том, что пора выполнять сложную сортировку с помощью границ, становится бессмысленным.

Ваш метод Merge ничего не делает для объединения двух списков, все, что он делает, это вставляет элементы в MinHeap и это тоже в отсортированном порядке !, что кажется совершенно бессмысленным.

Если вы используете MinHeap в качестве кучи, доступной для всех вызовов, а затем читаете из нее, то это O (n logn), поскольку вы вставляете n элементов в кучу, и вам не нужны все эти рекурсивные вызовы, просто вставьте их один за другим!

Так как это похоже на домашнюю работу, я лишь дам вам подсказку: в любой момент в куче должно быть не более k элементов.

0 голосов
/ 18 ноября 2011

Слияние - O(log N), Слияние - O(NlogN). HeapSort - это другой алгоритм.

...