Heapify, push et pop depuis zéro
Implémentez la remontée du tas pour push et la descente du tas pour pop, puis construisez un tas à partir d’un tableau non trié en O(n) avec l’algorithme de Floyd.
Heapify, push et pop depuis zéro est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 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.
Construire une classe MinHeap
Implémenter un tas à partir de zéro démontre une bonne maîtrise de ses mécanismes internes et constitue parfois une question d'entretien pour un poste confirmé. Une classe MinHeap encapsule un tableau et expose les opérations push, pop, peek et size. En interne, elle maintient la propriété de tas en appelant la remontée dans le tas après push et la descente dans le tas après pop. Comprendre cette implémentation rend le module heapq de Python parfaitement transparent.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
def pop(self):
if len(self._data) == 1:
return self._data.pop()
min_val = self._data[0]
self._data[0] = self._data.pop() # move last to root
self._sift_down(0)
return min_val
def peek(self):
return self._data[0] if self._data else None
def size(self):
return len(self._data)
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
print('MinHeap class skeleton defined')Implémenter la remontée dans le tas
La remontée dans le tas compare un nœud à son parent et l'échange vers le haut tant que la propriété de tas (parent <= enfant dans un tas min) est violée. L'élément nouvellement inséré se trouve à la fin et remonte jusqu'à sa position correcte. La boucle while s'exécute au maximum floor(log n) fois, ce qui correspond à la hauteur de l'arbre. Affectez i = parent à chaque étape pour continuer à remonter.
class MinHeap:
def __init__(self):
self._data = []
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
def _sift_up(self, i):
while i > 0:
p = self._parent(i)
if self._data[p] > self._data[i]: # parent > child: swap
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else:
break # heap property satisfied
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
h = MinHeap()
for v in [5, 3, 8, 1, 4]:
h.push(v)
print(h._data) # valid min-heapImplémenter la descente dans le tas
La descente dans le tas fait descendre un nœud en l'échangeant successivement avec son enfant le plus petit (dans un tas min), jusqu'à ce qu'aucun enfant ne soit plus petit ou que le nœud atteigne une feuille. Comparez toujours les deux enfants et échangez le nœud avec le plus petit afin de préserver la propriété de tas. N'oubliez pas de vérifier que les indices des enfants sont dans les limites avant de comparer les valeurs.
def _sift_down(data, i):
n = len(data)
while True:
smallest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and data[l] < data[smallest]:
smallest = l
if r < n and data[r] < data[smallest]:
smallest = r
if smallest == i:
break # already the smallest among i, l, r
data[i], data[smallest] = data[smallest], data[i]
i = smallest
# Test: put a large value at root and sift down
heap = [10, 1, 2, 3, 4, 5, 6]
print('Before sift-down:', heap)
_sift_down(heap, 0)
print('After sift-down:', heap) # 1 should reach top, 10 sinkCompléter MinHeap avec pop
L'opération pop supprime et renvoie la racine (le minimum dans un tas min). Pour préserver la forme de l'arbre binaire complet, déplacez le dernier élément à la position de la racine, puis faites-le descendre dans le tas. Cela évite de créer des espaces vides dans le tableau et conserve une représentation valide. Cas particulier : s'il ne reste qu'un seul élément, effectuez pop et renvoyez-le directement, sans descente dans le tas.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] > self._data[i]:
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop() # last -> root
i, n = 0, len(self._data)
while True:
s, l, r = i, 2*i+1, 2*i+2
if l < n and self._data[l] < self._data[s]: s = l
if r < n and self._data[r] < self._data[s]: s = r
if s == i: break
self._data[i], self._data[s] = self._data[s], self._data[i]
i = s
return result
h = MinHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [1,2,3,4,5,8] sortedAlgorithme heapify de Floyd
L'algorithme de Floyd construit un tas min à partir d'un tableau non trié en O(n) en appelant la descente dans le tas sur chaque nœud qui n'est pas une feuille, en commençant par le dernier nœud interne (n//2 - 1) et en progressant vers la racine. Les feuilles sont déjà, par définition, des tas valides à un seul élément. La complexité en O(n) vient du fait que la plupart des nœuds se trouvent près du bas de l'arbre et ne doivent descendre que sur une courte distance.
def heapify(arr):
n = len(arr)
# Start from last non-leaf: index n//2 - 1
# Work backward to root (index 0)
for i in range(n // 2 - 1, -1, -1):
# Sift down node at index i
j = i
while True:
s = j
l, r = 2*j+1, 2*j+2
if l < n and arr[l] < arr[s]: s = l
if r < n and arr[r] < arr[s]: s = r
if s == j: break
arr[j], arr[s] = arr[s], arr[j]
j = s
return arr
arr = [9, 7, 5, 3, 1, 8, 2, 4, 6]
print('Before:', arr)
heapify(arr)
print('After (min-heap):', arr) # arr[0] should be 1Pourquoi l'algorithme de Floyd est en O(n)
Preuve de la complexité en O(n) : l'arbre possède n/2^(k+1) nœuds à la hauteur k. Chaque nœud situé à la hauteur k effectue au plus k échanges lors de la descente dans le tas. Travail total = somme sur toutes les hauteurs k : n/2^(k+1) * k. Cette série géométrique converge vers O(n). En comparaison, l'insertion naïve élément par élément coûte O(log n) pour chaque push ; n insertions coûtent donc O(n log n). L'algorithme de Floyd est strictement meilleur pour une construction par lots.
import time
import random
# Compare: O(n) heapify vs O(n log n) one-by-one
n = 100000
data = list(range(n, 0, -1)) # reverse sorted = worst case for push
# Method 1: Floyd's O(n)
data1 = data[:]
start = time.time()
for i in range(n // 2 - 1, -1, -1):
j = i
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n and data1[l] < data1[s]: s = l
if r < n and data1[r] < data1[s]: s = r
if s == j: break
data1[j], data1[s] = data1[s], data1[j]; j = s
print(f'Floyd heapify: {time.time()-start:.4f}s')
# Method 2: One-by-one insertion
import heapq
start = time.time()
heap = []
for x in data: heapq.heappush(heap, x)
print(f'Push one-by-one: {time.time()-start:.4f}s')Insérer dans une collection existante avec un tas
heapq.heappushpop et heapq.heapreplace de Python sont des opérations combinées efficaces. heappushpop(heap, item) insère le nouvel élément avec push, puis effectue immédiatement pop sur le plus petit élément, ce qui est plus efficace que deux appels distincts. heapreplace(heap, item) effectue pop sur le plus petit élément et insère le nouvel élément en une seule passe (pour être correcte, cette opération exige que le nouvel élément soit >= à l'ancien minimum). Ces opérations sont utiles dans les algorithmes de traitement en flux des k meilleurs éléments.
import heapq
heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)
# heappushpop: push 2, then pop minimum
# More efficient than push + pop separately
result = heapq.heappushpop(heap, 2)
print('heappushpop(2):', result, '| heap:', heap)
# heapreplace: pop minimum, then push new item
# New item does NOT need to be larger (different from heappushpop)
result2 = heapq.heapreplace(heap, 4)
print('heapreplace(4):', result2, '| heap:', heap)
# Use case: maintaining a fixed-size top-k heap
# heappushpop is the standard patternImplémenter un MaxHeap à partir de zéro
Un MaxHeap inverse la comparaison : le parent doit être supérieur ou égal à tous ses descendants. Il suffit d'inverser la comparaison dans la remontée et la descente dans le tas. Vous pouvez également encapsuler les valeurs dans une classe de négation ou inverser le signe des entiers, comme avec le module heapq de Python. Implémenter un tas à partir de zéro montre que les tas min et max ont une structure identique et que seul l'opérateur de comparaison change.
class MaxHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] < self._data[i]: # FLIP: parent < child = violation
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop()
i, n = 0, len(self._data)
while True:
g = i; l, r = 2*i+1, 2*i+2
if l < n and self._data[l] > self._data[g]: g = l # FLIP
if r < n and self._data[r] > self._data[g]: g = r # FLIP
if g == i: break
self._data[i], self._data[g] = self._data[g], self._data[i]; i = g
return result
h = MaxHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [8,5,4,3,2,1]Supprimer un élément arbitraire d'un tas
Supprimer un élément arbitraire (qui n'est pas la racine) d'un tas s'exécute en O(log n), mais nécessite de connaître l'indice de l'élément. Remplacez l'élément par le dernier, supprimez ce dernier, puis effectuez une remontée ou une descente dans le tas sur l'élément de remplacement (une seule direction violera la propriété de tas). Cette technique est utilisée dans l'algorithme de Dijkstra avec une suppression différée, ainsi que dans les files de priorité qui prennent en charge les opérations de diminution de clé.
def delete_at_index(heap, i):
n = len(heap)
heap[i] = heap[n - 1]
heap.pop()
if i >= len(heap):
return # deleted the last element
# Try sift-up first
p = (i - 1) // 2
if i > 0 and heap[i] < heap[p]:
while i > 0:
p = (i - 1) // 2
if heap[p] > heap[i]:
heap[p], heap[i] = heap[i], heap[p]; i = p
else: break
else: # sift down
j = i; n2 = len(heap)
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n2 and heap[l] < heap[s]: s = l
if r < n2 and heap[r] < heap[s]: s = r
if s == j: break
heap[j], heap[s] = heap[s], heap[j]; j = s
heap = [1, 3, 2, 7, 4, 5, 6]
print('Before:', heap)
delete_at_index(heap, 2) # delete element at index 2 (value=2)
print('After:', heap) # 2 removed, heap still validTas pour les K éléments les plus fréquents
Les K éléments les plus fréquents (LeetCode n° 347) utilise un tas min de taille k. Maintenez un tas min dont chaque entrée est de la forme (frequency, element). Traitez chaque élément distinct : si le tas contient moins de k éléments, effectuez push ; sinon, si la fréquence du nouvel élément dépasse le minimum du tas, effectuez pop puis push. Le tas final contient les k éléments les plus fréquents en O(n log k).
import heapq
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
# Min-heap of (frequency, num)
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap) # remove least frequent
return [num for freq, num in heap]
print(top_k_frequent([1,1,1,2,2,3], 2)) # [1, 2]
print(top_k_frequent([4,4,4,3,3,2,1], 2)) # [4, 3]Applications des tas en planification
Au-delà de la programmation compétitive, les tas sont au cœur des systèmes de planification utilisés dans le monde réel. Les ordonnanceurs de tâches des systèmes d’exploitation utilisent une file de priorité (un tas) pour toujours exécuter le processus prêt le plus prioritaire. Les simulations pilotées par événements traitent les événements dans l’ordre chronologique au moyen d’un tas min dont la clé est l’heure de l’événement. Les ordonnanceurs de paquets réseau donnent la priorité au trafic selon sa classe de qualité de service. Comprendre le tas vous fournit un modèle mental de tous ces systèmes et ce sujet revient naturellement dans les entretiens de conception de systèmes portant sur les files d’attente et la planification.
import heapq
# Simple event-driven simulation using a heap
events = [] # (time, event_description)
def schedule(time, event):
heapq.heappush(events, (time, event))
def process_next():
time, event = heapq.heappop(events)
print(f't={time}: {event}')
return time, event
# Schedule events out of order:
schedule(10, 'Send email')
schedule(3, 'Open app')
schedule(7, 'Process request')
schedule(1, 'Start server')
# Process in time order:
while events:
process_next()
# Output: t=1, t=3, t=7, t=10 -- always in time orderVérification rapide
Testez votre compréhension des concepts de Structures de données et 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 à créer MinHeap et MaxHeap à partir de zéro avec les opérations de remontée et de descente, l’algorithme heapify de Floyd en O(n) et pourquoi il est plus efficace qu’une insertion élément par élément en O(n log n), ainsi que des applications pratiques, notamment les éléments les plus fréquents et la suppression à un indice. Ensuite, nous découvrirons le module heapq de Python et les astuces liées aux tas max.
Apprends Coding Interview Prep avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 90
- Leçons
- 360
Questions Fréquemment Posées
La leçon « Heapify, push et pop depuis zéro » est-elle gratuite ?
Oui — le texte complet de « Heapify, push et pop depuis zéro » 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 « Heapify, push et pop depuis zéro » ?
Implémentez la remontée du tas pour push et la descente du tas pour pop, puis construisez un tas à partir d’un tableau non trié en O(n) avec l’algorithme de Floyd. 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 2 sur 4.
Combien de temps prend la leçon « Heapify, push et pop depuis zéro » ?
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
- Propriété des tas et représentation par tableau
- Heapify, push et pop depuis zéro
- heapq de Python et astuces pour les tas max
- Médiane d’un flux de données et fusion k-voies