我正在将 C++ 库移植到 Java,我需要一个堆数据结构。是否有标准实施或我需要自己做?
原文由 user1796942 发布,翻译遵循 CC BY-SA 4.0 许可协议
我正在将 C++ 库移植到 Java,我需要一个堆数据结构。是否有标准实施或我需要自己做?
原文由 user1796942 发布,翻译遵循 CC BY-SA 4.0 许可协议
15 回答8.4k 阅读
8 回答6.2k 阅读
1 回答4k 阅读✓ 已解决
3 回答6k 阅读
3 回答2.2k 阅读✓ 已解决
2 回答3.1k 阅读
2 回答3.8k 阅读
对于 Java 8,更新现有 答案:
您可以将 Java 优先级队列用作堆。
最小堆: –> 使最小元素始终位于顶部,因此您可以在 O(1) 中访问它。
最大堆: –> 保持最大元素始终在顶部,与上面的顺序相同。
与其他答案中建议的
(Integer o1, Integer o2) -> Integer.compare(o2, o1)
或- Integer.compare(o1, o2)
相同。你可以使用:
add
–> 将元素添加到队列中。 O(log n)remove
–> 获取和删除最小值/最大值。 O(log n)peek
–> 获取,但不删除最小值/最大值。 O(1)