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

Pour Java 8, la mise à jour d'une responder :

Vous pouvez utiliser la file d'attente prioritaire de Java comme un tas.

Min Heap : --> pour que l'élément le plus petit soit toujours en haut, afin de pouvoir y accéder en O(1).

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

Max Heap : --> pour que l'élément max soit toujours en haut, dans le même ordre que ci-dessus.

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

Ce qui est la même chose que (Integer o1, Integer o2) -> Integer.compare(o2, o1) o - Integer.compare(o1, o2) comme suggéré dans d'autres réponses.

Et vous pouvez utiliser :
add --> pour ajouter un élément à la file d'attente. O(log n)
remove --> pour obtenir et supprimer le min/max. O(log n)
peek --> pour obtenir, mais pas supprimer le min/max. O(1)

Answer 2

Tas min :

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

Tas maximum :

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

Answer 3

En Java PriorityQueueue peut être utilisé comme un tas.

Min Heap

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

Max Heap

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

Answer 4

PriorityQueue utilise un tas. D'après la documentation d'oracle à https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html il semble probable qu'il s'agisse d'une implémentation d'un tas binaire. Je ne pense pas qu'il y ait une implémentation officielle d'un tas de fibonacci ou d'un tas d'appariement, même si j'adorerais voir l'un des deux disponibles.

Answer 5

Non, il n'y en a pas, mais vous pouvez utiliser la file d'attente prioritaire comme un tas. Oracle a officiellement indiqué qu'il fallait utiliser Priority Queue comme Heap, vous pouvez également vous référer à ce lien pour plus de précisions.

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

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