0Pricing
Coding Interview Prep · Leçon

Propriété des tas et représentation par tableau

Comprenez la structure d’arbre binaire complet stockée dans un tableau, déduisez les formules d’index des parents et des enfants et visualisez les opérations de remontée et de descente.

Propriété des tas et représentation par tableau est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce qu'un tas ?

Un tas est un arbre binaire complet spécialisé qui respecte la propriété de tas : dans un tas min, chaque parent est inférieur ou égal à ses enfants ; dans un tas max, chaque parent est supérieur ou égal à ses enfants. Cette propriété garantit que l'élément minimal (ou maximal) se trouve toujours à la racine, ce qui permet d'accéder en O(1) à l'élément extrême. Les tas sont la structure de données qui se trouve derrière les files de priorité.

# Min-heap example:
#         1
#        / \
#       3   2
#      / \ / \
#     7  4 5  6
# Every parent <= its children
# Root (1) is always the minimum

# Max-heap example:
#         9
#        / \
#       7   8
#      / \ / \
#     3  4 5  6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')

Structure d'arbre binaire complet

Un tas est stocké sous la forme d'un arbre binaire complet : tous les niveaux sont entièrement remplis, sauf éventuellement le dernier, qui est rempli de gauche à droite. Cette structure permet une élégante représentation sous forme de tableau, sans espace inutilisé ni pointeurs. La propriété de complétude garantit que la hauteur du tas est toujours floor(log₂ n), ce qui assure des opérations d'insertion et d'extraction en O(log n).

# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))

# NOT complete (last level not left-filled):
#     1
#    / \
#   2   3
#        \
#         4  <- right child without left sibling

# Valid complete binary tree with 4 nodes:
#     1
#    / \
#   2   3
#  /
# 4
print('Complete BT: height = floor(log2(n)) always')

Représentation d'un tas sous forme de tableau

La structure d'arbre binaire complet permet de stocker un tas dans un simple tableau sans aucun pointeur. Pour un nœud situé à l'indice i (avec un indexage à partir de 0), son parent se trouve à l'indice (i-1) // 2, son enfant gauche à l'indice 2i+1 et son enfant droit à l'indice 2i+2. Cette arithmétique entière remplace le parcours par pointeurs et rend les tas extrêmement adaptés au cache.

# Array representation (0-indexed):
# Index:  0  1  2  3  4  5  6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree:        1          (index 0)
#             / \         
#            3   2        (indices 1, 2)
#           / \ / \       
#          7  4 5  6      (indices 3,4,5,6)

# Index formulas (0-based):
def parent(i):      return (i - 1) // 2
def left_child(i):  return 2 * i + 1
def right_child(i): return 2 * i + 2

heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])

Remontée dans le tas : restauration après une insertion

La remontée dans le tas (également appelée remontée par bulles ou heapify vers le haut) est utilisée après l'insertion d'un nouvel élément à la fin du tableau du tas. Comparez le nouvel élément à son parent ; si la propriété de tas est violée, échangez-les et poursuivez vers le haut. Répétez l'opération jusqu'à ce que l'élément soit à la bonne position ou atteigne la racine. Cette opération s'exécute en O(log n), car la hauteur de l'arbre est O(log n).

def sift_up(heap, i):
    while i > 0:
        p = (i - 1) // 2  # parent index
        if heap[p] > heap[i]:  # min-heap: parent should be smaller
            heap[p], heap[i] = heap[i], heap[p]
            i = p
        else:
            break  # heap property restored

# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0)  # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap)  # 0 should bubble to root

Descente dans le tas : restauration après une extraction

La descente dans le tas (heapify vers le bas) est utilisée après la suppression de la racine. Déplacez le dernier élément à la racine, puis faites-le descendre en l'échangeant successivement avec l'enfant le plus petit (dans un tas min) jusqu'à rétablir la propriété de tas. Cette opération s'exécute également en O(log n). La remontée et la descente dans le tas sont les éléments fondamentaux de toutes les opérations sur les tas.

def sift_down(heap, i, n):
    while True:
        smallest = i
        l = 2 * i + 1  # left child
        r = 2 * i + 2  # right child
        if l < n and heap[l] < heap[smallest]:
            smallest = l
        if r < n and heap[r] < heap[smallest]:
            smallest = r
        if smallest == i:
            break  # already in correct position
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap)  # valid min-heap again

Construire un tas à partir d'un tableau : algorithme de Floyd

Insérer naïvement n éléments un par un s'exécute en O(n log n). L'algorithme heapify de Floyd construit un tas en O(n) en appliquant la descente dans le tas à chaque nœud qui n'est pas une feuille, en commençant par le dernier nœud interne (indice n//2 - 1) et en remontant jusqu'à la racine. Les feuilles sont déjà des tas triviaux ; il suffit donc de corriger les nœuds internes. C'est pourquoi le travail total est en O(n) plutôt qu'en O(n log n).

def build_heap(arr):
    n = len(arr)
    # Start from last non-leaf node: index n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)
    return arr

arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr)  # root should be 1

# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).

Tri par tas à l'aide d'un tas représenté en tableau

Le tri par tas s'exécute en O(n log n) avec un espace supplémentaire en O(1). Phase 1 : construisez un tas max à partir du tableau en O(n). Phase 2 : extrayez successivement le maximum en échangeant la racine avec le dernier élément non trié, puis effectuez une descente dans le tas réduit. Après n extractions, le tableau est trié par ordre croissant. Cet algorithme en place montre comment la représentation sous forme de tableau permet de trier sans allouer une structure de données distincte.

def sift_down_max(arr, i, n):
    while True:
        largest = i
        l, r = 2*i+1, 2*i+2
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest == i: break
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

def heap_sort(arr):
    n = len(arr)
    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        sift_down_max(arr, i, n)
    # Extract elements one by one
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]  # move max to end
        sift_down_max(arr, 0, end)

arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr)  # [1, 2, 3, 5, 7, 8, 9]

Tas min ou tas max

Un tas min possède le plus petit élément à la racine ; une extraction renvoie donc toujours le minimum. Un tas max possède le plus grand élément à la racine ; une extraction renvoie donc toujours le maximum. Leur structure et leurs opérations sont identiques : seule la direction de la comparaison change. Le module heapq de Python implémente uniquement un tas min ; vous devez donc inverser le signe des valeurs pour simuler un tas max.

import heapq

# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap))  # 1

# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
    heapq.heappush(max_heap, -val)  # negate on push
print('Max-heap max:', -heapq.heappop(max_heap))  # 5 (negate on pop)

# For tuples: heapq sorts by first element
print(min_heap, max_heap)

Résumé de la complexité des opérations sur les tas

Toutes les opérations sur les tas reposent sur la remontée et la descente dans le tas, qui s'exécutent toutes deux en O(log n). Insertion : append + remontée dans le tas = O(log n). Extraction : échange de la racine avec le dernier élément + descente dans le tas = O(log n). Consultation : accès à l'indice 0 = O(1). Construction du tas : O(n) avec l'algorithme de Floyd. Tri par tas : O(n log n). Ces complexités font des tas la structure idéale lorsque vous devez récupérer régulièrement le minimum ou le maximum d'une collection dynamique.

# Heap complexity summary:
# Operation     | Time       | Space
# --------------|------------|-------
# Push          | O(log n)   | O(1)
# Pop (min/max) | O(log n)   | O(1)
# Peek          | O(1)       | O(1)
# Build from n  | O(n)       | O(1) in-place
# Heap sort     | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)

import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data))  # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data))  # [1, 2, 3]

Schémas pratiques d'utilisation des tas en entretien

Les tas permettent de résoudre toute une famille de problèmes d'entretien selon un schéma commun : maintenir une file de priorité de k candidats tout en parcourant n éléments en flux. Les k éléments les plus fréquents, les k points les plus proches de l'origine et le planificateur de tâches utilisent tous ce schéma. Reconnaissez-le lorsque vous voyez : « étant donné un flux de n éléments, maintenir les k meilleurs » : cela nécessite toujours un tas de taille k, pour un coût total en O(n log k).

import heapq

# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
    # Use max-heap (negate distance) of size k
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)  # negate for max-heap
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # remove farthest
    return [[x, y] for _, x, y in heap]

points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2))  # 2 closest to origin

Compromis entre tas et tableau trié

Choisissez un tas lorsque vous avez uniquement besoin d'accéder régulièrement au minimum ou au maximum et que la collection évolue dynamiquement. Choisissez un tableau trié lorsque vous avez besoin d'un accès aléatoire par indice ou de requêtes sur des intervalles. Le point faible du tas est que la recherche d'éléments arbitraires s'effectue en O(n) ; son avantage est l'insertion et la suppression en O(log n), ainsi que l'accès au minimum ou au maximum en O(1). Un tableau trié permet une insertion en O(n), mais une recherche en O(log n) grâce à la recherche binaire.

# Trade-off comparison:
# Structure     | insert  | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap      | O(logn) | O(logn)    | O(n)   | O(n)
# Sorted array  | O(n)    | O(n)       | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn)    | O(logn)| O(logn+k)
# Hash map      | O(1)    | O(1)       | O(1)   | O(n)

# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')

Vérification rapide

Vérifiez votre compréhension des concepts de Structures de données & algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris la propriété de tas et la structure d'arbre binaire complet, la représentation sous forme de tableau avec les formules d'indices du parent et des enfants, ainsi que la remontée et la descente dans le tas, qui constituent les éléments fondamentaux de toutes les opérations sur les tas, notamment la construction en O(n) de Floyd. Nous allons ensuite implémenter heapify et explorer le module heapq de Python.

Questions Fréquemment Posées

La leçon « Propriété des tas et représentation par tableau » est-elle gratuite ?

Oui — le texte complet de « Propriété des tas et représentation par tableau » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Propriété des tas et représentation par tableau » ?

Comprenez la structure d’arbre binaire complet stockée dans un tableau, déduisez les formules d’index des parents et des enfants et visualisez les opérations de remontée et de descente. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.

Combien de temps prend la leçon « Propriété des tas et représentation par tableau » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Propriété des tas et représentation par tableau
  2. Heapify, push et pop depuis zéro
  3. heapq de Python et astuces pour les tas max
  4. Médiane d’un flux de données et fusion k-voies
← Retour à Coding Interview Prep