102

我正在将 C++ 库移植到 Java,我需要一个堆数据结构。有标准实现还是我需要自己做?

4

7 回答 7

104

对于 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)

于 2019-09-07T12:52:36.613 回答
46

最小堆:

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);
    }
});
于 2019-02-13T08:07:09.990 回答
17

在 Java中PriorityQueue可以用作堆。

最小堆

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

最大堆

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
于 2020-04-12T10:27:38.247 回答
9

PriorityQueue 使用堆。根据https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html上的 oracle 文档,它似乎很可能是二进制堆的实现。我不认为斐波那契或配对堆的正式实现,尽管我很想看到两者中的任何一个可用。

于 2017-05-12T23:42:50.023 回答
2

不,没有,但您可以将优先级队列用作堆。Oracle 正式告知它使用优先级队列作为堆,您也可以参考此链接以获得进一步说明。

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

PriorityQueue<Integer> MaxHeap = new PriorityQueue<>(Comparator.reverseOrder());
于 2020-05-30T10:43:51.237 回答
0

自 1.5 起可用的Java 文档PriorityQueue是要使用的类。

此代码用于创建一个具有默认初始容量 (11) 的 PriorityQueue,它根据元素的自然顺序Min Heap 对其元素进行排序,其中最小值位于顶部。

//MIN HEAP
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//equivalent to 
PriorityQueue<Integer> minHeap = new PriorityQueue<>(11);

如果要实现特殊排序,则需要使用此构造函数覆盖比较器

PriorityQueue​(int initialCapacity, Comparator<? super E> comparator);

从 1.8 开始我们也有这个版本

PriorityQueue​(Comparator<? super E> comparator);

这可以帮助您Max Heap以更优雅的方式创建,例如

//MAX HEAP
PriorityQueue<Integer> maxHeap = 
new PriorityQueue<>((n1,n2) -> Integer.compare(n2,n1));
//equivalent to 
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

对于特殊情况,请查看此示例,该示例显示自定义对象的自然排序,在我们根据客户到虚构餐厅的距离为客户排序的场景中

import java.util.List;
import java.util.PriorityQueue;

public class DeliveryHandler {

    private static final Address restaurant = new Address(5.0, 5.0);

    private static class Address implements Comparable<Address> {
        public double x, y;

        public Address(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public double distanceToShop() {
            return Math.pow(restaurant.x - x, 2) + Math.pow(restaurant.y - y, 2);
        }

        @Override
        public int compareTo(Address other) {
            return Double.compare(this.distanceToShop(), other.distanceToShop());
        }

        @Override
        public String toString() {
            return "Address {x=%s, y=%s}".formatted(x, y);
        }
    }

    public static void main(String[] args) {
        List<Address> customers = List.of(
                new Address(13, 14),
                new Address(3, 1),
                new Address(9, 20),
                new Address(12, 4),
                new Address(4, 4));

        PriorityQueue<Address> queueServingClosest = new PriorityQueue<>();
        queueServingClosest.addAll(customers);
        while (!queueServingClosest.isEmpty()) {
            System.out.println(queueServingClosest.remove());
        }

        /* Prints
        Address {x=4.0, y=4.0}
        Address {x=3.0, y=1.0}
        Address {x=12.0, y=4.0}
        Address {x=13.0, y=14.0}
        Address {x=9.0, y=20.0}
         */

        PriorityQueue<Address> queueServingFurthest = new PriorityQueue<>(
                (a1, a2) -> Double.compare(a2.distanceToShop(), a1.distanceToShop())
        );
        queueServingFurthest.addAll(customers);
        while (!queueServingFurthest.isEmpty()) {
            System.out.println(queueServingFurthest.remove());
        }

        /* Prints
        Address {x=9.0, y=20.0}
        Address {x=13.0, y=14.0}
        Address {x=12.0, y=4.0}
        Address {x=3.0, y=1.0}
        Address {x=4.0, y=4.0}
         */
    }
}

参考文献

1- https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

2- https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html

于 2021-06-16T15:27:19.567 回答
0

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

于 2016-05-26T09:12:08.113 回答