Dadas k arrays ordenadas de tamaño n cada una, combínelas e imprima la salida ordenada.
Ejemplo:
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>
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
Python3
# Python program to merge k
# sorted arrays of size n each.
n = 4
# Merge arr1[0..n1-1] and arr2[0..n2-1] into
# arr3[0..n1+n2-1]
def mergeArrays(arr1, arr2, n1, n2, arr3):
i, j, k = 0, 0, 0
# Traverse both array
while (i < n1 and 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]
k += 1
i += 1
else:
arr3[k] = arr2[j]
k += 1
j += 1
# Store remaining elements of first array
while (i < n1):
arr3[k] = arr1[i]
k += 1
i += 1
# Store remaining elements of second array
while (j < n2):
arr3[k] = arr2[j]
k += 1
j += 1
# A utility function to print array elements
def printArray(arr, size):
for i in range(size):
print(arr[i],end = " ")
# 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, i, j, output):
global n
# If one array is in range
if (i == j):
for p in range(n):
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
out1 = [0 for i in range(n * (((i + j) // 2) - i + 1))]
out2 = [0 for i in range(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
arr = [ [ 2, 6, 12, 34 ],
[ 1, 9, 20, 1000 ],
[ 23, 34, 90, 2000 ] ]
k = len(arr)
output = [0 for i in range(n * k)]
mergeKArrays(arr, 0, 2, output)
print("Merged array is ")
printArray(output, n * k)
# This code is contributed by shinjanpatra
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>
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
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA