Structure de données du tas : qu'est-ce que le tas ? Tas min et max (exemple)

Qu'est-ce qu'un tas ?

Heap est une structure de données arborescente spécialisée. Le tas comprend le nœud le plus élevé appelé racine (parent). Son deuxième enfant est l'enfant gauche de la racine, tandis que le troisième nœud est l'enfant droit de la racine. Les nœuds successifs sont remplis de gauche à droite. La clé du nœud parent est comparée à celle de sa progéniture et un arrangement approprié se produit. L'arborescence est facile à visualiser où chaque entité est appelée un nœud. Le nœud possède des clés d'identification uniques.

Pourquoi avez-vous besoin d’une structure de données en tas ?

Voici les principales raisons d’utiliser la structure de données en tas :

La structure de données en tas permet la suppression et l'insertion en temps logarithmique – O(log₂n).
Les données de l'arborescence sont façonnées dans un ordre particulier. En plus de mettre à jour ou d'interroger des éléments tels qu'un maximum ou un minimum, le programmeur peut trouver des relations entre le parent et la progéniture.
Vous pouvez appliquer le concept du Modèle d'objet de document pour vous aider à comprendre la structure des données du tas.

Types de tas

La structure de données de tas comporte divers algorithmes pour gérer les insertions et la suppression d'éléments dans une structure de données de tas, notamment Priority-Queue, Binary-Heap, Binomial Heap et Tri en tas.

File d'attente de priorité: Il s'agit d'une structure de données abstraite contenant des objets priorisés. Chaque objet ou élément a une priorité prédéfinie. Par conséquent, l’objet ou l’élément auquel une priorité plus élevée est attribuée obtient le service avant les autres.
Tas binaire : Les tas binaires conviennent aux opérations de tas simples telles que les suppressions et les insertions.
Tas binomial : Un tas binomial se compose d’une série de collections d’arbres binomiaux qui composent le tas. L’arbre binomial Heap n’est pas un arbre ordinaire car il est rigoureusement défini. Le nombre total d'éléments dans un arbre binomial possède toujours 2ⁿ nœuds.
Tri en tas : Contrairement à la plupart des algorithmes de tri, le tri par tas utilise l'espace O(1) pour son opération de tri. Il s'agit d'un algorithme de tri basé sur une comparaison dans lequel le tri s'effectue par ordre croissant en le transformant d'abord en un tas maximum. Vous pouvez considérer un Heapsort comme un arbre de recherche binaire de qualité améliorée.

En règle générale, une structure de données en tas utilise deux stratégies. Pour entrée 12 – 8 – 4 – 2 et 1

Min Heap – la moindre valeur en haut
Max Heap – valeur la plus élevée au sommet

Tas min

Dans la structure Min Heap, le nœud racine a une valeur égale ou inférieure à celle des enfants de ce nœud. Ce nœud de tas d'un Min Heap contient la valeur minimale. Dans l'ensemble, sa structure en tas min est une solution complète arbre binaire.

Une fois que vous avez un tas Min dans un arbre, toutes les feuilles sont des candidates viables. Cependant, vous devez examiner chacune des feuilles afin d'obtenir la valeur exacte du tas maximum.

Exemple de tas minimum

Dans les diagrammes ci-dessus, vous pouvez remarquer une séquence claire de la racine au nœud le plus bas.

Supposons que vous stockiez les éléments dans Array Array_N[12,2,8,1,4]. Comme vous pouvez le voir sur le tableau, l'élément racine viole la priorité Min Heap. Pour conserver la propriété Min tas, vous devez effectuer les opérations min-heapify pour échanger les éléments jusqu'à ce que les propriétés Min tas soient remplies.

Tas maximum

Dans la structure de Max Heap, le nœud parent ou racine a une valeur égale ou supérieure à celle de ses enfants dans le nœud. Ce nœud contient la valeur maximale. De plus, il s'agit d'un arbre binaire complet, vous pouvez donc créer un tas maximum à partir d'une collection de valeurs et l'exécuter à une heure O(n).

Voici quelques méthodes pour implémenter un tas Java Max

Ajouter (): placez un nouvel élément dans un tas. Si vous utilisez un tableau, les objets sont ajoutés à la fin du tableau, tandis que dans l'arborescence binaire, les objets sont ajoutés de haut en bas puis de gauche à droite.
Retirer (): Cette méthode vous permet de supprimer le premier élément de la liste du tableau. Comme l'élément nouvellement ajouté n'est plus le plus grand, la méthode Sift-Down le pousse toujours vers son nouvel emplacement.
Filtrer vers le bas (): Cette méthode compare un objet racine à son enfant, puis pousse le nœud nouvellement ajouté à sa position légitime.
Tamiser (): si vous utilisez la méthode tableau pour ajouter un élément nouvellement inséré à un tableau, la méthode Sift-Up aide le nœud nouvellement ajouté à se déplacer vers sa nouvelle position. L'élément nouvellement inséré est d'abord comparé au parent en simulant la structure arborescente des données.
Appliquez la formule Parent_Index=Child_Index/2. Vous continuez ainsi jusqu'à ce que le maximum d'éléments se trouve au début du tableau.

Tas de base Operations

Pour trouver les valeurs les plus élevées et les plus basses d'un ensemble de données, vous avez besoin de nombreuses opérations de base sur le tas, telles que la recherche, la suppression et l'insertion. Parce que les éléments vont et viennent constamment, vous devez :

Trouvez – Recherchez un élément dans un tas.
insérer – Ajoutez un nouvel enfant dans le tas.
Supprimer – Supprimer un nœud d'un tas.

Créer des tas

Le processus de construction de tas est appelé création de tas. Étant donné une liste de clés, le programmeur crée un tas vide, puis insère les autres clés une par une en utilisant des opérations de base sur le tas.

Commençons donc par construire un Min-heap en utilisant la méthode de Willaim en insérant les valeurs 12,2,8,1 et 4 dans un tas. Vous pouvez construire le tas avec n éléments en commençant par un tas vide puis en le remplissant successivement avec d'autres éléments en utilisant le temps O (nlogn).

Heapify : dans l'algorithme d'insertion, qui permet d'insérer des éléments dans un tas. Des contrôles sont effectués pour savoir si la structure de données du tas de propriétés mise en évidence est respectée.
Par exemple, un tas maximal vérifierait si la valeur du parent est supérieure à celle de sa progéniture. Les éléments peuvent ensuite être triés à l'aide de méthodes telles que l'échange.

Fusionner : étant donné que vous avez deux tas à combiner en un seul, utilisez des tas de fusion pour rassembler les valeurs des deux tas. Cependant, les tas d'origine sont toujours conservés.

Inspecter les tas

L'inspection des tas fait référence à la vérification du nombre d'éléments dans la structure de données du tas et à la validation si le tas est vide.

Il est important d'inspecter les tas lors du tri ou de la mise en file d'attente des éléments. Il est important de vérifier si vous avez des éléments à traiter à l'aide de Is-Empty(). La taille du tas aidera à localiser le tas maximum ou le tas minimum. Vous devez donc connaître les éléments qui suivent la propriété tas.

Taille – renvoie la grandeur ou la longueur du tas. Vous pouvez savoir combien d’éléments sont triés.
Est vide – si le tas est NULL, il renvoie TRUE sinon, il renvoie FALSE.

Ici, vous imprimez tous les éléments du prioritéQ boucle puis en vérifiant que prioritéQ n'est pas vide.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Utilisations de la structure de données en tas

La structure de données en tas est utile dans de nombreuses applications de programmation dans la vie réelle, comme :

Aide au filtrage du spam.
Implémentation d'algorithmes graphiques.
Operating Équilibrage de la charge du système et compression des données.
Retrouvez l'ordre dans les statistiques.
Implémentez des files d'attente prioritaires dans lesquelles vous pouvez rechercher des éléments dans une liste en temps logarithmique.
La structure de données en tas est également utilisée pour le tri.
Simuler des clients sur une ligne.
Gestion des interruptions dans Operating système.
Dans le codage de Huffman pour la compression des données.

Propriétés de la file d'attente prioritaire du tas

Dans les tas prioritaires, les éléments de données de la liste sont comparés les uns aux autres pour déterminer l'élément le plus petit.
Un élément est placé dans une file d’attente puis supprimé.
Chaque élément de la file d'attente prioritaire possède un numéro unique qui lui est associé, identifié comme prioritaire.
À la sortie d'une file d'attente prioritaire, l'élément de priorité supérieure sort en premier.

Étapes de mise en œuvre de la file d'attente prioritaire du tas dans Java

Tri par tas en JAVA avec exemple de code

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Sortie

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Tri en tas Python avec exemple de code

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)