Top K Most Frequent Numbers using MinHeap<T>, Dictionary<TKey,TValue>, and custom NumCountPair that implements IComparable

gistfile1.txt

/*

Given an unsorted array of numbers, find the top ‘K’ frequently occurring numbers in it.

Input: [1, 3, 5, 12, 11, 12, 11], K = 2
Output: [12, 11]

Approach:
// Create a class NumCountPair that implements IComparable to use in a MinHeap, which CompareTo other NumCountPairs based on their Count properties
// Use a dictionary to hold KeyValuePairs where the key is the number and the value is its frequency // tO(N), sO(N)
// Use a MinHeap of size K to hold top K most frequent elements (NumCountPair) as we iterate through the KVPs in dictionary // tO(N * log K) // sO(K)
//  If MinHeap.Peek().Count < KVP.Value, we pop() and push a new NumCountPair with KVP.Key, KVP.Value
// Copy all number properties from NumCountPairs in MinHeap to a result list by popping heap until it's empty // tO(K * logK), sO(K)
// Return the result list

Complexity:
// tO (N + N logK + K logK) => tO(N + 2N logK) => tO(N logK)
// sO(N + K + K) => sO(N + K)

*/

using System;
using System.Collections.Generic;

class Solution
{
    static void Main(string[] args)
    {
        int[] example = new int[] {1,3,5,12,11,12,11,5,5,5,5,5,5,3,3,3,3,3,3,3,3,3,3};
        List<int> output = FindTopKFrequentNumbers(example, 2);
        foreach(int item in output)
        {
            Console.Write(item + " ");
        }
    }
    
    public static List<int> FindTopKFrequentNumbers (int[] input, int k)
    {
        List<int> result = new List<int>();
        Dictionary<int, int> numCounts = new Dictionary<int, int>();
        MinHeap<NumCountPair> topK = new MinHeap<NumCountPair>(); // Heapifies based on NumCountPair.Count
        
        // Build Dictionary with KeyValuePairs
        foreach (int number in input)
        {
            if (!numCounts.ContainsKey(number))
            {
                numCounts.Add(number,0);
            }
            numCounts[number]++;
        }
        
        // Find top K elements using MinHeap of size K
        foreach(KeyValuePair<int,int> numCountKVP in numCounts)
        {
            if (topK.Count < k)
            {
                topK.Push(new NumCountPair(numCountKVP.Key, numCountKVP.Value));
            }
            else
            {
                if(topK.Peek().Count < numCountKVP.Value)
                {
                    topK.Pop();
                    topK.Push(new NumCountPair(numCountKVP.Key, numCountKVP.Value));
                }
            }
        }
        
        // Transfer to Result List
        while (topK.Count > 0)
        {
            NumCountPair topKPair = topK.Pop();
            result.Add(topKPair.Number);
        }
        
        return result;  
    }
    
    public class NumCountPair : IComparable<NumCountPair>
    {
        public int Number;
        public int Count;

        public NumCountPair(int num, int count)
        {
            Number = num;
            Count = count;
        }
        
        public int CompareTo(NumCountPair otherPair)
        {
            if (otherPair == null)
            {
                return 1;
            }
            
            if (otherPair.Count != 0)
            {
                return this.Count.CompareTo(otherPair.Count);
            }
            else
            {
                throw new Exception("NumCountPair does not have a value or count!");
            }
        }
    }
                      
    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
            }
        }
    }
}