归并排序的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) 个索引被扫描 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);
  }
}

归并排序的K-way归并操作

K-way merge operation for merge sort

algorithm

multidimensional-array

merge

mergesort

array-merge