相关疑难解决方法(0)

堆和BST有什么区别？

何时使用堆以及何时使用BST？

如果你想以排序的方式获取元素,BST是否优于堆？

具体来说,我需要一个集合,它使用一个字段A进行访问,使用另一个字段(字段S)进行排序,但是接受重复的已排序集合就足够了.

我经常到这一点,我需要这个集合,TreeMap不是一个选项,因为它不允许重复.所以现在是时候问这里了.stackoverflow 在这里和这里指出了几种解决方法- 即:

• PriorityQueue:缓慢更新(remove(Object)+ add(Object))和原始键的装箱
• 斐波纳契堆:内存浪费(？)
• TreeMap<Field_S, List<Value>>:对我来说问题是列表的内存开销和原始键的装箱
• 排序列表或数组:问题是慢插入和删除 - >我应该实现一个分段排序列表？
• 来自guava(docs)的TreeMultimap:外部依赖和可能内存效率低下(？)

谁有更好的建议？或者我应该对自己的排序数据结构(哪一个？)起作用？其他来源(Java,开源,单元测试和小deps)也不错.

更新

关于我目前用例的更多细节(虽然我上次有类似的需求).我有一个集合(有数百万)我想要的参考

• 轮询或获得关于字段S的最小元素
• 并在字段A的帮助下更新字段S.
• 字段S的相同值可能发生.字段A实际上是指向另一个数组的整数
• 我想要的唯一依赖是trove4j.如果需要,我可以使用不同的mahout集合.但不是番石榴,因为虽然是一个很好的lib,但是这些集合并没有被调整为内存效率(装箱/拆箱).

所以对于斐波那契堆的所有呼声,但我担心它每个元素的开销太多 - >这就是我考虑更高效的"排序+分段数组"解决方案的原因.

根据http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants,它采用Θ(logn)(转换为O(logn))来执行减小键操作.但是,似乎没有包含具有减少键操作的二进制堆实现的站点.

因此,由于Web上缺少实现,是否可以在二进制堆中执行reduce-key操作？

我知道Dijkstra的算法实际上是使用Fibonacci堆实现的.但它是否也可以使用红黑树实现,并且最坏情况下的运行时间仍为O(m log n)？