我应该使用 bucketsort 还是 heapsort 对包含频率的 hashmap 进行排序？

Question

我在 Java 中有一个散列图 HashMap<String, Integer> frequency。键是一个字符串，我在其中保存电影的名称，值是所述电影的频率。

我的程序从用户那里获取输入，所以每当有人将视频添加到收藏夹时，我都会进入哈希映射并增加它的频率。

现在的问题是我需要拍摄最频繁的k部电影。我发现我可以在这个 leetcode problem 中使用 bucketsort 或 heapsort（检查第一条评论），但是我不确定它在我的情况下是否更有效。我的 hashmap 不断更新，因此如果一个频率发生变化，我需要再次调用排序算法。

根据我的理解，构建地图需要 O(N) 的时间，其中 'N' 是即使有重复的电影数量，因为它需要增加频率，这让我 'M' 独特的电影片名。这是否意味着对于任何给定的 k，heapsort 将导致 O(M * log(k)) 和 bucketsort O(M)？

Answer 1

不幸的是，

拥有一个按值（您映射到的对象）排序的地图不是问题。您可以改为拥有一个集合，其键按频率自行排序，但考虑到频率是此时的键，您无法在事先不知道频率的情况下查找该集合中的条目，这消除了练习的重点。

想到的一个策略是拥有 2 个独立的数据结构。一个是让你根据片名查找实物，一个是自排序：

@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);
    }
}

并为您提供：

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;
}

每个操作都摊销了 O(1) 或 O(logn)，即使是 top10 操作。因此，如果您运行一百万次“增加电影的频率，然后获得前 10 名”，我们这样做的次数为 n = #，那么最坏的情况是 O(nlogn) 性能。

注意：将 lombok 用于构造函数、getter 等 - 如果您不喜欢这样，请让您的 IDE 生成这些东西。

我应该使用 bucketsort 还是 heapsort 对包含频率的 hashmap 进行排序？

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

java

complexity-theory

frequency

heapsort

bucket-sort