Structure de données Heap : Qu’est-ce qu’un Heap ?

Qu'est-ce qu'une structure de données de type tas ?

Un tas est une structure de données arborescente spécialisée. Cette structure comprend un nœud principal appelé racine (ou parent). Son deuxième nœud est son enfant gauche, et le troisième, son enfant droit. Les nœuds suivants sont remplis de gauche à droite. La clé du nœud parent est comparée à celle de ses enfants pour assurer un classement correct. L'arbre est facile à visualiser : chaque entité est appelée un nœud, et chaque nœud possède une clé unique pour son identification.

En termes simples, un tas est un arbre binaire complet qui satisfait la propriété de tas : chaque parent est ordonné de manière cohérente par rapport à ses enfants, ce qui le rend idéal pour les files d’attente prioritaires et le tri par tas.

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

Voici les principales raisons d'utiliser un tas :

• La structure de données de type tas permet la suppression et l'insertion en temps logarithmique – O(log₂n).
• Les données de l'arbre sont organisées selon un ordre précis. Outre la mise à jour ou la consultation de valeurs telles qu'un maximum ou un minimum, le programmeur peut identifier les relations entre le parent et l'enfant.
• Vous pouvez appliquer le concept du Modèle d'objet de document pour vous aider à comprendre visuellement la structure de données du tas.
• Les tas prennent en charge des opérations de file d'attente prioritaires efficaces, qui sont essentielles pour les algorithmes de graphes tels que le chemin le plus court de Dijkstra et l'arbre couvrant minimal de Prim.

Types de tas

La structure de données de type tas dispose de divers algorithmes pour gérer les insertions et les suppressions d'éléments, notamment la file de priorité, le tas binaire, le tas binomial et Tri de tas.

• File d'attente de priorité: C'est un abstracIl s'agit d'une structure de données contenant des objets hiérarchisés. Chaque objet possède une priorité prédéfinie. Par conséquent, l'objet ayant la priorité la plus élevée est traité en premier.
• Tas binaire : Les tas binaires conviennent aux opérations simples telles que les suppressions et les insertions. Ils constituent l'implémentation par défaut de la plupart des files de priorité de la bibliothèque standard.
• Tas binomial : Un tas binomial est constitué d'une série d'ensembles d'arbres binomiaux qui le forment. Un arbre binomial n'est pas un arbre ordinaire, car il est rigoureusement défini. Le nombre total d'éléments dans un arbre binomial est toujours égal à 2ⁿ.ⁿ nœuds.
• Tri par tas : Contrairement à la plupart des algorithmes de tri, le tri par tas utilise un espace mémoire constant (O(1)) pour son opération de tri. C'est un algorithme de tri par comparaison où le tri s'effectue par ordre croissant après avoir transformé les données d'entrée en un tas-max. On peut considérer le tri par tas comme une version améliorée d'un arbre binaire de recherche.

En général, une structure de données de type tas utilise deux stratégies. Pour les entrées 12 – 8 – 4 – 2 et 1 :

• Tas min. – la valeur la plus faible en haut
• Tas max – la valeur la plus élevée en haut

Tas min.

Dans la structure d'un tas min, la racine a une valeur inférieure ou égale à celle de ses enfants. La racine d'un tas min contient donc la valeur minimale. Un tas min est également un arbre binaire complet.

Une fois qu'un tas minimal est défini dans un arbre, toutes les feuilles peuvent potentiellement contenir la valeur maximale. Cependant, il est nécessaire d'examiner chaque feuille pour obtenir la valeur exacte du tas maximal.

Exemple de tas min

Dans le diagramme ci-dessus, vous pouvez observer une séquence claire allant de la racine au nœud le plus bas.

Supposons que vous stockiez les éléments dans le tableau Array_N[12, 2, 8, 1, 4]. Comme vous pouvez le constater, l'élément racine ne respecte pas la priorité du tas minimal. Pour préserver cette propriété, vous devez effectuer des opérations de réorganisation du tas (ou « min-heapify ») afin d'échanger les éléments jusqu'à ce que les règles du tas minimal soient respectées.

Tas max

Dans une structure de tas-max, le nœud parent (ou racine) a une valeur supérieure ou égale à celle de ses enfants. Ce nœud contient la valeur maximale. Il s'agit d'un arbre binaire complet ; on peut donc construire un tas-max à partir d'une collection de valeurs en temps constant O(n).

Voici quelques méthodes couramment utilisées lors de la mise en œuvre d'un Java Tas maximal :

• Ajouter (): Insère un nouvel élément dans le tas. Dans un tableau, les objets sont ajoutés à la fin, tandis que dans un arbre binaire, ils sont ajoutés de haut en bas puis de gauche à droite.
• Retirer (): Cette méthode permet de supprimer le premier élément de la liste. Comme l'élément ainsi déplacé n'est plus le plus grand, la méthode Sift-Down le déplace systématiquement vers sa nouvelle position.
• Filtrer vers le bas (): Cette méthode compare un objet racine à ses enfants, puis déplace le nœud relocalisé vers sa position légitime.
• Tamiser vers le haut (): Si vous utilisez la méthode `array` pour ajouter un nouvel élément à un tableau, la méthode `Sift-Up` permet à ce nouvel élément de se positionner correctement. Pour ce faire, il est d'abord comparé à son parent en simulant la structure de données arborescente.

  Appliquez la formule Parent_Index = Child_Index / 2. Continuez ainsi jusqu'à ce que l'élément maximal se trouve au début du tableau.

Tas de base Operations

Pour trouver les valeurs maximales et minimales d'un ensemble de données, vous aurez besoin de quelques opérations de base sur les tas, telles que la recherche, l'insertion et la suppression. Étant donné que les éléments sont constamment ajoutés et supprimés, vous devez savoir comment :

• 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 y insère les autres clés une à une en utilisant les opérations de base sur les tas.

Commençons donc à construire un tas min en utilisant la méthode de Williams en insérant les valeurs 12, 2, 8, 1 et 4. 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 un temps O(n log n).

• Tasifier : Une routine d'insertion qui permet d'insérer des éléments dans un tas tout en préservant les propriétés du tas.

  Par exemple, l'opération max-heapify vérifie que la valeur du parent est supérieure à celle de ses enfants. Les éléments peuvent ensuite être triés à l'aide de méthodes comme swap.ping.

• Fusionner: Pour fusionner deux tas en un seul, utilisez l'opération de fusion afin de réunir leurs valeurs. Les tas d'origine sont conservés.

Inspecter les tas

L'inspection des tas consiste à vérifier le nombre d'éléments dans la structure de données du tas et à valider si le tas est vide.

Il est important d'inspecter les tas lors du tri ou de la mise en file d'attente d'éléments. Vérifier la présence d'éléments à traiter à l'aide de la méthode `IsEmpty()` est essentiel. La taille du tas permet de localiser les racines `Max-Heap` ou `Min-Heap`, il est donc nécessaire de connaître le nombre d'éléments qui suivent la propriété `heap`.

• Taille – Renvoie la taille ou la longueur du tas. Elle indique le nombre d'éléments stockés, triés par ordre croissant.
• Est-Vide – renvoie TRUE si le tas est nul, 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 de type tas est utile dans de nombreuses applications de programmation concrètes, telles que :

• Contribue au filtrage des spams.
• Mise en œuvre d'algorithmes de graphes tels que Dijkstra et Prim.
• Operating système d'équilibrage de charge et compression des données.
• Recherche de statistiques d'ordre telles que le k-ième plus petit élément.
• Mise en œuvre de files d'attente prioritaires permettant de rechercher des éléments dans une liste en temps logarithmique.
• La structure de données de type tas est également utilisée pour le tri via le tri par tas.
• Simulation de clients faisant la queue.
• Gestion des interruptions dans le Operating système.
• En codage Huffman pour la compression de données.
• Optimisation de la recherche du meilleur d'abord et des heuristiques A* dans la planification de trajectoires en IA.

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

Les propriétés suivantes décrivent le comportement d'une file de priorité construite sur un tas :

• Dans les tas de priorité, les éléments de données de la liste sont comparés entre eux pour déterminer l'élément le plus petit ou le plus grand.
• Un élément est placé dans une file d'attente puis retiré par ordre de priorité.
• Chaque élément de la file d'attente prioritaire possède un numéro unique qui lui est associé et qui lui est attribué en tant que priorité.
• Lorsqu'on quitte une file d'attente prioritaire, l'élément ayant la priorité la plus élevée sort en premier.

Étapes de la mise en œuvre de la file d'attente à priorité de tas dans Java

La section suivante se déroule dans une zone en béton. Java implémentation qui transforme ces règles en code fonctionnel.

Tri en tas Java au Code Exemple

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 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 au Code Exemple

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)

Sortie

[1, 3, 4, 7, 9]

Ensuite, vous découvrirez… Méthode de bissection.

FAQ