爪哇有堆吗？

我正在将一个 C + + 库移植到 Java 中，我需要一个堆数据结构。是否有一个标准的实现，还是我需要自己来完成？

132684 次浏览
小开

您还可以考虑 TreeSet，它保证基本操作(add、 delete、 include)的 log (n)时间。

小开

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

小开

最小堆积:

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

Max heap:

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

对于 Java8，更新现有的 回答:

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

Min Heap: —— > 以保持 Min 元素始终位于顶部，因此可以在 O (1)中访问它。

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

Max Heap: —— > 保持 Max 元素始终位于顶部，顺序与上面相同。

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

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

你可以使用:
向队列中添加元素
remove --> to get and remove the min/max. O(log n)
要获取，但不要删除 min/max. O (1)

小开

在 Java优先队列中可以用作堆。

Min Heap

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

Max Heap

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

没有，但是您可以使用优先队列作为堆。Oracle 正式告诉它使用优先级队列作为堆，您也可以参考 这个链接以获得进一步的说明。

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


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

来自 Java 文档 PriorityQueue，因为要使用的类是1.5。

这是 Min Heap 创建一个具有默认初始容量(11)的 PriorityQueue，它根据元素的 < a href = “ https://docs.oracle.com/javase/7/docs/api/java/lang/Compable.html”rel = “ nofollow noReferrer”> 自然排序 来排序它的元素的代码，其中 min 在顶部。

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

which helps you create the Max Heap in more elegant ways such as

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


提交答案