将k个排序数组合并为一个排序数组[重复]

Question

我想写一个时间O（n*lgk）的算法，将k个排序数组合并成一个排序数组，其中n是所有输入数组的元素总数。

你能告诉我怎么做吗？

编辑：我编写了以下算法：

Algorithm(L) // L=[L1, L2, L3, ...., Lk]
  list=LNEW;
  for (i=1; i<=k; i++){
      H[i]=L[i][1];
  }
  BUILD-HEAP(H);
  j=1;
  while (j<n){
         LNEW[j]=H[1];
         yes=0;
         m=1;
         while (m<=k and L[m][j]!=NULL and L[m][j+1]!=NULL and yes!=1){
                if (H[1]==L[m][j]){
                    H[1]=L[m][j+1];
                    yes=1;
                    Heapify(H);
                }
                j=j+1;
  }

你能告诉我这是否正确吗？

Answer 1

我们可以维护由k个元素firstFree组成的数组，其中firstFree[i]是第i个数组中第一个未使用的元素。另外，我们可以有一个最多包含k个元素的堆（每个元素是一对（值，包含该值的数组的索引））。最初，我们应该将所有给定数组的第一个元素放入这个堆中。之后，我们应该重复以下过程，直到堆为空：

>

弹出堆的顶部元素。将其添加到输出数组中。

增加包含此元素的数组的firstFree值。如果没有超过数组的大小，则将下一个元素添加到堆中。

该算法不进行n次插入和弹出操作，因此其时间复杂度为O（n log k）。