Tas de Fibonacci

En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d'exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la première fois dans un journal scientifique en 1987. Les tas de Fibonacci sont utilisés pour améliorer le temps asymptotique de l'algorithme de Dijkstra, qui calcule les plus courts chemins dans un graphe, et de l'algorithme de Prim, qui calcule l'arbre couvrant de poids minimal d'un graphe. Le nom de tas de Fibonacci vient des nombres de Fibonacci, qui sont utilisés pour calculer son temps d'exécution. En particulier, les opérations insertion, trouver le minimum, décroître une clé, et union ont toutes un coût amorti constant. Les opérations supprimer et supprimer le minimum ont un coût amorti en O(log n). C'est-à-dire qu'en partant d'une structure vide, n'importe quelle séquence de a opérations du premier groupe et b opérations du second groupe prendrait un temps O(a + (b log n)). Dans un tas binomial, une telle séquence d'opérations prendrait un temps O((a + b)(log n)). Il devient donc plus intéressant d'utiliser un tas de Fibonacci plutôt qu'un tas binomial lorsque b est asymptotiquement plus petit que a. Un tas de Fibonacci est un ensemble d'arbres satisfaisant la propriété de tas-minimum, c'est-à-dire que la clé d'un fils est toujours supérieure ou égale à la clé de son père. Ceci implique que la clé minimum est toujours à la racine d'un des arbres. La structure des tas de Fibonacci est plus flexible que celle des tas binomiaux, en ce sens qu'elle permet à quelques opérations d'être exécutées de manière « paresseuse », en reportant le travail sur des opérations ultérieures. Par exemple, l'union de deux tas est effectuée simplement en concaténant les deux listes d'arbres, et l'opération de diminution de clé coupe parfois un nœud de son père pour former un nouvel arbre. Cependant, à un moment donné il est nécessaire d'introduire un certain ordre dans la structure du tas de manière à obtenir le temps d'exécution voulu.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Concepts associés (9)

Cours associés (6)

Séances de cours associées (60)

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

ME-213: Programmation pour ingénieur

Mettre en pratique les bases de la programmation vues au semestre précédent. Développer un logiciel structuré. Méthode de debug d'un logiciel. Introduction à la programmation scientifique. Introductio

CS-119(c): Information, Computation, Communication

L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (

Fibonacci Heaps

Ali Chekir, Mohamed Slim Slama

Binomial heaps are data structures implemented as a collection of binomial trees, (A binomial tree of order K can be constructed from two trees of order (K-1)). They can implement several methods: Min

2006

En informatique, un tas binomial est une structure de données assez proche du tas binaire, mais qui permet aussi de fusionner deux tas rapidement. Ainsi, il supporte les opérations suivantes, toutes en O(log n) : insérer un nouvel élément au tas ; trouver l'élément de plus petite clé ; effacer du tas l'élément de plus petite clé ; diminuer la clé d'un élément donné ; effacer un élément donné du tas ; fusionner deux tas en un seul. Le tas binomial est donc une implémentation du type abstrait tas fusionnable, c'est-à-dire une permettant des opérations de fusion.

A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations (assuming a min-heap): find-min: simply return the top element of the heap.

Multiplication matricielle et Heap Data Structure CS-250: Algorithms

Couvre l'algorithme de division et de conquête pour la multiplication matricielle et introduit la structure de données de tas (binaire).

Gestion de la mémoire et programmes d'accident ME-213: Programmation pour ingénieur

Couvre la gestion de la mémoire pour les ingénieurs, en se concentrant sur les programmes d'accident liés aux erreurs d'accès à la mémoire.

Gestion de la mémoire: raisons et solutions de crash ME-213: Programmation pour ingénieur

Plonge dans les raisons derrière les pannes de programme liées à la gestion de la mémoire.