Publication

Fibonacci Heaps

2006
Student Projects

Résumé

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, Insert, Union, ExtractMin, DecreaseKey and Delete. Fibonacci heaps are similar to binomial heaps,howevere it figured that they had a better performance in what regards the amortized analysis, These methods have a cost of O(1) except for ExtractMin and Delete (O(lg n)) Fibonacci heaps are used to improve the cost of Dijikstra and Prim. We implemented first the algorithms of Binomial and Fibonacci. We then used ExtractMin of fibonacci so as to implement Prim and Dijikstra. We have made a bonus algorithm , Kruskal who is also a "Minimum Spanning Tree" algorithm.

Source officielle

https://infoscience.epfl.ch/entities/publication/de334c00-7842-4ff7-a9fa-59226efee720

À 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.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

2006
Student Projects

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/de334c00-7842-4ff7-a9fa-59226efee720

À propos de ce résultat

Concepts associés (32)

Tas binomial

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.

Tas (informatique)

vignette|Un exemple de tas. Il contient 9 éléments. L'élément le plus prioritaire (100) est à la racine. En informatique, un tas (ou monceau au Canada, heap en anglais) est une structure de données de type arbre qui permet de retrouver directement l'élément que l'on veut traiter en priorité. C'est un arbre binaire presque complet ordonné. Un arbre binaire est dit presque complet si tous ses niveaux sont remplis, sauf éventuellement le dernier, qui doit être rempli sur la gauche (cf. Contre-exemples).

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.

Afficher plus

Publications associées (31)

Afficher plus

Fibonacci Heaps

Chattez avec Graph Search

Time-Space Trade-Offs for Sumcheck

FairTree: Subgroup Fairness Auditing of Machine Learning Models with Bias-Variance Decomposition

Probabilistic Methods for Joint Eigenvalue Problems with Applications