Full Solution to Merge K Sorted Linked Lists in C# with MinHeap<T> and ListNode implementation

gistfile1.txt

/*

Full solution to Merge K Sorted Lists with custom MinHeap<T> and ListNode classes implemented.

*/

using System;
using System.Collections;
using System.Collections.Generic;

class Solution
{
    static void Main(string[] args)
    {
        
        ListNode l1 = new ListNode(2);
        l1.Next = new ListNode(6);
        l1.Next.Next = new ListNode(8);

        ListNode l2 = new ListNode(3);
        l2.Next = new ListNode(6);
        l2.Next.Next = new ListNode(7);

        ListNode l3 = new ListNode(1);
        l3.Next = new ListNode(3);
        l3.Next.Next = new ListNode(4);
        
        ListNode[] example = new ListNode[] {l1, l2, l3 };
        ListNode result = MergeLinkedLists(example);
        
        Console.WriteLine("Here are the elements from the merged list: ");
        
        while (result != null)
        {
            Console.WriteLine(result.Value + " ");
            result = result.Next;
        }
        
    }
    
    public static ListNode MergeLinkedLists(ListNode[] lists)
    {
        MinHeap<ListNode> nodeHeap = new MinHeap<ListNode>();

        // put the root of each list in the min heap
        foreach (ListNode root in lists)
        {
            if (root != null)
            {
                nodeHeap.Push(root);
            }

        }

        // take the smallest (top) element from the min-heap and add it to the result; 
        // if the top element has a next element add it to the heap
        ListNode resultHead = null;
        ListNode resultTail = null;
        
        while (!nodeHeap.IsEmpty())
        {
            ListNode node = nodeHeap.Pop();
            if (resultHead == null)
            {
                resultHead = resultTail = node;
            }

            else
            {
                resultTail.Next = node;
                resultTail = resultTail.Next;
            }

            if (node.Next != null)
            {
                  nodeHeap.Push(node.Next);
            }
        }
        return resultHead;
    }
    
    public class ListNode : IComparable<ListNode>
    {
        public int Value;
        public ListNode Next;

        public ListNode(int val)
        {
            Value = val;
        }

        public int CompareTo(ListNode otherNode)
        {
            if (otherNode == null)
            {
                return 1;
            }

            if (otherNode.Value != null)
            {
                return this.Value.CompareTo(otherNode.Value);
            }
            else
            {
                throw new ArgumentException("Object is not a ListNode");
            }
        }
    }

    public class MinHeap<T> where T: System.IComparable<T> 
    {
        public List<T> heapList {get; set;}
        
        public int Count {get => heapList.Count;}
        
        private int GetLeftChildIndex(int elementIndex) => 2 * elementIndex + 1;
        private int GetRightChildIndex(int elementIndex) => 2 * elementIndex + 2;
        private int GetParentIndex(int elementIndex) => (elementIndex - 1) / 2;
        
        private bool HasLeftChild(int elementIndex) => GetLeftChildIndex(elementIndex) < Count;
        private bool HasRightChild(int elementIndex) => GetRightChildIndex(elementIndex) < Count;
        private bool IsRoot(int elementIndex) => elementIndex == 0;
        
        private T GetLeftChild(int elementIndex) => heapList[GetLeftChildIndex(elementIndex)];
        private T GetRightChild(int elementIndex) => heapList[GetRightChildIndex(elementIndex)];
        private T GetParent(int elementIndex) => heapList[GetParentIndex(elementIndex)];

        
        public MinHeap()
        {
            heapList = new List<T>();
        }
        
        public void PrintHeap()
        {
            foreach (T item in heapList)
            {
                Console.WriteLine(item.ToString());
            }
        }
        
        public void Push (T item)
        {
            heapList.Add(item);
            BubbleUp(Count - 1);
        }
        
        public T Pop ()
        {
            
            if (Count == 0)
            {
               throw new IndexOutOfRangeException();
            }

            // store copy to return at the end of the method
            T firstItemCopy = heapList[0];
            
            // move last item to first position
            heapList[0] = heapList[Count - 1];
            
            // remove the last thing off the list because it's redundant (it's now at the top of the heap)
            heapList.RemoveAt(Count - 1);
            
            FilterDown(0);
            
            return firstItemCopy;
        }
        
        public T Peek()
        {
            if (Count == 0)
            {
               throw new IndexOutOfRangeException();
            }

            return heapList[0];
        }
        
        public bool IsEmpty()
        {
            return Count == 0;
        }
        
        void Swap (int firstIndex, int secondIndex)
        {
            T temp = heapList[firstIndex];
            heapList[firstIndex] = heapList[secondIndex];
            heapList[secondIndex] = temp;
        }
        
        void BubbleUp (int index)
        {
            while (!IsRoot(index) && heapList[index].CompareTo(GetParent(index)) < 0)
            {
                int parentIndex = GetParentIndex(index);
                
                Swap(parentIndex, index);
                    
                index = parentIndex;
            }
        }
        
        void FilterDown (int index)
        {
            // set currentIndex
            int currentIndex = index;
            
            // while loop: check if index has a left child
            while (HasLeftChild(currentIndex))
            {
                // if it does, establish a smaller index
                int smallerIndex = GetLeftChildIndex(currentIndex);
                
                // check and see which of the left or right child has a smaller value
                // allocate the smaller value child as the smaller index
                if (HasRightChild(currentIndex) && GetRightChild(currentIndex).CompareTo(GetLeftChild(currentIndex)) < 0)
                {
                    smallerIndex = GetRightChildIndex(currentIndex);
                }
                
                // if the element at smallerindex is bigger than the element at current index, then break
                if (heapList[smallerIndex].CompareTo(heapList[currentIndex]) >= 0)
                {
                    break;
                }
                
                // otherwise, swap element[currentindex] with element[smallerindex]
                Swap(smallerIndex, currentIndex);
                
                // set index to smallerIndex
                currentIndex = smallerIndex;
                
                // while loop will break when the index no longer has a left child
            }
        }
    }
}