Операция слияния K-way для сортировки слияния

Question

У меня есть k отсортированные массивы, каждый с элементами n, и их необходимо объединить в один отсортированный массив из k*n элементов.

Как реализовать процедуру слияния для сортировки слияния, начиная с первых двух и последующих и так далее?

Это то, что у меня есть до сих пор.

// implementing function to merge arrays (merge procedure for merge sort) 
    public int[] merge(int[][] array){ 
     int k = array.length; 
     int n = array[0].length; 

// final merged array 
     int[] mergedArray = new int[k*n]; 
     return mergedArray;  
    } 

    public static void main(String[]args){ 
    Merge obj = new Merge(); 
int[][] data= new int[][]{{2, 9, 15, 20}, 
           {6, 8, 9, 19}, 
           {5, 10, 18, 22}, 
           {8, 12, 15, 26}}; 
    int[] mergedArrayTest = obj.merge(data); 
    //printArray(mergedArrayTest); 
    } 

Answer 1

Вместо слияния подмассивов два в то время, вы можете объединить все k сразу.

• Сделать массив индексов в каждом подматрице. Первоначально каждый индекс равен нулю.
• На каждую из k*n итераций для заполнения объединенного массива учитывайте каждое значение подмассива в соответствующем индексе и помните минимальное значение. (Пропустите индекс, если он уже достиг конца подматрицы.)
• Увеличьте индекс, указывающий на минимальное значение.

Это будет делать это:

// k-way merge operation 
public int[] merge(int[][] array){ 
    int k = array.length; 
    int n = array[0].length; 

    int[] mergedArray = new int[k*n]; 
    int[] indices = new int[k]; 
    for (int i = 0; i < mergedArray.length; ++i) { 
    int bestValue = -1, bestIndex = -1; 
    for (int j = 0; j < indices.length; ++j) { 
     int index = indices[j]; 
     if (index < n && (bestValue == -1 || array[j][index] < bestValue)) { 
     bestValue = array[j][index]; 
     bestIndex = j; 
     } 
    } 
    mergedArray[i] = bestValue; 
    indices[bestIndex] += 1; 
    } 

    return mergedArray; 
} 

Вы можете сделать этот подход несколько более эффективным удалением индексов, которые достигли конца своей подрешетки. Тем не менее, это все еще оставляет время работы в O (NK), потому что O (K) Индексов сканируются пк раз.

Мы можем сделать асимптотическое улучшение времени выполнения, сохраняя индексы в мини-куче, которая использует значение для каждого индекса в качестве ключа. С k индексы, размер кучи никогда не превышает k. В каждом из nk итераций мы выкладываем кучу и нажимаем не более одного элемента назад. Эти операции кучи каждый стоят O (log k), поэтому общее время работы O (nk log k).

import java.lang.*; 
import java.util.*; 
import java.io.*; 

class Candidate { 
    int id, index, value; 
    Candidate(int id, int index, int value) { 
    this.id = id; 
    this.index = index; 
    this.value = value; 
    } 
} 

class Heap { 
    ArrayList<Candidate> stack = new ArrayList<Candidate>(); 

    void push(Candidate current) { 
    // Add to last position in heap. 
    stack.add(current); 
    // Bubble up. 
    int n = stack.size(), 
     pos = n - 1; 
    while (pos != 0) { 
     int parent = (pos - 1)/2; 
     if (stack.get(parent).value <= current.value) { 
     return; 
     } 
     stack.set(pos, stack.get(parent)); 
     stack.set(parent, current); 
    } 
    } 

    Candidate pop() { 
    // Get top of heap. 
    if (stack.size() == 0) { 
     return null; 
    } 
    Candidate result = stack.get(0); 
    int n = stack.size(); 
    if (n == 1) { 
     stack.remove(0); 
     return result; 
    } 
    // Swap last element to top. 
    stack.set(0, stack.get(--n)); 
    Candidate current = stack.get(0); 
    stack.remove(n); 
    // Bubble down. 
    int pos = 0; 
    while (true) { 
     int left = 2 * pos + 1; 
     if (left >= n) { 
     return result; 
     } 
     int right = left + 1, 
      swapTo = -1; 
     if (current.value <= stack.get(left).value) { 
     if (right == n || current.value <= stack.get(right).value) { 
      return result; 
     } 
     swapTo = right; 
     } else { 
     if (right != n && stack.get(left).value > stack.get(right).value) { 
      swapTo = right; 
     } else { 
      swapTo = left; 
     } 
     } 
     stack.set(pos, stack.get(swapTo)); 
     stack.set(swapTo, current); 
     pos = swapTo; 
    } 
    } 
} 

public class Merge { 

    // k-way merge 
    public int[] merge(int[][] array){ 
    int k = array.length; 
    int n = array[0].length; 

    int[] mergedArray = new int[k*n]; 

    // Initialize heap with subarray number, index, and value. 
    Heap indexHeap = new Heap(); 
    for (int i = 0; i < k; ++i) { 
     indexHeap.push(new Candidate(i, 0, array[i][0])); 
    } 

    for (int i = 0; i < mergedArray.length; ++i) { 
     // Get the minimum value from the heap and augment the merged array. 
     Candidate best = indexHeap.pop(); 
     mergedArray[i] = best.value; 
     // Increment the index. If it's still valid, push it back onto the heap. 
     if (++best.index < array[best.id].length) { 
     best.value = array[best.id][best.index]; 
     indexHeap.push(best); 
     } 
    } 

    // Print out the merged array for testing purposes. 
    for (int i = 0; i < mergedArray.length; ++i) { 
     System.out.print(mergedArray[i] + " "); 
    } 
    System.out.println(); 
    return mergedArray; 
    } 

    public static void main(String[]args){ 
    Merge merge = new Merge(); 
    int[][] data= new int[][]{{2, 9, 15, 20}, 
           {6, 8, 9, 19}, 
           {5, 10, 18, 22}, 
           {8, 12, 15, 26}}; 
    int[] mergedArrayTest = merge.merge(data); 
    } 
}