Réordonner le Tas (Heapify)

Il existe deux opérations principales que l’on peut effectuer sur un tas (heap) : ajouter un élément ou supprimer le nœud racine du tas. Après chaque opération, il est indispensable de s’assurer que les propriétés du tas ne sont pas enfreintes.

Lorsque l’on supprime la racine, il faut procéder de haut en bas pour modifier et ajuster la structure de manière à ce que tous les nœuds parents conservent une valeur plus grande que leurs nœuds enfants (pour un tas maximum).

Lors de l’ajout d’un élément, il faut remonter depuis le bas jusqu’au sommet du tas en réarrangeant la structure de façon à ce que les nœuds parents aient toujours une valeur supérieure à leurs nœuds enfants.

Insérer un Nouvel Élément dans un Tas

Pour insérer une nouvelle valeur, on commence par l’ajouter à la fin du tableau, puis on restaure la propriété du tas en échangeant systématiquement l’élément nouvellement inséré avec son parent si la propriété n’est pas respectée :

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Tas initial
heap.append(6)                        # Ajouter un nouvel élément d'une valeur de 6

# Remonter et corriger la propriété de tas
node = len(heap) - 1                  # L'indice du nœud actuel
while node > 1:                       # Tant que nous ne sommes pas au niveau de la racine
    parent = node // 2                # Récupérer l'indice du nœud parent
    if heap[node] > heap[parent]:     # Si la structure du tas n'est pas correcte
        heap[node], heap[parent] = heap[parent], heap[node]
    else:                             # Si la structure est correcte
        break                         # Alors ceux au-dessus sont aussi à leur place => on s'arrête
    node //= 2                        # Passer au nœud parent

Supprimer l’Élément Racine d’un Tas

Pour supprimer l’élément racine, on le remplace d’abord par le dernier élément du tableau, puis on restaure la propriété du tas en échangeant systématiquement le nœud avec son enfant le plus grand (dans le cas d’un tas maximum) jusqu’à ce que ce nœud occupe la position qui lui revient :

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Tas initial
heap[1], heap[-1] = heap[-1], heap[1] # Échanger la racine avec le dernier élément
heap.pop()                            # Retirer le dernier élément (anciennement la racine)

# Descendre et corriger la propriété de tas
node = 1                              # L'indice du nœud actuel
while node < len(heap):               # Tant que nous ne sommes pas arrivés à la fin
    left = heap[2 * node] if 2 * node < len(heap) else float('-inf')
    right = heap[2 * node + 1] if 2 * node + 1 < len(heap) else float('-inf')
    
    # Si la propriété de tas n'est pas violée => s'arrêter ici
    if heap[node] >= left and heap[node] >= right:
        break
    
    # Si left > right => nous devons aller vers la gauche
    if left > right:
        heap[2 * node], heap[node] = heap[node], heap[2 * node]
        node = 2 * node
    else:
        heap[2 * node + 1], heap[node] = heap[node], heap[2 * node + 1]
        node = 2 * node + 1

Défi : Corriger le Tas

On vous donne un tas minimum (min-heap) contenant n nombres. Les n-1 premiers nombres satisfont déjà la propriété du tas minimum, mais le n-ième nombre peut la violer. Vous devez corriger le tas pour que l’ensemble des nombres respecte bien les propriétés du tas minimum.

Entrée

La première ligne de l’entrée contient un entier n (1 ≤ n ≤ ).

La ligne suivante contient n entiers séparés par des espaces (), qui représentent les valeurs des éléments du tas.

Sortie

Le programme doit afficher n entiers séparés par des espaces qui correspondent au tas corrigé.

Exemples

Entrée	Sortie
7 1 2 5 4 3 6 -3	-3 2 1 4 3 6 5
6 5 6 9 20 10 8	5 6 8 20 10 9

Explication

Exemple 1

Exemple 2