bob dylan bob dylan - 1 year ago 57
Java Question

How to constantly find the two smallest values from two different lists?

I have two different lists that contain integers and I need to constantly find the two smallest values between these two lists; I should note that I do NOT want to merge these two lists together, since they are different types.

I would like to know if my approach is good or bad. If it is bad, please let me know how I can make it more efficient.

  • Constantly have both lists sorted by descending order, so the mins will be at the bottom

  • Find the two mins from list1 and compare it with the two mins from list2 and find the two mins out of those four values

  • Remove the two mins from the associate list(s), combine their values together (required) and add it to list2

I am essentially performing a portion of the Huffman code, where I want to have a list of the frequency of chars in descending order.

Answer Source

Finding a min in List can be done in linear time without any sorting. Sorting and finding the min every time will be O(m*nlgn) m being the number of iterations and n the size of the list) .

A better way would to use PriorityQueue (min-heap) where the min is always on the top of the heap instead of sorting on every iteration.

Using a min-heap is common in implementing Huffman codes and greedy algorithms in general.