Is er een Heap in Java?

Ik port een C++-bibliotheek naar Java en ik heb een heap-gegevensstructuur nodig. Is er een standaard?
implementatie of moet ik het zelf doen?

Antwoord 1, autoriteit 100%

Voor Java 8, bijwerken op een bestaand antwoord:

Je kunt Java Priority Queue als een heap gebruiken.

Min. Heap: –> om het min-element altijd bovenaan te houden, zodat je er toegang toe hebt in O(1).

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

Max Heap: –> om het max-element altijd bovenaan te houden, dezelfde volgorde als hierboven.

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

Wat hetzelfde is als (Integer o1, Integer o2) -> Integer.compare(o2, o1) of - Integer.compare(o1, o2) zoals gesuggereerd uit andere antwoorden.

En je kunt gebruiken:
add –> om een ​​element aan de wachtrij toe te voegen. O(log n)
remove –> om de min/max. O(log n)
peek –> te krijgen, maar niet verwijderen van de min/max. O(1)

Antwoord 2, autoriteit 66%

Min. hoop:

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

Maximale hoop:

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

Antwoord 3, autoriteit 18%

In Java PriorityQueue kan worden gebruikt als een heap.

Min. hoop

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

Maximale hoop:

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

Antwoord 4, autoriteit 13%

PriorityQueue gebruikt een heap. Gebaseerd op de Oracle-documentatie op https://docs.oracle .com/javase/8/docs/api/java/util/PriorityQueue.html lijkt het waarschijnlijk dat het een implementatie is van een binaire heap. Ik denk niet dat er een officiële implementatie is van een fibonacci of pairing-heap, hoewel ik graag een van beide beschikbaar zou zien.

Antwoord 5, autoriteit 3%

Nee, dat is er niet, maar u kunt Priority Queue als een heap gebruiken. Het is officieel verteld door Oracle om Priority Queue als een heap te gebruiken, je kunt ook verwijzen naar deze link voor meer uitleg.

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

Antwoord 6

U kunt ook overwegen TreeSet, die log(n) tijd garandeert voor basishandelingen (toevoegen, verwijderen, bevat).

Antwoord 7

Van Java-documenten PriorityQueue die beschikbaar is sinds 1.5 is de te gebruiken klasse.

Deze code voor Min Heap creëert een PriorityQueue met de standaard initiële capaciteit (11) die de elementen rangschikt volgens hun natuurlijke volgorde waarbij de min bovenaan staat.

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

Als u een speciale volgorde wilt implementeren, moet u de comparator met deze constructor overschrijven

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

Sinds 1.8 hebben we deze versie ook

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

die u helpt om de Max Heap op elegantere manieren te maken, zoals

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

Kijk voor een speciaal geval naar dit voorbeeld dat de natuurlijke volgorde voor een aangepast object laat zien, in een scenario waarin we klanten bestellen op basis van hun afstand tot een fictief 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}
         */
    }
}

Referenties

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