https://leetcode.com/problems/merge-k-sorted-lists/
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
using System.Collections.Generic;
using Heap;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace LinkedListQuestions
{/// <summary>
/// https://leetcode.com/problems/merge-k-sorted-lists/
/// </summary>
[TestClass]
public class MergeKSortedLists
{
[TestMethod]
public void LeetCodeExample()
{
ListNode l1 = new ListNode(1);
l1.next = new ListNode(4);
l1.next.next = new ListNode(5);
ListNode l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);
ListNode l3 = new ListNode(2);
l3.next = new ListNode(6);
ListNode[] arr = new ListNode[] { l1, l2, l3 };
ListNode res = MergeKSortedListsTest.MergeKLists(arr);
}
}
public class MergeKSortedListsTest
{
public static ListNode MergeKLists(ListNode[] lists)
{
if (lists == null || lists.Length == 0)
{
return null;
}
MinHeap<ListNode> heap = new MinHeap<ListNode>(new ListNodeComparer());
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
foreach (ListNode node in lists)
{
if (node != null)
{
heap.Add(node);
}
}
while (heap.Count > 0)
{
tail.next = heap.ExtractDominating();
tail = tail.next;
if (tail.next != null)
{
heap.Add(tail.next);
}
}
return dummy.next;
}
public class ListNodeComparer : Comparer<ListNode>
{
public override int Compare(ListNode o1, ListNode o2)
{
if (o1.val < o2.val)
return -1;
else if (o1.val == o2.val)
return 0;
else
return 1;
}
}
}
}
you do not need to review the MinHeap code!
public abstract class Heap<T> : IEnumerable<T>
{
//capacity of the Queue
private const int InitialCapacity = 0;
private int _capacity = InitialCapacity;
//items in the queue
private T[] _heap = new T[InitialCapacity];
//last item in the queue
private int _tail = 0;
//when growing the queue you multiply by Growfactor
private const int GrowFactor = 2;
// if the min size is 0 you grow the queue size by at least Min grow
private const int MinGrow = 1;
//how to compare the keys
protected Comparer<T> Comparer { get; private set; }
//store how many Items are in the queue
public int Count { get { return _tail; } }
//shows the current capacity of the queue
public int Capacity { get { return _capacity; } }
//this function is used in BubbleUp and in GetDominating
protected abstract bool Dominates(T x, T y);
protected Heap() : this(Comparer<T>.Default)
{
}
protected Heap(Comparer<T> comparer) : this(Enumerable.Empty<T>(), comparer)
{
}
protected Heap(IEnumerable<T> collection) : this(collection, Comparer<T>.Default)
{
}
protected Heap(IEnumerable<T> collection, Comparer<T> comparer)
{
if (collection == null)
{
throw new ArgumentNullException("collection");
}
if (comparer == null)
{
throw new ArgumentNullException("comparer");
}
Comparer = comparer;
foreach (var item in collection)
{
if (Count > Capacity)
{
Grow();
}
_heap[_tail++] = item;
}
for (int i = 0; i < Parent(_tail - 1); i++)
{
BubbleDown(i);
}
}
public void Add(T item)
{
if (Count == Capacity)
{
Grow();
}
_heap[_tail++] = item;
BubbleUp(_tail - 1);
}
//when adding a new item we bubble the item from tail-1 up to its'
//correct position
private void BubbleUp(int i)
{
if (i == 0 || Dominates(_heap[Parent(i)], _heap[i]))
{
return; //correct domination (or root)
}
Swap(i, Parent(i));
BubbleUp(Parent(i));
}
// when adding new items into the queue from the CTOR
// we bubble them down
private void BubbleDown(int i)
{
int dominatingNode = Dominating(i);
if (dominatingNode == i)
{
return;
}
Swap(i,dominatingNode);
BubbleDown(dominatingNode);
}
public T GetMin()
{
if (Count == 0)
{
throw new InvalidOperationException("Heap is empty");
}
return _heap[0];
}
private void Swap(int i, int j)
{
T tmp = _heap[i];
_heap[i] = _heap[j];
_heap[j] = tmp;
}
public static int Parent(int i)
{
return (i + 1) / 2 - 1;
}
private void Grow()
{
int newCapcity = _capacity * GrowFactor + MinGrow;
var newHeap = new T[newCapcity];
Array.Copy(_heap, newHeap, _capacity);
_heap = newHeap;
_capacity = newCapcity;
}
//return from 0 up to Count
public IEnumerator<T> GetEnumerator()
{
return _heap.Take(Count).GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
//when we bubble down, when building the queue from a list in the CTOR
// we need to understand who is dominating i, and we swap them,
// and call bubbleDown again
private int Dominating(int i)
{
int dominatingNode = i;
dominatingNode = GetDominating(YoungChild(i), dominatingNode);
dominatingNode = GetDominating(OldChild(i), dominatingNode);
return dominatingNode;
}
private int GetDominating(int newNode, int dominatingNode)
{
if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode]))
{
return newNode;
}
else
{
return dominatingNode;
}
}
private static int YoungChild(int i)
{
return 2 * (i + 1) - 1;
}
private static int OldChild(int i)
{
return YoungChild(i) + 1;
}
public T ExtractDominating()
{
if (Count == 0) throw new InvalidOperationException("Heap is empty");
T ret = _heap[0];
_tail--;
Swap(_tail, 0);
BubbleDown(0);
return ret;
}
}
public class MinHeap<T> : Heap<T>
{
public MinHeap()
: this(Comparer<T>.Default)
{
}
public MinHeap(Comparer<T> comparer)
: base(comparer)
{
}
public MinHeap(IEnumerable<T> collection) : base(collection)
{
}
public MinHeap(IEnumerable<T> collection, Comparer<T> comparer)
: base(collection, comparer)
{
}
protected override bool Dominates(T x, T y)
{
return Comparer.Compare(x, y) <= 0;
}
}
