用于归并排序的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而不是一次合并两个子数组。

• 为每个子数组创建一个索引数组。初始值为0。
• 在每次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;
}

可以通过删除到达子数组末尾的索引来提高这种方法的效率。然而，这仍然使运行时间停留在 0 (nk²)，因为 0 (k)索引被扫描nk次。

我们可以通过将索引存储在最小堆中，并使用每个索引处的值作为键来逐步改善运行时间。对于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);
  }
}