Y a-t-il un Heap en Java ?

Question

Je porte une bibliothèque C++ vers Java et j'ai besoin d'une structure de données de type "heap". Existe-t-il une implémentation standard ou dois-je la faire moi-même ?

Answer 1

Vous pouvez également envisager Ensemble d'arbres qui garantit un temps log(n) pour les opérations de base (ajouter, enlever, contenir).

Answer 2

Extrait de la documentation Java PriorityQueue qui est disponible depuis la version 1.5 est la classe à utiliser.

Ce code pour Min Heap crée une PriorityQueue avec la capacité initiale par défaut (11) qui ordonne ses éléments en fonction de leurs ordre naturel dans laquelle le min est au sommet.

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

Si vous voulez implémenter un ordre spécial, vous devez surcharger le comparateur avec ce constructeur.

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

Depuis la 1.8, nous avons également cette version

PriorityQueue(Comparator<? super E> comparator);

qui vous aide à créer le Max Heap de manière plus élégante, comme

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

Pour un cas particulier, consultez cet exemple qui montre l'ordonnancement naturel d'un objet personnalisé, dans un scénario où nous ordonnons les clients en fonction de leur distance par rapport à un restaurant fictif.

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

Réf.

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