La file de priorité de Brodal (Brodal queue) est une file de priorité introduite par Gerth Stølting Brodal en 1996. Elle constitue la première structure de ce type à atteindre simultanément les bornes asymptotiques optimales en pire cas pour les opérations fondamentales :

Opération Complexité Insertion, recherche du minimum, fusion, diminution de clé Suppression du minimum, suppression d'un élément

Contrairement aux tas de Fibonacci, ces bornes sont garanties en pire cas et non amorties.

La structure repose sur deux arbres ordonnés satisfaisant un ensemble complexe d'invariants. Certaines violations temporaires de la propriété de tas sont autorisées puis corrigées progressivement afin de maintenir les garanties de complexité.

Version fonctionnelle

Gerth Stølting Brodal et Chris Okasaki ont proposé une version persistante et purement fonctionnelle de la structure, conservant les mêmes bornes asymptotiques.

Applications

La file de priorité de Brodal présente principalement un intérêt théorique. Elle démontre qu'il est possible de combiner des opérations de fusion et de diminution de clé en temps constant avec des garanties optimales en pire cas. En pratique, sa complexité d'implémentation conduit généralement à lui préférer des structures plus simples telles que les tas binomiaux, les tas de Fibonacci ou les tas à appariement.

Références

Catégorie:Arbre (structure de données)