Should I sort a hashmap that contains frequency with bucketsort or heapsort?

Question

I have a hashmap in Java in this form HashMap<String, Integer> frequency. The key is a string where I hold the name of a movie and the value is the frequency of the said movie.

My program takes input from users so whenever someone is adding a video to favorite I go in the hashmap and I increment its frequency.

Now the problem is at one point I need to take the most k frequent movies. I've found that I could use bucketsort or heapsort in this leetcode problem (check the first comment), however I am not sure if it is more efficient in my case. My hashmap constantly updates, therefore I need to call the sorting algorithm again times if one frequency changed.

From my understanding, it takes O(N) time to build the map, where 'N' is the number of movies even with duplicates as it needs to add to the frequency, which gets me 'M' unique movie titles. Would that mean that heapsort will result in O(M * log(k)) and bucketsort O(M) for any given k?

Answer 1

Having a map that sorts on values (the thing you map to) isn't a thing, unfortunately. You could instead have a set whose keys sort themselves on frequency, but given that frequency is the key at that point, you couldn't look up entries in this set without knowing the frequency beforehand which eliminates the point of the exercise.

One strategy that comes to mind is to have 2 separate data structures. One serves to let you look up the actual object based on the name of the movie, the other is to be self-sorting:

@Data
public class MovieFrequencyTuple implements Comparable<MovieFrequencyTable> {
    @NonNull private final String name;
    private int frequency;

    public void incrementFrequency() {
        frequency++;
    }

    @Override public int compareTo(MovieFrequencyTuple other) {
        int c = Integer.compare(frequency, other.frequency);
        if (c != 0) return -c;
        return name.compareTo(other.name);
    }
}

and with that available to you:

SortedSet<MovieFrequencyTuple> frequencies = new TreeSet<>();
Map<String, MovieFrequencyTuple> movies = new HashMap<>();

public int increment(String movieName) {
    MovieFrequencyTuple tuple = movies.get(name);
    if (tuple == null) {
        tuple = new MovieFrequencyTuple(name);
        movies.put(name, tuple);
    }

    // Self-sorting data structures will just fail
    // to do the job if you modify a sorting order on
    // an object already in the collection. Thus,
    // we take it out, modify, put it back in.
    frequencies.remove(tuple);
    tuple.incrementFrequency();
    frequencies.add(tuple);
    return tuple.getFrequency();
}

public int get(String movieName) {
    MovieFrequencyTuple tuple = movies.get(movieName);
    if (tuple == null) return 0;
    return tuple.getFrequency();
}

public List<String> getTop10() {
   var out = new ArrayList<String>();
   for (MovieFrequencyTuple tuple : frequencies) {
       out.add(tuple.getName());
       if (out.size() == 10) break;
   }
   return out;
}

Each operation is amortized O(1) or O(logn), even the top10 operation. So, if you run a million times 'increment a movie's frequency, then obtain the top 10', with n = # of times we do that, then the worst case scenario is O(nlogn) performance.

NB: Uses lombok for constructors, getters, etc - if you don't like that, have your IDE generate these things.