java中有堆吗？

Question

我正在将 C++ 库移植到 Java，我需要一个堆数据结构。是否有标准实施或我需要自己做？

原文由 user1796942 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

对于 Java 8，更新现有 答案：

您可以将 Java 优先级队列用作堆。

最小堆： –> 使最小元素始终位于顶部，因此您可以在 O(1) 中访问它。

 PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

最大堆： –> 保持最大元素始终在顶部，与上面的顺序相同。

 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

与其他答案中建议的 (Integer o1, Integer o2) -> Integer.compare(o2, o1) 或 - Integer.compare(o1, o2) 相同。

你可以使用：

add –> 将元素添加到队列中。 O(log n)

remove –> 获取和删除最小值/最大值。 O(log n)

peek –> 获取，但不删除最小值/最大值。 O(1)

原文由 Ahmed Hamdy 发布，翻译遵循 CC BY-SA 4.0 许可协议