Tas (informatique)

Pour enfiler un élément, on le place comme feuille, puis on fait "remonter" l'élément pour maintenir la priorité du tas.

Pseudo-code :

Fonction enfiler (T,e)
   ajouter e à T en dernière position
   T.taille=T.taille+1
   appeler tasser_1 (T,T.taille)
   retourner T

Python :

def enfiler(T, e):
    """On ajoute une feuille au tas, et on la tasse"""
    T = T + [e]
    tasser_1(T, len(T) - 1)
    return T

La fonction tasser_1 prend en entrée un arbre binaire presque complet, tel que celui-ci est un tas, sauf éventuellement au niveau de T[i], et retourne l'arbre réordonné en tas. Pour cela, il compare T[i] à son parent, on les échange si T[i] est plus grand que son parent, et on recommence, ou alors on stoppe l'algorithme :

Pseudo-code :

Fonction tasser_1 (T,i)
   k = ${\displaystyle \displaystyle argmax_{j\in \left\{i,\left\lfloor {\frac {i}{2}}\right\rfloor \right\}\cap [\![1,...,T.taille]\!]}T[j]}$
   si k = ${\displaystyle i}$
       échanger ${\displaystyle T[i]}$ et ${\displaystyle T[k]}$
       appeler tasser_1 (T,${\displaystyle \displaystyle \left\lfloor {\frac {i}{2}}\right\rfloor }$)

Python :

import numpy as np
def tasser_1(T, index):
    """On tasse des feuilles vers la racine"""
    # a//b correspond au quotient de a par b
    index_parent = (index - 1) // 2
    # np.argmax permet de renvoyer la place du plus grand élément d'un tableau donné
    # ex: np.argmax([3,1,2]) renvoie 0
    k = np.argmax([T[index], T[index_parent]])
    if k == 0:
        # Echange des deux noeuds: a,b = b,a
        T[index], T[index_parent] = T[index_parent], T[index]
        # Si le noeud parent n'est pas la racine
        # on continue de tasser à partir de l'index parent
        if index_parent != 0:
            tasser_1(T, index_parent)

L’opération peut être réalisée en O(log(n)). Dans certaines implémentations, l’insertion est en temps constant mais la propriété de tas n’est pas conservée.

Quand on défile un élément d'un tas, c'est toujours celui de priorité maximale. Il correspond donc à la racine du tas. L’opération peut conserver la structure de tas avec une complexité de O(log(n)) ; en effet, il ne reste alors qu'à réordonner l'arbre privé de sa racine pour en faire un nouveau tas, en plaçant la dernière feuille à la racine, puis par tamisage successif (on peut également seulement lire l'élément, sans pour autant le supprimer du tas, en temps constant) :

Pseudo-code :

Fonction défiler (T)
   m:=T[1]
   T[1]:=T[T.taille]
   T.taille=T.taille-1
   appeler tasser (T,1)
   retourner m

Python :

def defiler(T):
    m = T[0] 
    T[0] = T[-1] # T[-1] correspond au derner élément de T
    T = T[:-1] # T[:-1] correspond au tableau T sans le dernier élément
    tasser(T, 0)
    return m

La fonction tasser prend en entrée un arbre binaire presque complet, tel que T est un tas sauf éventuellement en T[i], et retourne l'arbre réordonné en un tas.

Défiler appliqué au tas de l'introduction (on enlève le 12)

Pseudo-code :

Fonction tasser (T,i)
   k=${\displaystyle \displaystyle argmax_{j\in \{i,2i+1,2i+2\}\cap [\![1,...,T.taille]\!]}T[j]}$
   si k${\displaystyle \neq }$i
       échanger ${\displaystyle T[i]}$et ${\displaystyle T[k]}$
       appeler tasser (T,k)

Python :

import numpy as np
def tasser(T, index):
    """On tasse de la racine vers les feuilles"""
    index_fils_gauche = index * 2 + 1
    index_fils_droit = index * 2 + 2
    # Verification de la présence d'un fils droit
    if index_fils_droit < len(T):
        A = [T[index], T[index_fils_gauche], T[index_fils_droit]]
    else:
        A = [T[index], T[index_fils_gauche]]
    # L'ordre de A permet d'obtenir un décalage (0, 1 ou 2)
    decalage = np.argmax(A)
    # Si le décalage vaut 0, le noeud courant est à sa place
    # donc on arrête de tasser
    if decalage != 0:
        # Sinon un des fils est plus grand, donc on l'échange de place
        index_plus_grand_fils = index * 2 + decalage
        T[index], T[index_plus_grand_fils] = T[index_plus_grand_fils], T[index]
        nouvel_index = index_plus_grand_fils
        # Si le noeud a encore des fils, on continue de tasser
        index_nouveau_fils_gauche = 2 * (nouvel_index) + 1
        if index_nouveau_fils_gauche < len(T):
            tasser(T, nouvel_index)

Le tamisage ou parfois entassement, appliqué à un nœud n dont les fils g et d vérifient tous les deux la condition de tas permet, par échange de n avec l’un des fils g ou d, puis tamisage du sous arbre représenté par le fils échangé, de transformer le sous arbre (n, g, d) en tas. Le coût de l’opération dans le pire des cas est de O(h-p(n)), où p(n) est la profondeur du nœud n et h la hauteur totale du tas (cette hauteur étant en logarithme du nombre de nœud, car on a affaire a un arbre presque complet).

Pour construire un tas à partir d'un arbre (implémenté comme un tableau), il suffit de le tasser successivement, en partant "en bas" de l'arbre, sans se préoccuper des feuilles :

Construction du tas de l'introduction

Pseudo-code :

Fonction construire_tas (T)
   T.taille=${\displaystyle \left\vert T\right\vert }$
   pour i allant de ${\displaystyle \left\lfloor {\frac {\left\vert T\right\vert }{2}}\right\rfloor }$ à 1
       appeler tasser (T,i)

Python :

def construire_tas(T):
    for i in range(len(T) // 2, 0, -1):
        tasser(T, i)

La construction se fait en O(n), où n est le nombre total de nœuds.

Quitte à devoir construire un arbre à partir des données en entrée (en O(n)), il est possible d’extraire le sommet du tas et de tamiser à la racine, en répétant l’opération jusqu’à avoir un tas vide. Les données en entrée sont alors triées dans l’ordre croissant en O(n log(n)) (complexité asymptotique optimale pour un tri) ; et une représentation en mémoire astucieuse (avec des tableaux de taille fixée) permet d’effectuer le tri sur place, c’est-à-dire sans allocation de mémoire supplémentaire autre que la pile d’exécution des récursions. Cependant, ce tri n’est pas stable, et sa complexité temporelle est en pratique inférieure à celle du tri rapide (quicksort).

Certaines implémentations permettent également la suppression d’éléments autres que le sommet, et la modification de la clef d’un élément. Il est possible d’implémenter ces opérations en O(log(n)), mais une structure de données annexe, permettant de retrouver la position d’un élément, doit être gérée pour éviter une recherche dans le tas, non optimisé pour ce genre d’opérations et susceptible de nécessiter O(n) opérations sans cette table annexe.