Java 中是否有堆（Heap）？

Question

我正在将一个C++库移植到Java，需要使用堆（heap）数据结构。是否有标准实现可用，还是我需要自己实现?

- user1796942

---

除了本地的PriorityQueue，guava还提供了一个MinMaxPriorityQueue。 - Elliott Frisch

与此相关的内容：https://dev59.com/RXNA5IYBdhLWcg3wEpoU - Ciro Santilli OurBigBook.com

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

---

删除操作在堆中不是应该是O(1)的吗？这些是红黑树的性能。 - Ilya Gazman

嗨@IlyaGazman，您需要在每次添加或删除后进行堆化，以便保持堆的平衡，这就是为什么这两个操作的时间复杂度为O(logn)。您还可以查看此文章：https://www.geeksforgeeks.org/insertion-and-deletion-in-heaps/ - Ahmed Hamdy

Answer 2

最小堆：

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);
    }
});

- user2015398

---

"Integer.compare(o1, o2);" 的意思是将 o1 和 o2 进行比较，而"Integer.compare(o2, o1);"的意思则是将 o2 和 o1 进行比较。这两条语句的含义相同。 - Naman

Answer 3

在Java中，PriorityQueue可以用作堆。

最小堆

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

最大堆

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

- Boaz

---

它与这个或这个答案有何不同？ - Naman

当我写这篇文章的时候，没有其他答案提供了Comparator.reverseOrder()选项。有些回答是在我的发帖之后发布的，也有一些是经过编辑的。 - Boaz

Answer 4

PriorityQueue使用堆来实现。根据Oracle文档的描述，https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html，它似乎是二叉堆的一种实现方式。我认为目前没有斐波那契堆或成对堆的官方实现，但我很想看到其中任意一种。

- Pete

Answer 5

实际上没有堆，但您可以使用优先级队列作为堆。Oracle官方建议使用优先级队列作为堆，您也可以参考此链接以获取更多说明。

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

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

- Anubhav Mishra

---

它与这个或这个答案有何不同？ - Naman

Answer 6

从Java文档中可以得知，自1.5以来可用的PriorityQueue类是我们应该使用的。

下面这段代码实现的是一个最小堆，它使用默认初始化容量（11）创建了一个PriorityQueue对象，按照自然顺序（natural ordering）排序其元素，其中最小值在堆顶。

//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
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

- mcvkr

---

这有什么不同于已经提供的答案呢？ - Svetlin Zarev

@SvetlinZarev它提供更多的参考资料，告诉我们类是何时引入和更新的，给出了一个自然排序和其他用途的定制对象示例，不仅限于整数。谢谢你的询问。 - mcvkr

Answer 7

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

- Adriana Cosma

---

TreeSet提供的特性与堆有所不同。优先队列是Java中java.util.*的堆结构。 - ahains

实际上，TreeSet 在内部使用 TreeMap 数据结构实现，而 TreeMap 是一种红黑树实现方式，因此它与堆有所不同。 - Alfredo Osorio