what is heap data structure java
Ce didacticiel explique ce qu'est la structure de données Java Heap et les concepts associés tels que Min Heap, Max Heap, Heap Sort, Stack vs Heap avec des exemples:
Un tas est une structure de données spéciale en Java. Un tas est une structure de données arborescente et peut être classé comme un arbre binaire complet. Tous les nœuds du tas sont organisés dans un ordre spécifique.
=> Visitez ici pour voir la série de formations Java pour tous
Ce que vous apprendrez:
Structure de données de tas en Java
Dans la structure de données du tas, le nœud racine est comparé à ses enfants et arrangé selon l'ordre. Donc, si a est un nœud racine et b est son enfant, alors la propriété, clé (a)> = clé (b) générera un tas maximum.
La relation ci-dessus entre la racine et le nœud enfant est appelée «Propriété du tas».
En fonction de l'ordre des nœuds parent-enfant, le tas est généralement de deux types:
# 1) Max-Heap :Dans un Max-Heap, la clé du nœud racine est la plus grande de toutes les clés du tas. Il convient de s'assurer que la même propriété est vraie pour tous les sous-arbres du tas de manière récursive.
Le diagramme ci-dessous montre un exemple de tas max. Notez que le nœud racine est supérieur à ses enfants.
# 2) Min-tas :Dans le cas d'un Min-Heap, la clé du nœud racine est la plus petite ou minimale parmi toutes les autres clés présentes dans le tas. Comme dans le tas Max, cette propriété doit être récursivement vraie dans tous les autres sous-arbres du tas.
Un exemple, d'un arbre Min-heap, est illustré ci-dessous. Comme nous pouvons le voir, la clé racine est la plus petite de toutes les autres clés du tas.
Une structure de données de tas peut être utilisée dans les domaines suivants:
- Les tas sont principalement utilisés pour implémenter des files d'attente prioritaires.
- En particulier, le min-heap peut être utilisé pour déterminer les chemins les plus courts entre les sommets d'un graphe.
Comme déjà mentionné, la structure de données de tas est une arborescence binaire complète qui satisfait la propriété de tas pour root et les enfants. Ce tas est également appelé tas binaire .
Tas binaire
Un tas binaire remplit les propriétés ci-dessous:
- Un tas binaire est un arbre binaire complet. Dans un arbre binaire complet, tous les niveaux sauf le dernier niveau sont complètement remplis. Au dernier niveau, les touches sont le plus à gauche possible.
- Il satisfait la propriété de tas. Le tas binaire peut être max ou min-heap selon la propriété du tas qu'il satisfait.
Un tas binaire est normalement représenté comme un tableau. Comme il s'agit d'un arbre binaire complet, il peut facilement être représenté sous forme de tableau. Ainsi, dans une représentation de tableau de tas binaire, l'élément racine sera A (0) où A est le tableau utilisé pour représenter le tas binaire.
Donc en général pour tout ienode dans la représentation du tableau de tas binaire, A (i), nous pouvons représenter les indices des autres nœuds comme indiqué ci-dessous.
| A ((i-1) / 2) | Représente le nœud parent |
|---|---|
| L'accès est plus rapide. | Plus lent que la pile. |
| A ((2 * i) +1) | Représente le nœud enfant gauche |
| A ((2 * i) +2) | Représente le bon nœud enfant |
Considérez le tas binaire suivant:
La représentation sous forme de tableau du tas binaire min ci-dessus est la suivante:
Comme indiqué ci-dessus, le tas est parcouru selon le ordre de niveau c'est-à-dire que les éléments sont traversés de gauche à droite à chaque niveau. Lorsque les éléments d'un niveau sont épuisés, nous passons au niveau suivant.
Ensuite, nous allons implémenter le tas binaire en Java.
Le programme ci-dessous montre le tas binaire en Java.
import java.util.*; class BinaryHeap { private static final int d= 2; private int() heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int( capacity+1); Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap public void insert(int x){ if(isFull()) throw new NoSuchElementException('Heap is full, No space to insert new element'); heap(heapSize++) = x; heapifyUp(heapSize-1); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap(x); heap(x) = heap(heapSize -1); heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion private void heapifyUp(int i) { int temp = heap(i); while(i>0 && temp > heap(parent(i))){ heap(i) = heap(parent(i)); i = parent(i); } heap(i) = temp; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap(i); while(kthChild(i, 1) heap(rightChild)?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i Production:
nHeap = 7 4 6 1 3 2 5
Heap minimum en Java
Un min-heap en Java est un arbre binaire complet. Dans min-heap, le nœud racine est plus petit que tous les autres nœuds du tas. En général, la valeur de clé de chaque nœud interne est inférieure ou égale à ses nœuds enfants.
En ce qui concerne la représentation en tableau de min-heap, si un nœud est stocké à la position «i», alors son nœud enfant gauche est stocké à la position 2i + 1, puis le nœud enfant droit est à la position 2i + 2. La position (i-1) / 2 renvoie son nœud parent.
Vous trouverez ci-dessous les différentes opérations prises en charge par min-heap.
# 1) Insérer (): Au départ, une nouvelle clé est ajoutée à la fin de l'arborescence. Si la clé est plus grande que son nœud parent, la propriété du tas est conservée. Sinon, nous devons parcourir la clé vers le haut pour remplir la propriété du tas. L'opération d'insertion dans le tas min prend O (log n) temps.
# 2) extraitMin (): Cette opération supprime l'élément minimum du tas. Notez que la propriété du tas doit être conservée après avoir supprimé l'élément racine (élément min) du tas. Cette opération entière prend O (Logn).
# 3) getMin (): getMin () renvoie la racine du tas qui est également l'élément minimum. Cette opération se fait en temps O (1).
Vous trouverez ci-dessous un exemple d'arborescence pour un tas min.
Le diagramme ci-dessus montre une arborescence min-tas. Nous voyons que la racine de l'arbre est l'élément minimum de l'arbre. Comme la racine est à l'emplacement 0, son enfant gauche est placé à 2 * 0 + 1 = 1 et l'enfant droit est à 2 * 0 + 2 = 2.
Algorithme de tas min
Ci-dessous est l'algorithme de construction d'un min-heap.
procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A( ) , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A(left) < A( i ) ) smallest = left; else smallest = i; if(right <= N and A(right) < A(smallest) ) smallest = right; if(smallest != i) { swap A( i ) and A( smallest )); call min_heapify (A, smallest,N); } }Implémentation Min Heap en Java
Nous pouvons implémenter le tas min soit en utilisant des files d'attente de tableau ou de priorité. L'implémentation de min-heap à l'aide de files d'attente prioritaires est l'implémentation par défaut car une file d'attente prioritaire est implémentée en tant que min-heap.
Le programme Java suivant implémente le min-heap à l'aide de tableaux. Ici, nous utilisons une représentation de tableau pour le tas, puis nous appliquons la fonction heapify pour conserver la propriété de tas de chaque élément ajouté au tas. Enfin, nous affichons le tas.
class Min_Heap { private int() HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int(this.maxsize + 1); HeapArray(0) = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray(leftChild(pos)) || HeapArray(pos) > HeapArray(rightChild(pos))) { // swap with left child and then heapify the left child if (HeapArray(leftChild(pos)) = maxsize) { return; } HeapArray(++size) = element; int current = size; while (HeapArray(current) = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray(FRONT); HeapArray(FRONT) = HeapArray(size--); minHeapify(FRONT); return popped; } } class Main{ public static void main(String() arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } } Production:
Max Heap en Java
Un tas max est également un arbre binaire complet. Dans un tas max, le nœud racine est supérieur ou égal aux nœuds enfants. En général, la valeur de tout nœud interne dans un tas max est supérieure ou égale à ses nœuds enfants.
Alors que le tas max est mappé à un tableau, si un nœud est stocké à la position «i», alors son enfant gauche est stocké à 2i +1 et l’enfant droit est stocké à 2i + 2.
Le tas Max typique ressemblera à celui ci-dessous:
Dans le diagramme ci-dessus, nous voyons que le nœud racine est le plus grand du tas et que ses nœuds enfants ont des valeurs plus petites que le nœud racine.
Semblable à min-heap, le tas max peut également être représenté sous forme de tableau.
Donc, si A est un tableau qui représente le tas Max, alors A (0) est le nœud racine. De même, si A (i) est n'importe quel nœud dans le tas max, alors les autres nœuds adjacents peuvent être représentés à l'aide d'un tableau.
- A ((i-1) / 2) représente le nœud parent de A (i).
- A ((2i +1)) représente le nœud enfant gauche de A (i).
- A (2i + 2) renvoie le nœud enfant droit de A (i).
Les opérations pouvant être effectuées sur le tas max sont indiquées ci-dessous.
# 1) Insérer: L'opération d'insertion insère une nouvelle valeur dans l'arborescence de tas max. Il est inséré à la fin de l'arbre. Si la nouvelle clé (valeur) est plus petite que son nœud parent, la propriété du tas est conservée. Sinon, l'arborescence doit être entassée pour conserver la propriété de tas.
comment faire une liste en java
La complexité temporelle de l'opération d'insertion est O (log n).
# 2) ExtractMax: L'opération ExtractMax supprime l'élément maximum (racine) du tas maximum. L'opération amasse également le tas max pour conserver la propriété du tas. La complexité temporelle de cette opération est O (log n).
# 3) getMax: L'opération getMax renvoie le nœud racine du tas max avec la complexité temporelle de O (1).
Le programme Java ci-dessous implémente le tas max. Nous utilisons ArrayList ici pour représenter les éléments de tas maximum.
import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } void insert(ArrayList hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ public static void main(String args()) { ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println('Max-Heap array: '); h.printArray(array, size); h.deleteNode(array, 4); System.out.println('After deleting an element: '); h.printArray(array, size); } } Production:
Heap minimum de file d'attente prioritaire en Java
La structure de données de la file d'attente prioritaire en Java peut être directement utilisée pour représenter le tas min. Par défaut, la file d'attente prioritaire implémente min-heap.
Le programme ci-dessous illustre le tas min en Java à l'aide de la file d'attente prioritaire.
import java.util.*; class Main { public static void main(String args()) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println('
Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println('
Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } Production:
Heap max de file d'attente prioritaire en Java
Pour représenter le tas max en Java en utilisant la file d'attente Priority, nous devons utiliser Collections.reverseOrder pour inverser le tas min. La file d'attente prioritaire représente directement un tas min en Java.
Nous avons implémenté Max Heap en utilisant une file d'attente Priority dans le programme ci-dessous.
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println('
Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println('
Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } Production:
Tri de tas en Java
Le tri par tas est une technique de tri par comparaison similaire au tri par sélection dans laquelle nous sélectionnons un élément maximum dans le tableau pour chaque itération. Le tri du tas utilise la structure de données du tas et trie les éléments en créant un tas min ou max à partir des éléments du tableau à trier.
Nous avons déjà discuté du fait que dans le tas min et max, le nœud racine contient respectivement l'élément minimum et maximum du tableau. Dans le tri du tas, l'élément racine du tas (min ou max) est supprimé et déplacé vers le tableau trié. Le tas restant est ensuite entassé pour conserver la propriété du tas.
Nous devons donc effectuer deux étapes de manière récursive pour trier le tableau donné en utilisant le tri de tas.
- Construisez un tas à partir du tableau donné.
- Supprimez à plusieurs reprises l'élément racine du tas et déplacez-le vers le tableau trié. Heapify le tas restant.
La complexité temporelle du tri de tas est O (n log n) dans tous les cas. La complexité spatiale est O (1).
Algorithme de tri de tas en Java
Vous trouverez ci-dessous les algorithmes de tri de tas pour trier le tableau donné dans l'ordre croissant et décroissant.
# 1) Algorithme de tri en tas pour trier par ordre croissant:
- Créez un tas maximum pour le tableau donné à trier.
- Supprimez la racine (valeur maximale dans le tableau d'entrée) et déplacez-la vers le tableau trié. Placez le dernier élément du tableau à la racine.
- Heapify la nouvelle racine du tas.
- Répétez les étapes 1 et 2 jusqu'à ce que la matrice entière soit triée.
# 2) Algorithme de tri en tas pour trier par ordre décroissant:
- Construisez un tas min pour le tableau donné.
- Supprimez la racine (valeur minimale du tableau) et échangez-la avec le dernier élément du tableau.
- Heapify la nouvelle racine du tas.
- Répétez les étapes 1 et 2 jusqu'à ce que la matrice entière soit triée.
Implémentation du tri de tas en Java
Le programme Java ci-dessous utilise le tri par tas pour trier un tableau par ordre croissant. Pour cela, nous construisons d'abord un tas max, puis échangeons et entassons récursivement l'élément racine comme spécifié dans l'algorithme ci-dessus.
import java.util.*; class HeapSort{ public void heap_sort(int heap_Array()) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array(0); heap_Array(0) = heap_Array(i); heap_Array(i) = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array(), int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array(largest)) largest = left; if (right heap_Array(largest)) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array(i); heap_Array(i) = heap_Array(largest); heap_Array(largest) = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args()) { //define input array and print it int heap_Array() = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } } Production:
La complexité temporelle globale de la technique de tri de tas est O (nlogn). La complexité temporelle de la technique heapify est O (logn). Alors que la complexité temporelle de la construction du tas est O (n).
Stack Vs Heap en Java
Passons maintenant à un tableau de certaines des différences entre une structure de données de pile et un tas.
Empiler Tas Une pile est une structure de données linéaire. Un tas est une structure de données hiérarchique. Suit la commande LIFO (Last In, First Out). La traversée est dans l'ordre des niveaux. Principalement utilisé pour l'allocation de mémoire statique. Utilisé pour l'allocation de mémoire dynamique. La mémoire est allouée de manière contiguë. La mémoire est allouée à des emplacements aléatoires. La taille de la pile est limitée en fonction du système d'exploitation. Aucune limite de taille de tas appliquée par le système d'exploitation. Stack a uniquement accès aux variables locales. Heap a des variables globales qui lui sont allouées. L'allocation / désallocation de la mémoire est automatique. L'allocation / désallocation doit être effectuée manuellement par le programmeur. La pile peut être implémentée à l'aide de tableaux, de listes liées, de listes de tableaux, etc. ou de toute autre structure de données linéaire. Heap est implémenté à l'aide de tableaux ou d'arbres. Coût de la maintenance si moins. Plus coûteux à entretenir. Peut entraîner un manque de mémoire car la mémoire est limitée. Pas de pénurie de mémoire mais peut souffrir de fragmentation de la mémoire.
Questions fréquemment posées
Q # 1) La pile est-elle plus rapide que Heap?
Répondre: Une pile est plus rapide que le tas car l'accès est linéaire dans la pile par rapport au tas.
Q # 2) À quoi sert un tas?
Répondre: Heap est principalement utilisé dans les algorithmes qui trouvent le chemin minimum ou le plus court entre deux points comme l'algorithme de Dijkstra, pour trier en utilisant le tri de tas, pour les implémentations de file d'attente prioritaire (min-heap), etc.
Q # 3) Qu'est-ce qu'un tas? Quels sont ses types?
Répondre: Un tas est une structure de données hiérarchique et arborescente. Un tas est un arbre binaire complet. Les tas sont de deux types, c'est-à-dire le tas Max dans lequel le nœud racine est le plus grand parmi tous les nœuds; Tas min dans lequel le nœud racine est le plus petit ou le minimum parmi toutes les clés.
Q # 4) Quels sont les avantages de Heap par rapport à une pile?
Répondre: Le principal avantage du tas par rapport à la pile réside dans le tas, la mémoire est allouée dynamiquement et il n'y a donc pas de limite sur la quantité de mémoire pouvant être utilisée. Deuxièmement, seules les variables locales peuvent être allouées sur la pile tandis que nous pouvons également allouer des variables globales sur le tas.
Q # 5) Heap peut-il avoir des doublons?
Répondre: Oui, il n'y a aucune restriction sur le fait d'avoir des nœuds avec des clés en double dans le tas car le tas est un arbre binaire complet et il ne satisfait pas les propriétés de l'arbre de recherche binaire.
Conclusion
Dans ce didacticiel, nous avons discuté des types de tas et de tri de tas à l'aide de types de tas. Nous avons également vu l'implémentation détaillée de ses types en Java.
=> Consultez le guide de formation Perfect Java ici.
lecture recommandée
- Tutoriel Java Graph - Comment implémenter la structure de données graphiques
- Introduction aux structures de données en C ++
- Tri de tas en C ++ avec des exemples
- Arborescence AVL et structure de données de tas en C ++
- Structure de données d'arbre binaire en C ++
- Structure de données de file d'attente en C ++ avec illustration
- Structure de données de liste liée circulaire en C ++ avec illustration
- Principes de base de Java: syntaxe Java, classe Java et principaux concepts Java
