java中有堆吗？

Question

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

Answer 1

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

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

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

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

Max Heap: --> 保持最大元素始终在顶部，顺序与上面相同。

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)

Answer 2

在 Java PriorityQueue 中可以作为 Heap 使用。

最小堆

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

最大堆：

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

Answer 3

最小堆：

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

最大堆：

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return - Integer.compare(o1,o2);
        }
    });

Answer 4

PriorityQueue使用堆.基于https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html上的oracle文档,它似乎可能是二进制堆的实现.我不认为有一个斐波纳契或配对堆的正式实现,但我很乐意看到两者中的任何一个可用.

Answer 5

您还可以考虑TreeSet，它保证基本操作（添加、删除、包含）的 log(n) 时间。