Is There a Heap in Java?
I Am Porting a C++ Library to Java and I Need a Heap Data Structure. Is There a Standard Implementation or Will I Need to Do It Myself? 2 7 Answers for Java 8...
I am porting a C++ library to Java and I need a heap data structure. Is there a standard implementation or will I need to do it myself?
For Java 8, updating on an existing answer:
You can use Java Priority Queue as a Heap.
Min Heap: --> to keep the min element always on top, so you can access it in O(1).
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
Max Heap: --> to keep the max element always on top, the same order as above.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
Which is the same as (Integer o1, Integer o2) -> Integer.compare(o2, o1) or - Integer.compare(o1, o2) as suggested from other answers.
And you can use:
add --> to add element to the queue. O(log n)
remove --> to get and remove the min/max. O(log n)
peek --> to get, but not remove the min/max. O(1)
Min heap:
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);
}
});
In Java PriorityQueue can be used as a Heap.
Min Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue uses a heap. Based on the oracle documentation at it seems likely that it is an implementation of a binary heap. I don't think there is an official implementation of a fibonacci or pairing heap, though I'd love to see either one of the two available.
No as such there isn't but you can use Priority Queue as a Heap. Its officially told by Oracle to use Priority Queue as a Heap you can also refer to this link for further clarification.
PriorityQueue<Integer> MinHeap = new PriorityQueue<>();
PriorityQueue<Integer> MaxHeap = new PriorityQueue<>(Comparator.reverseOrder());
You can also consider TreeSet, which guarantees log(n) time for basic operations (add, remove, contains).
From Java docs PriorityQueue which is available since 1.5 is the class to use.
This code for Min Heap creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering in which the min is at the top.
//MIN HEAP
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//equivalent to
PriorityQueue<Integer> minHeap = new PriorityQueue<>(11);
If you want to implement a special ordering you need to override the comparator with this constructor
PriorityQueue(int initialCapacity, Comparator<? super E> comparator);
Since 1.8 we also have this version
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());
For a special case check this example that shows the natural ordering for a custom object, in a scenario where we order customers based on their distance to a fictional restaurant
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}
*/
}
}
Refs
1-
2-