using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        string[] arr = new string[] { "a", "c", "b", "z", "d", "g", "z", "g", "f", "d", "z", "z" };

        var result=GetTopTwoproducts(arr,3);

        foreach(var product in result)

            Console.WriteLine(product);

    }

    public static List<string> GetTopTwoproducts(string[] products, int k)

        {

            List<string> Top2 = new List<string>();

            if (products == null)

                return null;

            Dictionary<string, int> prodCounts = new Dictionary<string, int>();

            int counter = 0;

​

            foreach (var product in products)

            {

                if (prodCounts.ContainsKey(product))

                    prodCounts[product]++;

                else

                    prodCounts.Add(product, 1);

​

            }

​

            foreach (var key in prodCounts.Keys)

            {

                var minHeap = new MinHeap(prodCounts[key], key);

​

                if (counter < k)

                {

                    HeapOperations.Enqueue(minHeap);

                }

                else

                {

                    HeapOperations.Replace(minHeap);

                }

                counter++;

            }

​

            var result = HeapOperations.Get();

​

            foreach (var p in result)

            {

                Top2.Add(p.product);

            }

​

            return Top2;

        }

}

​

public class MinHeap

    {

        public int prodCount;

        public string product;

​

        public MinHeap(int prodCount, string product)

        {

            this.prodCount = prodCount;

            this.product = product;

        }

    }

​

    public class HeapOperations

    {

        public static MinHeap[] minHeap;

        public static int count;

​

        public static MinHeap[] Get()

        {

            return minHeap;

        }

​

        public static int GetParentIndex(int index)

        {

            if (index == 0)

                return -1;

            else if (index == 1 || index == 2)

            {

                return 0;

            }

            else

            {

                return (index - 1) / 2;

            }

        }

​

        public static int GetLeftIndex(int index)

        {

            return (index * 2) + 1;

        }

​

        public static int GetRightIndex(int index)

        {

            return (index * 2) + 2;

        }

​

        public static void Enqueue(MinHeap prod)

        {

            if (minHeap == null)

            {

                minHeap = new MinHeap[3];

                HeapOperations.minHeap[0] = prod;

                count++;

            }

            else

            {

                int lastIndex = count;

                minHeap[lastIndex] = prod;

                HeapifyUp(lastIndex);

                count++;

            }

        }

​

        public static void Replace(MinHeap prod)

        {

            int lastIndex = 0;

            if (minHeap[lastIndex].prodCount < prod.prodCount)

            {

                minHeap[lastIndex] = prod;

                HeapifyDown();

            }

        }

​

        public static void HeapifyUp(int lastIndex)

        {

            while (lastIndex > 0)

            {

                int parentIndex = GetParentIndex(lastIndex);

​

                if (minHeap[parentIndex] == null)

                {

                    Swap(minHeap, parentIndex, lastIndex);

                }

                else if (minHeap[parentIndex].prodCount > minHeap[lastIndex].prodCount)

                {

                    Swap(minHeap, parentIndex, lastIndex);

                }

                lastIndex = parentIndex;

            }

        }

​

        public static void HeapifyDown()

        {

            int lastIndex = 0;

            int leftIndex = GetLeftIndex(lastIndex);

            int rightIndex = GetRightIndex(lastIndex);

​

            while (lastIndex <= minHeap.Length - 1 && leftIndex<= minHeap.Length - 1 && rightIndex<= minHeap.Length - 1)

            {

                if (minHeap[leftIndex] != null && minHeap[lastIndex].prodCount > minHeap[leftIndex].prodCount)

                {

                    Swap(minHeap, lastIndex, leftIndex);

                    lastIndex = leftIndex;

                }

                else if (minHeap[rightIndex] != null && minHeap[lastIndex].prodCount > minHeap[rightIndex].prodCount)

                {

                    Swap(minHeap, lastIndex, rightIndex);

                    lastIndex = rightIndex;

                }

                if (lastIndex < leftIndex && lastIndex < rightIndex)

                    break;

                leftIndex = GetLeftIndex(lastIndex);

                rightIndex = GetRightIndex(lastIndex);

            }

        }

​

        public static void Swap(MinHeap[] arr, int i, int j)

        {

            var temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

        }

    }