Exercices de programmation pour classes préparatoires
Une file de priorite (min-heap) permet d'inserer des elements et d'extraire le plus petit en temps logarithmique. Elle peut etre representee par un tableau vu comme un arbre binaire quasi-complet : pour un element a l'indice i, son fils gauche est a l'indice 2*i + 1 et son fils droit a l'indice 2*i + 2.
Ecrire une fonction tas_ops(operations) qui simule une file de priorite a l'aide d'un tas binaire implemente a la main (sans utiliser le module heapq ni sorted/sort). La fonction renvoie la liste des valeurs extraites.
Chaque operation est un tuple :
- ("insert", valeur) : insere valeur dans le tas.
- ("extract_min",) : retire et renvoie le minimum du tas.
On garantit qu'aucun extract_min n'est appele sur un tas vide.
| Appel | Résultat attendu |
|---|---|
| tas_ops([('insert', 3), ('insert', 1), ('insert', 2), ('extract_min',)]) | [1] |
| tas_ops([('insert', 5), ('insert', 2), ('insert', 8), ('extract_min',), ('extract_min',)]) | [2, 5] |
Connectez-vous pour soumettre du code.