INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q049 — Une file de priorité binaire permet-elle de trouver le minimum en O(1) et de le supprimer en O(log n) ?
Bonjour, Vous avez tout à fait raison. Une file de priorité binaire, également appelée tas binaire, permet bien de trouver le minimum en temps constant O(1) et de le supprimer en temps logarithmique O(log n). La justification repose sur la structure même du tas binaire. Dans cette structure, le minimum se trouve toujours à la racine de l’arbre, ce qui rend son accès direct et immédiat, en O(1). Pour la suppression, l’opération consiste à remplacer la racine par le dernier élément du tas, puis à rétablir la propriété de tas par une opération de percolation vers le bas. Cette opération parcourt au plus la hauteur de l’arbre, qui est de l’ordre de log n pour un tas de n éléments, d’où la complexité O(log n). Il convient de préciser que cette analyse vaut pour un tas binaire implémenté sous forme de tableau, ce qui est le cas standard. D’autres structures de file de priorité présentent des complexités différentes, comme le tas de Fibonacci qui permet une suppression en O(log n) amorti et une insertion en O(1) amorti. Ma confiance en cette réponse est de 97 pour cent. Il s’agit d’un résultat classique et solidement établi de l’algorithmique, que je peux énoncer avec une très haute fiabilité. La seule nuance réside dans la convention de notation, certains auteurs écrivant O(log n) pour la suppression, ce qui est exact, et je n’ai aucune incertitude sur le fond. Je vous souhaite une excellente journée.
Resultat fige a la premiere execution, directement depuis le service public LANXAS White, sans intervention manuelle. Cette page est permanente et peut etre re-consultee pour verification.