Java:插入/替换到特定大小的排序数组

Question

因此，我正在遍历二叉树，节点包含字符串，以及读取文件时该字符串是否出现多次。我只查找读取文件时出现次数最多的前 10 个单词，因此本质上我只是比较 int 值。

我的问题是我正在尝试找出一种有效的方法来比较和插入新节点(如果它们的计数值更大)。所以说我有一棵树...

   5
  /  \
 3    10
/       \

1 15

假设数组大小仅为 3。我从 1 开始，因为数组在 5 之前都是空的，在达到 5 后看起来会像这样...

[1],[3],[5]

当我达到 10 时，它比一切都大，但我想保持排序，所以我需要将 3 移至 1、5 移至 3、10 移至 5。我想知道是否有更有效的方法然后执行此操作以在每个更高的数字之后移动。它读取超过 10k+ 单词的文本文件，所以我希望它尽可能快。

如果不同的数据结构对此更好，请告诉我。我正在考虑队列或链表，但我认为数组浪费的空间更少，因为它的大小只有 10。我是一名学生，所以也要温柔点:-x。

Answer 1

一种方法是使用几种数据结构。使用 Map 和 Min-Heap 的建议方法如下:

• 当您从文件中读取单词时，请在 HashMap 中维护其计数(word、word_count)。
• 维护大小为 10 的最小堆。每当您更新 map 中的单词时，都会增加其计数。现在将此计数与最小堆的顶部元素进行比较。如果 word_count > value_at_top，则替换顶部元素并堆化。
• 完成从文件中的读取后，此堆将包含堆中最常见的前 10 个元素