给定k个大小为n的排序数组，合并它们并打印排序后的输出。
null
例子：
输入： k=3，n=4 arr[][]={{1,3,5,7}， {2, 4, 6, 8}, {0, 9, 10, 11}} ; 输出： 0 1 2 3 4 5 6 7 8 9 10 11 说明： 输出数组是一个包含输入矩阵所有元素的排序数组。
输入： k=4，n=4 arr[][={{1,5,6,8}， {2, 4, 10, 12}, {3, 7, 9, 11}, {13, 14, 15, 16}} ; 输出： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 说明： 输出数组是一个包含输入矩阵所有元素的排序数组。
天真的方法 : 最简单的方法是创建一个大小为n*k的输出数组，然后将所有元素复制到输出数组中，然后进行排序。
- 算法：
- 创建大小为n*k的输出数组。
- 从头到尾遍历矩阵，并在输出数组中插入所有元素。
- 排序并打印输出数组。
- 实施：
C++14
// C++ program to merge k sorted arrays of size n each. #include<bits/stdc++.h> using namespace std; #define n 4 // A utility function to print array elements void printArray( int arr[], int size) { for ( int i=0; i < size; i++) cout << arr[i] << " " ; } // This function takes an array of arrays as an argument and // All arrays are assumed to be sorted. It merges them together // and prints the final sorted output. void mergeKArrays( int arr[][n], int a, int output[]) { int c=0; //traverse the matrix for ( int i=0; i<a; i++) { for ( int j=0; j<n ;j++) output=arr[i][j]; } //sort the array sort(output,output + n*a); } // Driver program to test above functions int main() { // Change n at the top to change number of elements // in an array int arr[][n] = {{2, 6, 12, 34}, {1, 9, 20, 1000}, {23, 34, 90, 2000}}; int k = sizeof (arr)/ sizeof (arr[0]); int output[n*k]; mergeKArrays(arr, 3, output); cout << "Merged array is " << endl; printArray(output, n*k); return 0; } |
JAVA
// Java program to merge k sorted arrays of size n each. import java.io.*; import java.util.*; class GFG { // This function takes an array of arrays as an argument // and // All arrays are assumed to be sorted. It merges them // together and prints the final sorted output. public static void mergeKArrays( int [][] arr, int a, int [] output) { int c = 0 ; // traverse the matrix for ( int i = 0 ; i < a; i++) { for ( int j = 0 ; j < 4 ; j++) output = arr[i][j]; } // sort the array Arrays.sort(output); } // A utility function to print array elements public static void printArray( int [] arr, int size) { for ( int i = 0 ; i < size; i++) System.out.print(arr[i] + " " ); } // Driver program to test above functions public static void main(String[] args) { int [][] arr = { { 2 , 6 , 12 , 34 }, { 1 , 9 , 20 , 1000 }, { 23 , 34 , 90 , 2000 } }; int k = 4 ; int n = 3 ; int [] output = new int [n * k]; mergeKArrays(arr, n, output); System.out.println( "Merged array is " ); printArray(output, n * k); } } |
Python3
# Python program to merge k sorted arrays of size n each. # This function takes an array of arrays as an argument # and # All arrays are assumed to be sorted. It merges them # together and prints the final sorted output. def mergeKArrays(arr, a, output): c = 0 ; # traverse the matrix for i in range (a): for j in range ( 4 ): output = arr[i][j]; c + = 1 ; # sort the array output.sort(); # A utility function to print array elements def printArray(arr, size): for i in range (size): print (arr[i], end = " " ); # Driver program to test above functions if __name__ = = '__main__' : arr = [[ 2 , 6 , 12 , 34 ],[ 1 , 9 , 20 , 1000 ],[ 23 , 34 , 90 , 2000 ]] ; k = 4 ; n = 3 ; output = [ 0 for i in range (n * k)]; mergeKArrays(arr, n, output); print ( "Merged array is " ); printArray(output, n * k); # This code is contributed by umadevi9616 |
C#
// C# program to merge k sorted arrays of size n each. using System; public class GFG { // This function takes an array of arrays as an argument // and // All arrays are assumed to be sorted. It merges them // together and prints the readonly sorted output. public static void mergeKArrays( int [,] arr, int a, int [] output) { int c = 0; // traverse the matrix for ( int i = 0; i < a; i++) { for ( int j = 0; j < 4; j++) output = arr[i,j]; } // sort the array Array.Sort(output); } // A utility function to print array elements public static void printArray( int [] arr, int size) { for ( int i = 0; i < size; i++) Console.Write(arr[i] + " " ); } // Driver program to test above functions public static void Main(String[] args) { int [,] arr = { { 2, 6, 12, 34 }, { 1, 9, 20, 1000 }, { 23, 34, 90, 2000 } }; int k = 4; int n = 3; int [] output = new int [n * k]; mergeKArrays(arr, n, output); Console.WriteLine( "Merged array is " ); printArray(output, n * k); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to merge k sorted // arrays of size n each. // This function takes an array of // arrays as an argument and // All arrays are assumed to be sorted. // It merges them together and prints // the final sorted output. function mergeKArrays(arr , a, output) { var c = 0; // traverse the matrix for (i = 0; i < a; i++) { for (j = 0; j < 4; j++) output = arr[i][j]; } // sort the array output.sort((a,b)=>a-b); } // A utility function to print array elements function printArray(arr , size) { for (i = 0; i < size; i++) document.write(arr[i] + " " ); } // Driver program to test above functions var arr = [ [ 2, 6, 12, 34 ], [ 1, 9, 20, 1000 ], [ 23, 34, 90, 2000 ] ]; var k = 4; var n = 3; var output = Array(n * k).fill(0); mergeKArrays(arr, n, output); document.write( "Merged array is " ); printArray(output, n * k); // This code contributed by Rajput-Ji </script> |
输出：
Merged array is 1 2 6 9 12 20 23 34 34 90 1000 2000
- 复杂性分析：
- 时间复杂性： O（n*k*log（n*k））。 因为生成的数组大小为N*k。
- 空间复杂性： O（n*k），输出数组的大小为n*k。
有效的方法 这个过程可以从将数组合并为两组开始。在第一次合并之后，我们有了k/2数组。再次分组合并数组，现在我们有了k/4数组。这类似于合并排序。将k个数组分成两半，包含相等数量的数组，直到一组中有两个数组。然后以自下而上的方式合并阵列。
- 算法：
- 创建一个递归函数，该函数接受k个数组并返回输出数组。
- 在递归函数中，如果k的值为1，则返回数组；如果k的值为2，则在线性时间内合并两个数组并返回数组。
- 如果k的值大于2，则将k元素组分成两等分，并递归调用该函数，即在一个递归函数中0到k/2数组，在另一个递归函数中k/2到k数组。
- 打印输出数组。
- 实施：
C++14
// C++ program to merge k sorted arrays of size n each. #include<bits/stdc++.h> using namespace std; #define n 4 // Merge arr1[0..n1-1] and arr2[0..n2-1] into // arr3[0..n1+n2-1] void mergeArrays( int arr1[], int arr2[], int n1, int n2, int arr3[]) { int i = 0, j = 0, k = 0; // Traverse both array while (i<n1 && j <n2) { // Check if current element of first // array is smaller than current element // of second array. If yes, store first // array element and increment first array // index. Otherwise do same with second array if (arr1[i] < arr2[j]) arr3[k++] = arr1[i++]; else arr3[k++] = arr2[j++]; } // Store remaining elements of first array while (i < n1) arr3[k++] = arr1[i++]; // Store remaining elements of second array while (j < n2) arr3[k++] = arr2[j++]; } // A utility function to print array elements void printArray( int arr[], int size) { for ( int i=0; i < size; i++) cout << arr[i] << " " ; } // This function takes an array of arrays as an argument and // All arrays are assumed to be sorted. It merges them together // and prints the final sorted output. void mergeKArrays( int arr[][n], int i, int j, int output[]) { //if one array is in range if (i==j) { for ( int p=0; p < n; p++) output[p]=arr[i][p]; return ; } //if only two arrays are left them merge them if (j-i==1) { mergeArrays(arr[i],arr[j],n,n,output); return ; } //output arrays int out1[n*(((i+j)/2)-i+1)],out2[n*(j-((i+j)/2))]; //divide the array into halves mergeKArrays(arr,i,(i+j)/2,out1); mergeKArrays(arr,(i+j)/2+1,j,out2); //merge the output array mergeArrays(out1,out2,n*(((i+j)/2)-i+1),n*(j-((i+j)/2)),output); } // Driver program to test above functions int main() { // Change n at the top to change number of elements // in an array int arr[][n] = {{2, 6, 12, 34}, {1, 9, 20, 1000}, {23, 34, 90, 2000}}; int k = sizeof (arr)/ sizeof (arr[0]); int output[n*k]; mergeKArrays(arr,0,2, output); cout << "Merged array is " << endl; printArray(output, n*k); return 0; } |
JAVA
// Java program to merge k sorted arrays of size n each. import java.util.*; class GFG{ static final int n = 4 ; // Merge arr1[0..n1-1] and arr2[0..n2-1] into // arr3[0..n1+n2-1] static void mergeArrays( int arr1[], int arr2[], int n1, int n2, int arr3[]) { int i = 0 , j = 0 , k = 0 ; // Traverse both array while (i<n1 && j <n2) { // Check if current element of first // array is smaller than current element // of second array. If yes, store first // array element and increment first array // index. Otherwise do same with second array if (arr1[i] < arr2[j]) arr3[k++] = arr1[i++]; else arr3[k++] = arr2[j++]; } // Store remaining elements of first array while (i < n1) arr3[k++] = arr1[i++]; // Store remaining elements of second array while (j < n2) arr3[k++] = arr2[j++]; } // A utility function to print array elements static void printArray( int arr[], int size) { for ( int i = 0 ; i < size; i++) System.out.print(arr[i]+ " " ); } // This function takes an array of arrays as an argument and // All arrays are assumed to be sorted. It merges them together // and prints the final sorted output. static void mergeKArrays( int arr[][], int i, int j, int output[]) { // if one array is in range if (i == j) { for ( int p = 0 ; p < n; p++) output[p] = arr[i][p]; return ; } //if only two arrays are left them merge them if (j - i == 1 ) { mergeArrays(arr[i], arr[j], n, n, output); return ; } //output arrays int []out1 = new int [n*(((i + j) / 2 ) - i + 1 )]; int []out2 = new int [n*(j - ((i + j) / 2 ))]; //divide the array into halves mergeKArrays(arr, i, (i + j) / 2 , out1); mergeKArrays(arr, (i + j) / 2 + 1 , j, out2); //merge the output array mergeArrays(out1, out2, n * (((i + j) / 2 ) - i + 1 ), n * (j - ((i + j) / 2 )), output); } // Driver program to test above functions public static void main(String[] args) { // Change n at the top to change number of elements // in an array int arr[][] = {{ 2 , 6 , 12 , 34 }, { 1 , 9 , 20 , 1000 }, { 23 , 34 , 90 , 2000 }}; int k = arr.length; int []output = new int [n*k]; mergeKArrays(arr, 0 , 2 , output); System.out.print( "Merged array is " + "" ); printArray(output, n*k); } } // This code is contributed by gauravrajput1 |
C#
// C# program to merge k sorted arrays of size n each. using System; class GFG{ static readonly int n = 4; public static int [] GetRow( int [,] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int [rowLength]; for ( var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i]; return rowVector; } // Merge arr1[0..n1-1] and arr2[0..n2-1] into // arr3[0..n1+n2-1] static void mergeArrays( int []arr1, int []arr2, int n1, int n2, int []arr3) { int i = 0, j = 0, k = 0; // Traverse both array while (i < n1 && j < n2) { // Check if current element of first // array is smaller than current element // of second array. If yes, store first // array element and increment first array // index. Otherwise do same with second array if (arr1[i] < arr2[j]) arr3[k++] = arr1[i++]; else arr3[k++] = arr2[j++]; } // Store remaining elements of first array while (i < n1) arr3[k++] = arr1[i++]; // Store remaining elements of second array while (j < n2) arr3[k++] = arr2[j++]; } // A utility function to print array elements static void printArray( int []arr, int size) { for ( int i = 0; i < size; i++) Console.Write(arr[i] + " " ); } // This function takes an array of arrays as an // argument and All arrays are assumed to be // sorted. It merges them together and prints // the readonly sorted output. static void mergeKArrays( int [,]arr, int i, int j, int []output) { // If one array is in range if (i == j) { for ( int p = 0; p < n; p++) output[p] = arr[i, p]; return ; } // If only two arrays are left them merge them if (j - i == 1) { mergeArrays(GetRow(arr, i), GetRow(arr, j), n, n, output); return ; } // Output arrays int []out1 = new int [n*(((i + j) / 2) - i + 1)]; int []out2 = new int [n*(j - ((i + j) / 2))]; // Divide the array into halves mergeKArrays(arr, i, (i + j) / 2, out1); mergeKArrays(arr, (i + j) / 2 + 1, j, out2); // Merge the output array mergeArrays(out1, out2, n * (((i + j) / 2) - i + 1), n * (j - ((i + j) / 2)), output); } // Driver code public static void Main(String[] args) { // Change n at the top to change number of elements // in an array int [,]arr = { { 2, 6, 12, 34 }, { 1, 9, 20, 1000 }, { 23, 34, 90, 2000 } }; int k = arr.GetLength(0); int []output = new int [n * k]; mergeKArrays(arr, 0, 2, output); Console.Write( "Merged array is " + "" ); printArray(output, n * k); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to merge k // sorted arrays of size n each. let n = 4 // Merge arr1[0..n1-1] and arr2[0..n2-1] into // arr3[0..n1+n2-1] function mergeArrays(arr1, arr2, n1, n2, arr3) { let i = 0, j = 0, k = 0; // Traverse both array while (i < n1 && j < n2) { // Check if current element of first // array is smaller than current element // of second array. If yes, store first // array element and increment first array // index. Otherwise do same with second array if (arr1[i] < arr2[j]) arr3[k++] = arr1[i++]; else arr3[k++] = arr2[j++]; } // Store remaining elements of first array while (i < n1) arr3[k++] = arr1[i++]; // Store remaining elements of second array while (j < n2) arr3[k++] = arr2[j++]; } // A utility function to print array elements function printArray(arr, size) { for (let i = 0; i < size; i++) document.write(arr[i] + " " ); } // This function takes an array of arrays // as an argument and all arrays are assumed // to be sorted. It merges them together // and prints the final sorted output. function mergeKArrays(arr, i, j, output) { // If one array is in range if (i == j) { for (let p = 0; p < n; p++) output[p] = arr[i][p]; return ; } // If only two arrays are left // them merge them if (j - i == 1) { mergeArrays(arr[i], arr[j], n, n, output); return ; } // Output arrays let out1 = new Array(n * (((i + j) / 2) - i + 1)) let out2 = new Array(n * (j - ((i + j) / 2))); // Divide the array into halves mergeKArrays(arr, i, (i + j) / 2, out1); mergeKArrays(arr, (i + j) / 2 + 1, j, out2); // Merge the output array mergeArrays(out1, out2, n * (((i + j) / 2) - i + 1), n * (j - ((i + j) / 2)), output); } // Driver code // Change n at the top to change number // of elements in an array let arr = [ [ 2, 6, 12, 34 ], [ 1, 9, 20, 1000 ], [ 23, 34, 90, 2000 ] ]; let k = arr.length; let output = new Array(n * k); mergeKArrays(arr, 0, 2, output); document.write( "Merged array is " + "<br>" ); printArray(output, n * k); // This code is contributed by Mayank Tyagi </script> |
输出：
Merged array is 1 2 6 9 12 20 23 34 34 90 1000 2000
复杂性分析：
- 时间复杂性： O（n*k*logk）。 日志有k个级别，因为在每个级别中，k个数组被分成两半，在每个级别上，k个数组被遍历。所以时间复杂度是O（n*k）。
- 空间复杂性： O（n*k*logk）。 在每个级别中都需要O（n*k）空间，因此空间复杂度为O（n*k*logk）。
其他有效方法： 这个想法是使用 最小堆 .这种基于MinHeap的解决方案具有与O（NK log K）相同的时间复杂度。但是为了一个 不同大小的阵列 ，此解决方案效果更好。这个过程必须从创建一个MinHeap并插入所有k数组的第一个元素开始。移除Minheap的根元素并将其放入输出数组，然后从移除的元素数组中插入下一个元素。要获得结果，该步骤必须继续，直到MinHeap中没有剩余的元素。
MinHeap： 最小堆是一个完整的二叉树，其中每个内部节点中的值小于或等于该节点的子节点中的值。将堆的元素映射到数组是很简单的：如果一个节点存储在索引k中，那么它的左子节点存储在索引2k+1中，右子节点存储在索引2k+2中。
- 算法：
- 创建一个最小堆并插入所有k数组的第一个元素。
- 运行循环，直到MinHeap的大小大于零。
- 移除MinHeap的顶部元素并打印该元素。
- 现在，从移除的元素所属的同一数组中插入下一个元素。
- 如果数组没有更多的元素，那么将root替换为infinite。更换根后，将树重新固定。
实施：
C++
// C++ program to merge k sorted // arrays of size n each. #include<bits/stdc++.h> using namespace std; #define n 4 // A min-heap node struct MinHeapNode { // The element to be stored int element; // index of the array from which the element is taken int i; // index of the next element to be picked from the array int j; }; // Prototype of a utility function to swap two min-heap nodes void swap(MinHeapNode *x, MinHeapNode *y); // A class for Min Heap class MinHeap { // pointer to array of elements in heap MinHeapNode *harr; // size of min heap int heap_size; public : // Constructor: creates a min heap of given size MinHeap(MinHeapNode a[], int size); // to heapify a subtree with root at given index void MinHeapify( int ); // to get index of left child of node at index i int left( int i) { return (2*i + 1); } // to get index of right child of node at index i int right( int i) { return (2*i + 2); } // to get the root MinHeapNode getMin() { return harr[0]; } // to replace root with new node x and heapify() new root void replaceMin(MinHeapNode x) { harr[0] = x; MinHeapify(0); } }; // This function takes an array of arrays as an argument and // All arrays are assumed to be sorted. It merges them together // and prints the final sorted output. int *mergeKArrays( int arr[][n], int k) { // To store output array int *output = new int [n*k]; // Create a min heap with k heap nodes. // Every heap node has first element of an array MinHeapNode *harr = new MinHeapNode[k]; for ( int i = 0; i < k; i++) { // Store the first element harr[i].element = arr[i][0]; // index of array harr[i].i = i; // Index of next element to be stored from the array harr[i].j = 1; } // Create the heap MinHeap hp(harr, k); // Now one by one get the minimum element from min // heap and replace it with next element of its array for ( int count = 0; count < n*k; count++) { // Get the minimum element and store it in output MinHeapNode root = hp.getMin(); output[count] = root.element; // Find the next element that will replace current // root of heap. The next element belongs to same // array as the current root. if (root.j < n) { root.element = arr[root.i][root.j]; root.j += 1; } // If root was the last element of its array // INT_MAX is for infinite else root.element = INT_MAX; // Replace root with next element of array hp.replaceMin(root); } return output; } // FOLLOWING ARE IMPLEMENTATIONS OF // STANDARD MIN HEAP METHODS FROM CORMEN BOOK // Constructor: Builds a heap from a given // array a[] of given size MinHeap::MinHeap(MinHeapNode a[], int size) { heap_size = size; harr = a; // store address of array int i = (heap_size - 1)/2; while (i >= 0) { MinHeapify(i); i--; } } // A recursive method to heapify a // subtree with root at given index. // This method assumes that the subtrees // are already heapified void MinHeap::MinHeapify( int i) { int l = left(i); int r = right(i); int smallest = i; if (l < heap_size && harr[l].element < harr[i].element) smallest = l; if (r < heap_size && harr[r].element < harr[smallest].element) smallest = r; if (smallest != i) { swap(&harr[i], &harr[smallest]); MinHeapify(smallest); } } // A utility function to swap two elements void swap(MinHeapNode *x, MinHeapNode *y) { MinHeapNode temp = *x; *x = *y; *y = temp; } // A utility function to print array elements void printArray( int arr[], int size) { for ( int i=0; i < size; i++) cout << arr[i] << " " ; } // Driver program to test above functions int main() { // Change n at the top to change number of elements // in an array int arr[][n] = {{2, 6, 12, 34}, {1, 9, 20, 1000}, {23, 34, 90, 2000}}; int k = sizeof (arr)/ sizeof (arr[0]); int *output = mergeKArrays(arr, k); cout << "Merged array is " << endl; printArray(output, n*k); return 0; } |
JAVA
// Java program to merge k sorted // arrays of size n each. // A min heap node class MinHeapNode { int element; // The element to be stored // index of the array from // which the element is taken int i; // index of the next element // to be picked from array int j; public MinHeapNode( int element, int i, int j) { this .element = element; this .i = i; this .j = j; } }; // A class for Min Heap class MinHeap { MinHeapNode[] harr; // Array of elements in heap int heap_size; // Current number of elements in min heap // Constructor: Builds a heap from // a given array a[] of given size public MinHeap(MinHeapNode a[], int size) { heap_size = size; harr = a; int i = (heap_size - 1 )/ 2 ; while (i >= 0 ) { MinHeapify(i); i--; } } // A recursive method to heapify a subtree // with the root at given index This method // assumes that the subtrees are already heapified void MinHeapify( int i) { int l = left(i); int r = right(i); int smallest = i; if (l < heap_size && harr[l].element < harr[i].element) smallest = l; if (r < heap_size && harr[r].element < harr[smallest].element) smallest = r; if (smallest != i) { swap(harr, i, smallest); MinHeapify(smallest); } } // to get index of left child of node at index i int left( int i) { return ( 2 *i + 1 ); } // to get index of right child of node at index i int right( int i) { return ( 2 *i + 2 ); } // to get the root MinHeapNode getMin() { if (heap_size <= 0 ) { System.out.println( "Heap underflow" ); return null ; } return harr[ 0 ]; } // to replace root with new node // "root" and heapify() new root void replaceMin(MinHeapNode root) { harr[ 0 ] = root; MinHeapify( 0 ); } // A utility function to swap two min heap nodes void swap(MinHeapNode[] arr, int i, int j) { MinHeapNode temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // A utility function to print array elements static void printArray( int [] arr) { for ( int i : arr) System.out.print(i + " " ); System.out.println(); } // This function takes an array of // arrays as an argument and All // arrays are assumed to be sorted. // It merges them together and // prints the final sorted output. static void mergeKSortedArrays( int [][] arr, int k) { MinHeapNode[] hArr = new MinHeapNode[k]; int resultSize = 0 ; for ( int i = 0 ; i < arr.length; i++) { MinHeapNode node = new MinHeapNode(arr[i][ 0 ],i, 1 ); hArr[i] = node; resultSize += arr[i].length; } // Create a min heap with k heap nodes. Every heap node // has first element of an array MinHeap mh = new MinHeap(hArr, k); int [] result = new int [resultSize]; // To store output array // Now one by one get the minimum element from min // heap and replace it with next element of its array for ( int i = 0 ; i < resultSize; i++) { // Get the minimum element and store it in result MinHeapNode root = mh.getMin(); result[i] = root.element; // Find the next element that will replace current // root of heap. The next element belongs to same // array as the current root. if (root.j < arr[root.i].length) root.element = arr[root.i][root.j++]; // If root was the last element of its array else root.element = Integer.MAX_VALUE; // Replace root with next element of array mh.replaceMin(root); } printArray(result); } // Driver code public static void main(String args[]){ int [][] arr= {{ 2 , 6 , 12 , 34 }, { 1 , 9 , 20 , 1000 }, { 23 , 34 , 90 , 2000 }}; System.out.println( "Merged array is :" ); mergeKSortedArrays(arr,arr.length); } }; // This code is contributed by shubham96301 |
C#
// C# program to merge k sorted // arrays of size n each. using System; // A min heap node public class MinHeapNode { public int element; // The element to be stored // index of the array from // which the element is taken public int i; // index of the next element // to be picked from array public int j; public MinHeapNode( int element, int i, int j) { this .element = element; this .i = i; this .j = j; } }; // A class for Min Heap public class MinHeap { MinHeapNode[] harr; // Array of elements in heap int heap_size; // Current number of elements in min heap // Constructor: Builds a heap from // a given array a[] of given size public MinHeap(MinHeapNode []a, int size) { heap_size = size; harr = a; int i = (heap_size - 1) / 2; while (i >= 0) { MinHeapify(i); i--; } } // A recursive method to heapify a subtree // with the root at given index This method // assumes that the subtrees are already heapified void MinHeapify( int i) { int l = left(i); int r = right(i); int smallest = i; if (l < heap_size && harr[l].element < harr[i].element) smallest = l; if (r < heap_size && harr[r].element < harr[smallest].element) smallest = r; if (smallest != i) { swap(harr, i, smallest); MinHeapify(smallest); } } // to get index of left child of node at index i int left( int i) { return (2 * i + 1); } // to get index of right child of node at index i int right( int i) { return (2 * i + 2); } // to get the root MinHeapNode getMin() { if (heap_size <= 0) { Console.WriteLine( "Heap underflow" ); return null ; } return harr[0]; } // to replace root with new node // "root" and heapify() new root void replaceMin(MinHeapNode root) { harr[0] = root; MinHeapify(0); } // A utility function to swap two min heap nodes void swap(MinHeapNode[] arr, int i, int j) { MinHeapNode temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // A utility function to print array elements static void printArray( int [] arr) { foreach ( int i in arr) Console.Write(i + " " ); Console.WriteLine(); } // This function takes an array of // arrays as an argument and All // arrays are assumed to be sorted. // It merges them together and // prints the final sorted output. static void mergeKSortedArrays( int [,] arr, int k) { MinHeapNode[] hArr = new MinHeapNode[k]; int resultSize = 0; for ( int i = 0; i < arr.GetLength(0); i++) { MinHeapNode node = new MinHeapNode(arr[i, 0], i, 1); hArr[i] = node; resultSize += arr.GetLength(1); } // Create a min heap with k heap nodes. // Every heap node has first element of an array MinHeap mh = new MinHeap(hArr, k); int [] result = new int [resultSize]; // To store output array // Now one by one get the minimum element // from min heap and replace it with // next element of its array for ( int i = 0; i < resultSize; i++) { // Get the minimum element and // store it in result MinHeapNode root = mh.getMin(); result[i] = root.element; // Find the next element that will // replace current root of heap. // The next element belongs to same // array as the current root. if (root.j < arr.GetLength(1)) root.element = arr[root.i,root.j++]; // If root was the last element of its array else root.element = int .MaxValue; // Replace root with next element of array mh.replaceMin(root); } printArray(result); } // Driver code public static void Main(String []args) { int [,] arr = {{2, 6, 12, 34}, {1, 9, 20, 1000}, {23, 34, 90, 2000}}; Console.WriteLine( "Merged array is :" ); mergeKSortedArrays(arr, arr.GetLength(0)); } }; // This code is contributed by 29AjayKumar |
输出：
Merged array is 1 2 6 9 12 20 23 34 34 90 1000 2000
复杂性分析：
- 时间复杂性： O（n*k*logk），在最小堆中插入和删除需要logk时间。所以总的时间复杂度是O（n*k*logk）
- 空间复杂性： O（k），如果未存储输出，则所需的唯一空间是k个元素的最小堆。所以空间复杂度是O（k）。
合并k个排序数组|集合2（不同大小的数组） 幸亏 维涅什 感谢您提出这个问题和初步解决方案。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
