Introduction
Given k sorted arrays of size n each, merge them and print the sorted output.
Input:
k = 3, n = 4
arr[][] = {
{1, 3, 5, 7},
{2, 4, 6, 8},
{0, 9, 10, 11}
} ;
Output: 0 1 2 3 4 5 6 7 8 9 10 11
Explanation: The output array is a sorted array that contains all the elements of the input matrix.Approach
We think of the Merge operation in the Merge Sort to merge two sorted arrays into one. We can optimize this approach by merging in the pair and merge till it converges to a single array.
We can also use the Min Heap method to sort batches of k elements repeating n times. This will reduce the Space complexity to O(k)
The below problem approach might consists of minor coding issues that are resolved in the implementation in the end.
The below implementation consists of a Min Heap implementation.
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
internal class MergeKSortedArrays
{
public static void Run()
{
var input = new[]
{
new[] {1, 3, 5, 7},
new[] {2, 4, 6, 8},
new[] {0, 9, 10, 11}
};
var res = Merge(input);
foreach (var item in res)
{
Console.Write(item + " ");
}
Console.WriteLine();
}
private static int[] Merge(int[][] input)
{
var k = input.Length;
var mh = new MinHeap<MinHeapNode>(k);
var res = new List<int>();
// Initialize
var firstIndex = 0;
for (var j = 0; j < k; j++)
{
var n = input[j].Length;
if (firstIndex >= n)
{
continue;
}
mh.Enqueue(new MinHeapNode
{
Val = input[j][firstIndex],
KIndex = j,
NextNIndex = firstIndex + 1
});
}
while (mh.Count > 0)
{
var node = mh.Dequeue();
res.Add(node.Val);
if (node.NextNIndex >= input[node.KIndex].Length)
{
continue;
}
node.Val = input[node.KIndex][node.NextNIndex++];
mh.Enqueue(node);
}
return res.ToArray();
}
}
internal class MinHeapNode : IComparable<MinHeapNode>
{
public int Val { get; set; }
public int KIndex { get; set; }
public int NextNIndex { get; set; }
public int CompareTo(MinHeapNode other)
{
if (ReferenceEquals(this, other)) return 0;
if (ReferenceEquals(null, other)) return 1;
return Val.CompareTo(other.Val);
}
}
internal class MinHeap<T> where T : IComparable<T>
{
private readonly T[] _nodes;
public MinHeap(int k)
{
_nodes = new T[k];
Count = 0;
}
public int Count { get; private set; }
public void Enqueue(T node)
{
if (Count >= _nodes.Length)
{
throw new OverflowException($"Heap is full: {Count}");
}
_nodes[Count++] = node;
BubbleUp(Count - 1);
}
public T Dequeue()
{
if (Count <= 0)
{
throw new IndexOutOfRangeException($"Heap is empty : {Count}");
}
var index = 0;
var front = _nodes[index];
_nodes[index] = _nodes[--Count];
TrickleDown(index);
return front;
}
private void TrickleDown(int index)
{
var childIndex = GetLesserChildIndex(index);
while (index <= _nodes.Length - 1 && childIndex > -1 && childIndex < Count && _nodes[index].CompareTo(_nodes[childIndex]) > -1)
{
Swap(index, childIndex);
index = childIndex;
childIndex = GetLesserChildIndex(index);
}
}
private int GetLesserChildIndex(in int index)
{
var childIndex = GetChildIndex(index);
if (childIndex == -1 || childIndex >= _nodes.Length - 1)
{
return -1;
}
return _nodes[childIndex + 1].CompareTo(_nodes[childIndex]) < 0
? childIndex + 1
: childIndex;
}
private int GetChildIndex(in int index)
{
if (index >= _nodes.Length - 1)
{
return -1;
}
return index * 2 + 1;
}
private void BubbleUp(int index)
{
var parentIndex = GetParent(index);
while (parentIndex > -1 && index > 0 && _nodes[parentIndex].CompareTo(_nodes[index]) > 0)
{
Swap(parentIndex, index);
index = parentIndex;
parentIndex = GetParent(index);
}
}
private void Swap(in int parentIndex, in int index)
{
var temp = _nodes[index];
_nodes[index] = _nodes[parentIndex];
_nodes[parentIndex] = temp;
}
private int GetParent(in int index)
{
if (index == 0)
{
return -1;
}
return (index - 1) / 2;
}
}
}