哪个是合适的数据结构？

Question

我需要一个Java数据结构,它具有:

• 快速(O(1))插入
• 快速清除
• 快速(O(1))max()功能

什么是最好的数据结构？

HashMap几乎可以工作,但使用java.util.Collections.max()的地图大小至少为O(n).TreeMap的插入和删除速度太慢.

有什么想法吗？

Answer 1

O(1)插入和O(1)max()与快速移除点互斥.

max由于集合未排序,AO(1)插入集合将不具有O(1).必须对AO(1)max集合进行排序,因此插入是O(n).你必须咬紧牙关,在两者之间做出选择.然而,在这两种情况下,移除应该同样快.

如果您可以使用缓慢删除,则可以使用变量保存当前最高元素,将插入与该变量进行比较,max和insert应为O(1).然后删除将是O(n),因为在删除的元素最高的情况下你必须找到一个新的最高元素.

Answer 2

如果可以插入和删除O(log n),则可以使用TreeSet或PriorityQueue获得O(1)最大值.O(log n)对于大多数应用程序来说非常好.