bob dylan - 8 months ago 23

Java Question

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

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.