Structure des données du tas

Dans ce didacticiel, vous apprendrez ce qu'est la structure de données du tas. En outre, vous trouverez des exemples fonctionnels d'opérations de tas en C, C ++, Java et Python.

La structure de données du tas est une arborescence binaire complète qui satisfait la propriété du tas . Il est également appelé comme un tas binaire .

Un arbre binaire complet est un arbre binaire spécial dans lequel

  • chaque niveau, sauf peut-être le dernier, est rempli
  • tous les nœuds sont le plus à gauche possible

Heap Property est la propriété d'un nœud dans lequel

  • (pour le tas maximum) la clé de chaque nœud est toujours supérieure à son / ses nœud (s) enfant (s) et la clé du nœud racine est la plus grande parmi tous les autres nœuds;
  • (pour le tas min) de chaque nœud est toujours plus petit que le ou les nœuds enfants et la clé du nœud racine est la plus petite parmi tous les autres nœuds.

Opérations de tas

Certaines des opérations importantes effectuées sur un tas sont décrites ci-dessous avec leurs algorithmes.

Heapify

Heapify est le processus de création d'une structure de données de tas à partir d'un arbre binaire. Il est utilisé pour créer un Min-Heap ou un Max-Heap.

  1. Soit le tableau d'entrée
  2. Créer un arbre binaire complet à partir du tableau
  3. Commencez par le premier index du nœud non feuille dont l'index est donné par n/2 - 1.
  4. Définissez l'élément actuel icomme largest.
  5. L'index de l'enfant gauche est donné par 2i + 1et l'enfant droit est donné par 2i + 2.
    Si leftChildest supérieur à currentElement(c'est-à-dire élément à l' ithindex), défini leftChildIndexcomme le plus grand.
    Si rightChildest supérieur à l'élément dans largest, défini rightChildIndexcomme largest.
  6. Echanger largestaveccurrentElement
  7. Répétez les étapes 3 à 7 jusqu'à ce que les sous-arbres soient également entassés.

Algorithme

 Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array(largest) set leftChildIndex as largest if rightChild > array(largest) set rightChildIndex as largest swap array(i) and array(largest)

Pour créer un Max-Heap:

 MaxHeap(array, size) loop from the first index of non-leaf node down to zero call heapify

Pour Min-Heap, les deux leftChildet rightChilddoivent être plus petits que le parent pour tous les nœuds.

Insérer un élément dans le tas

Algorithme pour l'insertion dans Max Heap

 If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array
  1. Insérez le nouvel élément à la fin de l'arborescence.
  2. Heapify l'arbre.

Pour Min Heap, l'algorithme ci-dessus est modifié afin qu'il parentNodesoit toujours plus petit que newNode.

Supprimer l'élément du tas

Algorithme de suppression dans Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Sélectionnez l'élément à supprimer.
  2. Échangez-le avec le dernier élément.
  3. Supprimez le dernier élément.
  4. Heapify l'arbre.

Pour Min Heap, l'algorithme ci-dessus est modifié afin que les deux childNodessoient plus petits que currentNode.

Peek (Trouver max / min)

L'opération Peek renvoie l'élément maximum de Max Heap ou l'élément minimum de Min Heap sans supprimer le nœud.

Pour les tas Max et Min Heap

 retourner rootNode

Extrait-Max / Min

Extract-Max renvoie le nœud avec la valeur maximale après l'avoir supprimé d'un tas Max tandis que Extract-Min renvoie le nœud avec le minimum après l'avoir supprimé du tas min.

Exemples Python, Java, C / C ++

Python Java C C ++ 
 # Max-Heap data structure in Python def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r if largest != i: arr(i),arr(largest) = arr(largest),arr(i) heapify(arr, n, largest) def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum); for i in range((size//2)-1, -1, -1): heapify(array, size, i) def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size-1) = array(size-1), array(i) array.remove(num) for i in range((len(array)//2)-1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr)) 
  // Max-Heap data structure in Java 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(); ) 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); ) )
 // Max-Heap data structure in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) void deleteRoot(int array(), int num) ( int i; for (i = 0; i  = 0; i--) ( heapify(array, size, i); ) ) void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); ) 
 // Max-Heap data structure in C++ #include #include using namespace std; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(vector &hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )

Applications de structure de données de tas

  • Le tas est utilisé lors de l'implémentation d'une file d'attente prioritaire.
  • Algorithme de Dijkstra
  • Tri de tas

Articles intéressants...