我有一个要求来跟踪文本中单词的出现，并且这个出现需要按降序排列。我最初使用哈希映射数据结构，但是当我进一步研究时，我发现了“Trie”数据结构。
我认为“Trie”数据结构非常适合跟踪灵活性和复杂性的发生。但是还有一个要求，我需要按降序对事件进行排序。所以基本上先深入遍历“Trie”进行搜索。
实施明智这有点棘手，所以我想知道我是否走在正确的轨道上。任何意见都会很棒。在这种情况下使用的最佳数据结构是什么？
注意：排序顺序按出现次数递减，因此如果“A”出现 5 次，“B”出现 2 次，排序顺序应为“A”、“B”。此外，出现相同的两个单词也将按字母顺序排序。
谢谢
如果单词的前缀是可重复的，则trie 树将是最节省内存的解决方案，不幸的是仍然悲观 O(N)。您需要使用附加信息（单词计数器）来丰富标准的 trie-tree 类。
如果您正在寻找悲观的最佳解决方案，multimap 是一个更好的解决方案：
O(1) 插入时间（如果您的字母表中有很多字母，则不在特里树中）
O(N) 内存和运行时间
尽管如此，您仍然需要对相同出现计数桶内的单词进行排序，如果有许多单词具有相同的出现次数，则排序成为主要操作，并且 trie-tree 方法与 multimap 方法相同。
的主要属性trie是合并传入的数据以节省空间，因此，如果您想使用任何数据单元独有的属性，则无法从trie内置属性中受益。因此，您可以考虑如果要节省空间，请使用trie，但要获得最常用的单词，不知何故您需要使用其他算法（例如trie在收集数据后遍历并准备另一个表）。
我的想法可能priority queue是单词的频率，因为键可以是可能的候选者
您可以使用三元树，但插入时间很昂贵，但是当您只对前 5 个最常出现的单词感兴趣时，您可以跳过排序算法。