k sortierte Arrays zusammenführen | Set 1
Bei gegebenen k sortierten Arrays der Größe n füge sie zusammen und drucke die sortierte Ausgabe.
Beispiel:
Eingabe:
k = 3, n = 4
arr[][] = { {1, 3, 5, 7},
{2, 4, 6, 8},
{0, 9, 10, 11}} ;
Ausgabe: 0 1 2 3 4 5 6 7 8 9 10 11
Erläuterung: Das Ausgabearray ist ein sortiertes Array, das alle Elemente der Eingabematrix enthält.Eingabe:
k = 4, n = 4
arr[][] = { {1, 5, 6, 8},
{2, 4, 10, 12},
{3, 7, 9, 11},
{13, 14 , 15, 16}} ;
Ausgabe: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Erläuterung: Das Ausgabearray ist ein sortiertes Array, das alle Elemente der Eingabematrix enthält.
Naiver Ansatz : Die sehr naive Methode besteht darin, ein Ausgabearray der Größe n * k zu erstellen und dann alle Elemente in das Ausgabearray zu kopieren, gefolgt von einer Sortierung.
- Algorithmus:
- Erstellen Sie ein Ausgabearray der Größe n * k.
- Durchlaufen Sie die Matrix von Anfang bis Ende und fügen Sie alle Elemente in das Ausgabearray ein.
- Sortieren und drucken Sie das Ausgabearray.
- Implementierung:
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[c++]=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[c++] = 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);
}
}
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[c++] = 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[c++] = arr[i][j];
}
// sort the array
output.sort((a,b)=>a-b);
}
// A utility function to prvar 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>
Ausgabe:
Zusammengeführtes Array ist 1 2 6 9 12 20 23 34 34 90 1000 2000
- Komplexitätsanalyse:
- Zeitkomplexität: O(n*k*log(n*k)).
da das resultierende Array eine Größe von N * k hat. - Raumkomplexität: O(n*k), Das Ausgabearray hat die Größe n*k.
- Zeitkomplexität: O(n*k*log(n*k)).
Effizienter Ansatz Der Prozess kann mit dem Zusammenführen von Arrays in Zweiergruppen beginnen. Nach der ersten Zusammenführung haben wir k/2 Arrays. Arrays wieder in Gruppen zusammenführen, jetzt haben wir k/4 Arrays. Dies ähnelt der Zusammenführungssortierung. Teile k Arrays in zwei Hälften, die eine gleiche Anzahl von Arrays enthalten, bis es zwei Arrays in einer Gruppe gibt. Anschließend werden die Arrays von unten nach oben zusammengeführt.
- Algorithmus:
- Erstellen Sie eine rekursive Funktion, die k Arrays übernimmt und das Ausgabearray zurückgibt.
- Wenn in der rekursiven Funktion der Wert von k 1 ist, geben Sie das Array zurück, andernfalls, wenn der Wert von k 2 ist, führen Sie die beiden Arrays in linearer Zeit zusammen und geben Sie das Array zurück.
- Wenn der Wert von k größer als 2 ist, teilen Sie die Gruppe von k Elementen in zwei gleiche Hälften und rufen Sie die Funktion rekursiv auf, dh 0 bis k/2 Array in einer rekursiven Funktion und k/2 bis k Array in einer anderen rekursiven Funktion.
- Drucken Sie das Ausgabearray.
- Implementierung:
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 " +"\n");
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 " + "\n");
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>
Ausgabe:
Zusammengeführtes Array ist 1 2 6 9 12 20 23 34 34 90 1000 2000
Komplexitätsanalyse:
- Zeitkomplexität: O( n * k * log k).
Es gibt log k Ebenen, da in jeder Ebene die k Arrays halbiert werden und auf jeder Ebene die k Arrays durchlaufen werden. Die Zeitkomplexität ist also O( n * k ). - Raumkomplexität: O( n * k * log k).
In jeder Ebene wird O( n*k ) Raum benötigt, also ist die Raumkomplexität O( n * k * log k).
Alternativer effizienter Ansatz: Die Idee ist, Min Heap zu verwenden . Diese auf MinHeap basierende Lösung hat die gleiche Zeitkomplexität, die O(NK log K) ist. Aber für ein anderes und besonders großes Array funktioniert diese Lösung viel besser. Der Prozess muss mit dem Erstellen eines MinHeap und dem Einfügen des ersten Elements aller k Arrays beginnen. Entfernen Sie das Wurzelelement von Minheap und fügen Sie es in das Ausgabearray ein und fügen Sie das nächste Element aus dem Array des entfernten Elements ein. Um das Ergebnis zu erhalten, muss der Schritt fortgesetzt werden, bis kein Element mehr im MinHeap vorhanden ist.
MinHeap: Ein Min-Heap ist ein vollständiger Binärbaum, in dem der Wert in jedem internen Node kleiner oder gleich den Werten in den Kindern dieses Nodes ist. Die Elemente eines Heaps in ein Array abzubilden ist trivial: Wenn ein Node am Index k gespeichert ist, dann wird sein linkes Kind an Index 2k + 1 und sein rechtes Kind an Index 2k + 2 gespeichert.
- Algorithmus:
- Erstellen Sie einen min Heap und fügen Sie das erste Element aller k Arrays ein.
- Führen Sie eine Schleife aus, bis die Größe von MinHeap größer als Null ist.
- Entfernen Sie das oberste Element des MinHeap und drucken Sie das Element.
- Fügen Sie nun das nächste Element aus demselben Array ein, in das das entfernte Element gehörte.
- Wenn das Array keine weiteren Elemente enthält, ersetzen Sie root durch infinite. Nachdem Sie die Wurzel ersetzt haben, häufen Sie den Baum an.
Implementierung:
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 elelement 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
Ausgabe:
Zusammengeführtes Array ist 1 2 6 9 12 20 23 34 34 90 1000 2000
Komplexitätsanalyse:
- Zeitkomplexität: O(n * k * log k), das Einfügen und Löschen in einem Min Heap erfordert log k Zeit. Die Gesamtzeitkomplexität ist also O ( n * k * log k)
- Platzkomplexität: O(k), wenn die Ausgabe nicht gespeichert wird, dann ist der einzige benötigte Platz der Min-Heap von k Elementen. Die Raumkomplexität ist also O(k).
k sortierte Arrays zusammenführen | Set 2 (Arrays unterschiedlicher Größe)
Vielen Dank an Vignesh für den Vorschlag dieses Problems und der ersten Lösung. Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben diskutierten Thema teilen möchten
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .