Heap/Tas

Un tas (heap) est une structure de données arborescente qui satisfait la propriété de tas : pour chaque nœud, la valeur du nœud est supérieure (tas max) ou inférieure (tas min) à celles de ses enfants. Cette structure est généralement implémentée sous forme d'un tableau, où les relations parent-enfant sont définies par des indices.

Contexte d'utilisation

Les tas sont utilisés pour implémenter des files de priorité, pour le tri par tas (heapsort), et dans des algorithmes comme Dijkstra ou Prim. Ils permettent d'accéder efficacement à l'élément minimum ou maximum avec une complexité O(1), et d'insérer ou supprimer des éléments en O(log n).

Origine

Le concept de tas a été formalisé par J.W.J. Williams en 1964 lors de la création de l'algorithme de tri heapsort. Le terme "heap" en anglais fait référence à l'organisation en "tas" ou "amas" des éléments, reflétant sa structure partiellement ordonnée.

Exemple pratique:

# Implémentation d'un tas min en Python
class MinHeap:
    def __init__(self):
        self.heap = []
        
    def parent(self, i):
        return (i - 1) // 2
        
    def left_child(self, i):
        return 2 * i + 1
        
    def right_child(self, i):
        return 2 * i + 2
        
    def insert(self, value):
        self.heap.append(value)
        current = len(self.heap) - 1
        
        # Remonter l'élément jusqu'à sa position correcte
        while current > 0 and self.heap[current] < self.heap[self.parent(current)]:
            # Échanger avec le parent
            self.heap[current], self.heap[self.parent(current)] = self.heap[self.parent(current)], self.heap[current]
            current = self.parent(current)
            
    def extract_min(self):
        if not self.heap:
            return None
            
        min_val = self.heap[0]
        
        # Remplacer la racine par le dernier élément
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        
        # Faire descendre la nouvelle racine
        self._heapify_down(0)
        
        return min_val
        
    def _heapify_down(self, i):
        smallest = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
            
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
            
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self._heapify_down(smallest)

Variantes et nuances

• Tas binaire: La forme la plus courante, où chaque nœud a au maximum deux enfants.
• Tas binomial: Collection de tas binaires utilisée dans certaines files de priorité.
• Tas de Fibonacci: Variante optimisée pour les opérations de diminution de clé, utilisée dans l'algorithme de Dijkstra.
• Implémentation: En C++, la STL fournit std::priority_queue, en Java PriorityQueue, et Python offre le module heapq.

Termes associés:

• File de priorité: Structure de données souvent implémentée avec un tas, permettant d'accéder efficacement à l'élément de plus haute priorité.
• Heapsort: Algorithme de tri basé sur la structure de tas avec une complexité O(n log n).
• Propriété d'ordre partiel: Caractéristique fondamentale du tas où seule la relation parent-enfant est ordonnée, pas les relations entre nœuds de même niveau.
• Heapify: Processus de transformation d'un tableau en structure de tas.