Is there a Heap in java?

Question

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?

Rosana

In addition to the native PriorityQueue, guava provides a MinMaxPriorityQueue – Alexandrina

related #1098777 – Yodle

Answer 1

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)

Seedbed

Isn't remove supposed to be o(1) in heaps? Those are the performance of RBT – Loma

Hi @IlyaGazman you will need to do heapify after every add or remove, so you can keep the balance of the heap, that is why those 2 operations are in O(logn). You can also check this article: geeksforgeeks.org/insertion-and-deletion-in-heaps – Seedbed

Answer 2

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

Knob

- Integer.compare(o1, o2); shall be same as Integer.compare(o2, o1); – Clutter

Answer 3

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

Gemoets

how is it different from this or this answer? – Clutter

At the time I wrote it, no other answer showed the option of Comparator.reverseOrder(). Some answered posted and some edited after my post – Gemoets

Answer 4

PriorityQueue uses a heap. Based on the oracle documentation at https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html 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.

Photoengrave

Answer 5

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

Sculpture

how is it different from this or this answer? – Clutter

Answer 6

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

Rustin

How is this any different than the already provided answers ? – Assiut

@SvetlinZarev it gives more refs, tells when the class was introduced and updated, gives an example to natural ordering and other uses for a custom object not only Integers. thanks for asking – Rustin

Answer 7

You can also consider TreeSet, which guarantees log(n) time for basic operations (add, remove, contains).

Clary

TreeSet provides different characteristics then a heap. Priority Queue is the Heap structure in java.util.* – Varitype

Actually, TreeSet uses a TreeMap internally, which it is a Red-Black Tree implementation so it is different than a heap. – Idio