C# Minimum heap using SortedDictionary

August 4, 2018

Introduction

There is no C# class like Java PriorityQueue for minimum heap. I learned to write a minimum heap using SortedDictionary since I read the source code to study the problem solving of the algorithm called Merge k sorted lists recently.

I like to write a blog to document my experience.

Source code 

Here is C# source code to write a minimum heap using SortedDictionary. Also the folder is here to access my practice for the algorithm 23 Merge K sorted lists.

Challenge 

Here is the fact:

Julia, you spent 10 rounds of mock interviews from March 2017 to June 2018. You could not come out using SortedDictionary to write a simple minimum heap for K messed sorted array algorithm.

Give a few arguments to defend yourself:
I do not spend time to read SortedDictionary source code.
I do not know how SortedDictionary class is designed, why it is needed.
I do not try to memeorize all APIs from SortedDictionary.
I do not have chance to read the code using SortedDictionary to solve the problem.
I did search why C# does not provide PriorityQueue like Java, but I do not find alternatives with source code using SortedDictionary. 
I got so many choices to continue to study and improve. I just move on other problems to solve.


Give a few advice how to break through the problem:

Please provide a possible three solutions you can approach to come out a written solution like using SortedDictionary.

Follow up

March 26, 2019

I reviewed the solution written for union find algorithm, and then I will write new version using SortedDictionary as well.

Here is the folder to contain my practice.

Here is the union find algorithm using SortedDictionary

Follow up 

June 4 2020
I like to work on 215 Find kth largest element in the array using SortedDictionary. The idea is to write a solution using minimum heap.

Leetcode discuss: 215. Kth Largest Element in an Array

June 5, 2020

Here is the post.

C# SortedDictionary minimum heap practice II in June 2020

It is my second practice on this algorithm. I found out that my first practice has a unnecessary work to save -1 * element value in the array to minimujm heap. Here is the first practice. I think that my first practice shows weakness of my analytical skills using minimum heap; I should argue that minimum heap can deal with kth largest element algorithm perfectly, without using maximum heap.

Case study
Given an array, find kth largest element in the array. For example, array [1, 2, 3, 4, 5], k = 2, so kth largest element is value 4, index position = 3; We have to iterate all numbers in the array in order to find kth largest one.

If minimum heap is kept to size k, then kth largest one will be on top of minimum heap after last element is visited.

Kth largest element in the array can be solved using minimum heap, and heap size is also k. If k is not too largest, heap size is not an issue, then I just choose to go ahead to save element value in minimum heap; otherwise I can play the trick to save -1 * element value to reduce heap size.

Here are higlights:

1. Design a minimum heap and understand the importance to keep minimum heap size as k;
2. Use C# SortedDictionary<int, int> strong typing, value data type is count of same element value in the array;
3. Look into other C# data structure which may be best choice compared to SortedDictionary<int, int>

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _215_kth_largest_element
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// First practice: June 4, 2020
        /// </summary>
        public class MinHeap
        {
            /// <summary>
            /// use SortedDictionary to implement the minimum heap              
            /// </summary>
            public SortedDictionary<int, int> sorted = new SortedDictionary<int, int>();

            public void Add(int val)
            {
                if (sorted.ContainsKey(val))
                {
                    sorted[val]++;
                }
                else
                {
                    sorted.Add(val, 1);
                }
            }

            /// <summary>
            /// SortedDictionary<int> default is in ascending order. 
            /// 
            /// </summary>
            /// <returns></returns>
            public int PopMin()
            {
                int minKey = sorted.Keys.First();

                var count = sorted[minKey];
                if (count == 1)
                {
                    sorted.Remove(minKey);
                }
                else
                {
                    sorted[minKey]--;
                }

                return minKey;
            }
        }

        /// <summary>
        /// Find kth largest element in the array, not kth largest distinct element
        /// For example, [1, 2, 3, 4, 5], kth largest element is 4 if k = 2; how to find 4? 
        /// All elements should be searched, last one is 5, kth one should be minimum one on the top. 
        /// The tricky part is to keep minimum heap size as k
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int FindKthLargest(int[] nums, int k)
        {
            if (nums == null || nums.Length == 0 || k < 0)
                return -1;            

            var length = nums.Length;
            var heap = new MinHeap();

            // Let us keep min heap size as k all the time
            // In other words, add one number to the heap, 
            // move the minimum one in the heap as well if heap's size is bigger than k. 
            int size = 0;

            for (int i = 0; i < length; i++)
            {
                var value = nums[i];
                size++;

                heap.Add(value);

                if (size > k)
                {
                    heap.PopMin();
                }
            }

            return heap.PopMin();
        }
    }
}

treesminimum heapc# sorteddictionary

Leetcode 23: Merge k sorted lists

August 3, 2018

Introduction

It is a hard level algorithm called Merge k sorted lists. I could not believe that I had to learn the algorithm again in such a short time. I spent over 30 minutes to study one of Leetcode discussion and wrote first time using SortedDictionary to implement C# minimum heap.

My practice

Here is my C# practice of the algorithm called Merge k sorted lists.

Related algorithm

I spent 30 minutes to rewrite mock interview algorithm called K messed array using minimum heap. It is so excited to learn how to write a minimum heap using C# using less than 20 lines of code.

Here is the algorithm code written for K messed array.

100-hard level algorithms 2018 summer campaign

Here is the hard level algorithm folder. I like to document the learning of the algorithm.

Challenge 

Here is the fact:

Julia, you spent 10 rounds of mock interviews from March 2017 to June 2018. You could not come out using SortedDictionary to write a simple minimum heap for K messed sorted array algorithm.

Give a few arguments to defend yourself:
I do not spend time to read SortedDictionary source code.
I do not know how SortedDictionary class is designed, why it is needed.
I do not try to memeorize all APIs from SortedDictionary.
I do not have chance to read the code using SortedDictionary to solve the problem.
I did search why C# does not provide PriorityQueue like Java.
I got so many choices to continue to study and improve. I just move on other problems to solve.


Give a few advice how to break through the problem:



Please provide a possible three solutions you can approach to come out a written solution like using SortedDictionary.

Leetcode discuss: 215. Kth Largest Element in an Array

Here is the post.

C# SortedDictionary minimum heap practice in 2020

June 4, 2020

Find kth largest element is very classical algorithm. I work on two tricky things to convert the problem into a minimum heap problem.

Warmup and best design talk

Let us walk through an example, how to design data structure heap for the help.
For example, integer array [1, 2, 3, 4, 5,6,7,8,9,10], k = 2
Minimum heap
Every number has to be went through, so the last one the heap should be [9, 10], the size is 2.
9 is the top of minimum heap.

Another example, still [1, 9, 2, 3, 4, 5, 6, 7, 8, 10], the last one the heap still should be [9, 10], the size is 2. Kth number is the top of heap.

The size of heap is important to find kth number in minimum heap. k = 2, heap size is 2.

If the array size is 10,000, number from 1 to 10,000, and then kth number is 9995, why we keep heap size as 9995, it is better to reverse the array in ascending order using -10,000 to -1. So the heap size can be 5 instead of 9995.

The exercise is warmup our design muscle and have a short break ice for real coding work.

Maximum heap
Since maximum heap can be processed using negative value of element array. We can stay with the minimum heap all the time.

Two tips
Work on a test case, array, [1, 2, 3, 4, 5], kth largest element, for example, 2th largest element is the fourth smallest element. Both are 4.

In order to apply kth largest element problem, it is to save -1 * element value. So largest one is converted into smallest one.If k is very big number close to size of array, then -1 * element will make sense, because n - k + 1 will be small integer, the minimum heap's size is small one.

Here are my highlights:

1. Design a minimum heap using SortedDictionary<int, int>, key is -1 * element value, value is count of element value; Notice that largest kth element not largest kth distinct element;
2. Write a class called MinHeap, two APIs, one is called Add(int val), second one is PopMin(), public property called sorted using SortedDictionary<int, int>;
3. Work on test case [1, 2, 3, 4,5], k = 2, 2th largest one is 4, and it is 4th smallest one. k -> n - k + 1 is the conversion mapping;
4. In order to get kth smallest minimum element, the heap size should be n - k + 1 at most.

Tips to share
I wrote a solution using minimum heap to find 814: third largest distinct element in the array, similar idea. The post is here.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _215_kth_largest_element
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// First practice: June 4, 2020
        /// </summary>
        public class MinHeap
        {
            /// <summary>
            /// use SortedDictionary to implement the minimum heap              
            /// </summary>
            public SortedDictionary<int, int> sorted = new SortedDictionary<int, int>();

            public void Add(int val)
            {
                if (sorted.ContainsKey(val))
                {
                    sorted[val]++;
                }
                else
                {
                    sorted.Add(val, 1); 
                }
            }

            /// <summary>
            /// SortedDictionary<int> default is in ascending order. 
            /// 
            /// </summary>
            /// <returns></returns>
            public int PopMin()
            {
                int minKey = sorted.Keys.First();

                var count = sorted[minKey];
                if (count == 1)
                {
                    sorted.Remove(minKey);
                }
                else
                {
                    sorted[minKey]--;
                }

                return minKey;
            }
        }

        /// <summary>
        /// Find kth largest element in the array, not kth largest distinct element
        /// Save each element value * -1, so kth largest one will be (n - k + 1)th smallest one. 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int FindKthLargest(int[] nums, int k)
        {            
            if (nums == null || nums.Length == 0 || k < 0)
                return -1;

            k = nums.Length - k + 1; // convert largest kth to smallest 

            var length = nums.Length;
            var heap = new MinHeap();            
          
            // Let us keep min heap size as k all the time
            // In other words, add one number to the heap, 
            // move the minimum one in the heap as well if heap's size is bigger than k. 
            int size = 0; 
            
            for (int i = 0; i < length; i++)
            {
                var negativeValue = -1 * nums[i];
                size++; 

                heap.Add(negativeValue);

                if (size > k)
                {
                    heap.PopMin();
                }
            }

            return -1 * heap.PopMin();
        }
    }
}

23. Merge k Sorted Lists

It is a hard level algorithm. I wrote a minimum heap using SortedDictionary and also I shared my solution here.

I like to warm up this algorithm since I was asked to work on the algorithm back in August 2018 phone screen.

Here is the link.

It is hard level algorithm and also minimum heap is most popular data structure to work on. I learned to write the first minimum heap using SortedDictionary in August 2018, and it is time for me to warm up and study other C# solution as well.

I like to take some time to write a C# solution again.

Here are highlights:

1. Define MinHeap class using SortedDictionary, the key of dictionary is the value of linked list node's value, the value of dictionary is Queue;
2. Add two API for MinHeap class, one is to add node to the heap, second one is to remove minimum from heap. In order to find node with minimum value, since SortedDictionary is sorted, just call First() API and then get Key.
3. Time complexity is O(k * logk + n * logk), k is the heap size, n is total of nodes in all the lists.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _23_merge_k_sorted_lists
{
    class Program
    {
        public class ListNode {
            public int val;
            public ListNode next;
            public ListNode(int x) { val = x; }
        }

        static void Main(string[] args)
        {
        }

        /// <summary>
        /// July 13, 2019
        /// I like to take the approach using minimum heap as a solution, so the time complexity will be O(N), 
        /// N is total of all nodes. 
        /// Assuming that lists's length is K, build a heap with size K, 
        /// time complexity: O(KlogN). 
        /// 
        /// </summary>
        /// <param name="lists"></param>
        /// <returns></returns>
        public ListNode MergeKLists(ListNode[] lists)
        {
            var heap = new MinHeap(); 

            // put head node in every list into minimum heap first
            foreach(var node in lists)
            {
                if (node == null)
                    continue;
                heap.Add(node.val, node);
            }

            // next build a linked list using ascending order
            ListNode current = null;
            ListNode newHead = null; 

            while(heap.map.Count > 0)
            {
                var node = heap.PopMin();
                if (node.next != null)
                    heap.Add(node.next.val, node.next);

                if (current == null)
                {
                    current = node;
                    newHead = current;
                }
                else
                {
                    current.next = node;
                    current = current.next; 
                }                
            }

            return newHead; 
        }

        /// <summary>
        /// Define my own minimum heap class MinHeap
        /// </summary>
        public class MinHeap
        {
            public SortedDictionary<int, Queue<ListNode>> map = new SortedDictionary<int, Queue<ListNode>>(); 

            public void Add(int val, ListNode node)
            {
                if(!map.ContainsKey(val))
                {
                    map.Add(val, new Queue<ListNode>());
                }

                map[val].Enqueue(node); 
            }

            public ListNode PopMin()
            {
                int minKey = map.First().Key;
                var node = map[minKey].Dequeue(); 

                if(map[minKey].Count == 0)
                {
                    map.Remove(minKey);
                }

                return node; 
            }
        }
    }
}

HackerRank: Sherlock And Anagram (VI)

March 27, 2016

 Julia was surprised to have a workout on this moderate difficult string problem from 9:00am - 4:00pm. She did some code study, and then, read so many codes from Microsoft, box, and saleforce, Amazon, and then, she read linkin profile, and blogs. She is getting connected to all other programmers in the world. HackerRank is young, all the coders are in charge of business this world, right now! No complaint.

 Just learn one good code  a time. Pay attention to some details. Follow up with a revisit once a while. Julia, you will make your programmer life easy, just relax, and see how people are creative to solve problems. You should do so, just copy the idea. Make sure that think by yourself first, do not be a copycat.

 This code is her favorite. She is still learning, never use SortedDictionary before,


 code reference:
https://www.hackerrank.com/Relentless

http://anothercasualcoder.blogspot.ca/#!

 Julia is too busy to work on coding, so she chooses on easy to moderate questions. She waited until 7 - 10 string questions, and then, finally, she worked on her first moderate question on HackerRank after 1 - 2 months. But, she likes to read other people's code, and then, she just needs ideas to solve problems.

 Here is the code gist:

https://gist.github.com/jianminchen/22f8e0de115cf656995e

/*
 Julia likes to talk about design of the function, through debugging, she knows a few things:

  For string "abba", 
  First, go over string with length 1, 
  then, SortedDictionary - key 'a', 'b', values are 2, 2
  then, Hashtable htPairs - key: a2, value: 

  then, go over string with length 2, 
  then, SortedDictionary - key 'a', value 1; key 'b', value '1'

  "abba" go through a loop, to get substring with length 2, in the order:
    ^  ->
     |
    "ab", 
    "bb", 
    "ba"
1.   string "ab", , key "a1b1",   htPairs["a1b1"] = 1
2.  string "bb", key "b2",          htPairs["b2"] = 1
3.  string "ba",            hashTable contains the key, so the value htPairs["a1b1] = 2
  Hashtable key "a1b1", sortedDictionary, value 2

*/
 static BigInteger UnorderedAnagrams(string str)
    {
        Hashtable htPairs = new Hashtable();

        for (int len = 1; len <= str.Length; len++)
        {
            for (int i = 0; i + len <= str.Length; i++)
            {
                SortedDictionary<char, int> anagram = new SortedDictionary<char, int>();
                for (int j = i; j < i + len; j++)
                {
                    if (anagram.ContainsKey(str[j]))
                    {
                        anagram[str[j]] = (int)anagram[str[j]] + 1;
                    }
                    else
                    {
                        anagram.Add(str[j], 1);
                    }
                }

                string finalKey = "";
                foreach (char key in anagram.Keys)
                {
                    finalKey += key.ToString() + ((int)anagram[key]).ToString();
                }

                if (!htPairs.ContainsKey(finalKey))
                {
                    htPairs.Add(finalKey, 1);
                }
                else
                {
                    htPairs[finalKey] = (int)htPairs[finalKey] + 1;
                }
            }
        }

        BigInteger finalResult = 0;
        foreach (string k in htPairs.Keys)
        {
            finalResult += Combinatorial((int)htPairs[k], 2);
        }

        return finalResult;
    }
Blogs:
http://juliachencoding.blogspot.ca/2016/03/hackerrank-string-sherlock-and-anagrams.html

703. Kth largest element in a stream

Oct. 27, 2018

Introduction

It is an easy level heap algorithm. I thought that I can write a solution using minimum heap quickly, but it took longer than one hour. I submitted more than four times and then finally I made it work.

My practice

Here is the post I shared on Leetcode discuss.

I like to write down very good experience to learn to design a minimum heap using SortedDictionary again, this time I also learned that time out issue, since I chose to count of minimum heap using SortedDictionary.Values.Count instead of keeping tracking of it by an variable actualSize.

What I did surprisingly is how to fix the timeout issue? Do SortedDictionary have issue with First() api related to time complexity?

I choose a good fight

One thing I like to do is to go for those easy level algorithms first, and also I like to show my problem solving skills.

First, I reviewed my past practice and I learned using SortedDictionary to write a minimum heap. I had rich experience to work on coding, since I have solved over 260 algorithms, I had experience to work on Merge k sorted lists, and I did study all C# submissions on Leetcode discuss.

Even though I have a lot of experience, but I still have to discipline myself again. I missed use case actualSize < size related to addNumberToHeap.

Most challenging thing is to solve timeout issue. I believe that SortedDictionary is based on binary tree to maintain the order, and I pinpointed the issue is related to check minimum heap's size. I decided to give it a try to track the size of heap by myself.

All those cases are really part of good workout for me to train myself, prepare myself for future challenge and exciting project to work.

1090. Largest Values From Labels

1090. Largest Values From Labels C# Try to solve using greedy algorithm practice in 2019

It is one of medium level algorithms in the contest. The greedy algorithm may work out fine.

Here are highlights:

1. Use SortedDictionary to save all values and their label into SortedDictionary, the key of hashMap is the value, the value of hashMap is list of labels. Since the same value for same label may have duplicate, List is used to store labels;
2. Get all keys in SortedDictionary and save into the array; Iterate one by one using descending order;
3. Fail test case II (see function RunTestcase2()), I have to learn how to break two loops instead of one.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1090_largest_value_from_labels
{
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase2();
        }

        public static void RunTestcase1()
        {
            var values = new int[] { 5, 4, 3, 2, 1 };
            var labels = new int[] { 1, 1, 2, 2, 3 };

            var result = LargestValsFromLabels(values, labels, 3, 1);
            Debug.Assert(result == 9);
        }

        public static void RunTestcase2()
        {
            var values = new int[] { 5, 4, 3, 2, 1 };
            var labels = new int[] { 1, 3, 3, 3, 2 };

            var result = LargestValsFromLabels(values, labels, 3, 2);
            Debug.Assert(result == 12);
        }

        /// <summary>
        /// 1090 largest value from labels
        /// Use greedy algorithm to solve the problem
        /// Try to simplify the algorithm and do not think generic case
        /// </summary>
        /// <param name="values"></param>
        /// <param name="labels"></param>
        /// <param name="num_wanted"></param>
        /// <param name="use_limit"></param>
        /// <returns></returns>
        public static int LargestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit)
        {
            var sortedMap = new SortedDictionary<int, List<int>>();

            var length = values.Length;
            for (int i = 0; i < length; i++)
            {
                var key = values[i];
                var value = labels[i];

                if (!sortedMap.ContainsKey(key))
                {
                    sortedMap.Add(key, new List<int>());
                }

                sortedMap[key].Add(value);
            }

            var usedCount = new Dictionary<int, int>();

            int index = 0;
            var numbers = sortedMap.Keys.ToArray();
            length = numbers.Length;
            var sum = 0;
            var breakLoops = false;
 
            for (int i = length - 1; i >= 0; i--)
            {
                var key  = numbers[i];
                var list = sortedMap[key];

                foreach (var item in list)
                {
                    if (!usedCount.ContainsKey(item))
                    {
                        usedCount.Add(item, 0);
                    }

                    if (usedCount[item] < use_limit)
                    {
                        index++;
                        sum += key;

                        usedCount[item]++;

                        if (index == num_wanted)
                        {
                            breakLoops = true;
                            break;  // there are two loops 
                        }
                    }
                }

                if (breakLoops)
                    break; // caught by online judge, test case 2
            }

            return sum; 
        }
    }
}

C# sortedDictionary - Minimum Cost Algorithm - an idea to write code (series 5 of 10)

Nov. 20, 2016

1. Introduction:
Julia spent time to write a C# solution in HackerRank - woman codesprint #2, using Dictionary<Int64, int> in the contest, here are the detail:

Here is the problem statement:
https://www.hackerrank.com/contests/womens-codesprint-2/challenges/minimum-loss

Julia's C# solution:

https://gist.github.com/jianminchen/af474846d81b96f4e70fc1a5866dca15

The ideas used in the algorithm:

Sort the array with house price.

Use bucket sort similar idea to go through each bucket, compare to previous if the current is less than minimum loss or not. Each bucket keeps the two value - max/ min value.

2. C# solution - Go deep to search for ideas to improve and strength the skill:

1. There is a solution written in C#, much simpler and smarter than Julia's C# code:

https://gist.github.com/jianminchen/c382bc1b40e47c2740a25abcaeffb846

Based on the assumption that housing price is different for each year, but I did not find the word in the problem statement.

2. Using Binary search - therefore, it is easy to find the minimum price, O(nlogn)
Maintain a binary search tree!

Study this C# solution using Binary search tree:

https://gist.github.com/jianminchen/c910f5d1f37309c70b489e6c75b0678c

3. Performance comparison among Java TreeSet, C# SortedSet, SortedDictionary:

Now, she likes to write a C# solution similar to C++14 using Set, Java 8 using TreeSet. Now she will write using SortedDictionary.

C# solution using SortedDictionary, timeout, only score 17.5 of 20.
https://gist.github.com/jianminchen/3e978465798afbd7d611e90a8ad7af0c

using C# SortedSet, timeout, score 17.5 of 20.
https://gist.github.com/jianminchen/63c1ed68999f78a72250372eb58a6953

Look up on stackoverflow.com
http://stackoverflow.com/questions/14675108/sortedset-sortedlist-with-better-linq-performance

Java TreeSet code: Perfect solution, score 20
https://gist.github.com/jianminchen/3fce12eff5838fa10bff0792547d0779

Test code here:
https://www.hackerrank.com/contests/womens-codesprint-2/challenges/minimum-loss

Use LINQ only, no SortedSet, timeout
https://gist.github.com/jianminchen/83f0079acbcfc4b6de3f5b1aff6aa131

Dec. 1, 2016
StackExchange.com Code Review
Julia came out the idea to get help from top talent in the world, she chose stackexchange.com code review and posted a code review request, a few people gave out their contribution, one on LINQ, one on SortedSet, then, Julia learned the solution. The question was posted on Nov. 30, 2016, and then, it was solved on Dec. 2, 2016. Less than 3 days.

Using List<T> BinarySearch
Using List<Int64>, BinarySearch and Insert APIs. Score 24 ( maximum score 35).

https://gist.github.com/jianminchen/d6c675533578d50049c636e566695830

The stackexchange.com code review link:
http://codereview.stackexchange.com/a/148714/123986

Using SortedSet<T> GetViewBetween(), score 30 (maximum score: 30)
http://codereview.stackexchange.com/a/148727/123986

C# submission:
https://gist.github.com/jianminchen/2fda6d1d11b19d6b59f3d44822115927