| dbpedia-owl:abstract
|
- In der Informatik ist ein Fibonacci-Heap eine Datenstruktur, ähnlich zu einem Binomial-Heap, die sich als Vorrangwarteschlange einsetzen lässt. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge effizient in den Heap hinein gelegt werden können und stets ein Element mit höchster Priorität entnommen werden kann. Im Unterschied zu Binomial-Heaps benötigen fast alle Operationen amortisiert nur konstante Laufzeit. Die Priorität der Elemente wird diesen durch Schlüssel aufgeprägt. Über der Menge der Schlüssel muss daher eine Totalordnung bestehen, wie sie zum Beispiel die Kleiner-Relation (<) über den ganzen Zahlen darstellt. Fibonacci-Heaps wurden erstmals 1984 von Michael L. Fredman und Robert Tarjan beschrieben. Ihr Name rührt von der Analyse der Datenstruktur her, bei der Fibonacci-Zahlen eine große Rolle spielen.
- In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987. The name of Fibonacci heap comes from Fibonacci numbers which are used in the running time analysis. Find-minimum is O(1) amortized time. Operations insert, decrease key, and merge (union) work in constant amortized time. Operations delete and delete minimum work in O(log n) amortized time. This means that starting from an empty data structure, any sequence of a operations from the first group and b operations from the second group would take O(a + b log n) time. In a binomial heap such a sequence of operations would take O(log) time. A Fibonacci heap is thus better than a binomial heap when b is asymptotically smaller than a. Using Fibonacci heaps for priority queues improves the asymptotic running time of important algorithms, such as Dijkstra's algorithm for computing Shortest paths.
- En Informática, un Montículo de Fibonacci (o Heap de Fibonacci) es una estructura de datos subconjunto de los montículos, que a su vez, son un subconjunto especial dentro de los bosques de árboles. Resulta similar a un montículo binomial, pero dispone de una mejor relación entre el coste y su amortización. Los montículos de Fibonacci fueron desarrollados en 1984 por Michael L. Fredman y Robert E. Tarjan y publicados por primera vez en una revista científica en 1987. El nombre de montículos de Fibonacci viene de la sucesión de Fibonacci, que se usa en pruebas comparativas de tiempo. En particular, las operaciones Insertar, Encontrar el mínimo, Decrementar la clave, y la Unión trabajan con tiempo constante amortizado. Las operaciones Borrar y Borrar el mínimo tienen un coste O(log n) como coste amortizado. Esto significa que, empezando con una estructura de datos vacía, cualquier secuencia de a operaciones del primer grupo y b operaciones del segundo grupo tardarían O(a + b log n). En un montículo binomial cualquier secuencia de operaciones tardarían O(log). Un montículo de Fibonacci es mejor que un montículo binomial cuando b es asintóticamente más pequeño que a. El montículo de Fibonacci puede ser utilizado para mejorar el tiempo de ejecución asintótico del algoritmo de Dijkstra para calcular el camino más corto en un grafo y el algoritmo de Prim para calcular el árbol mínimo de un grafo.
- フィボナッチヒープ（Fibonacci heap）とは、計算機科学におけるデータ構造（ヒープ）の1つ。
- Fibonacci heap, förbättring av datastrukturen heap som bland annat medför snabbare insättning av element och möjlighet att implementera snabbare algoritmer för minimalt uppspännande träd. Strukturen implementerades första gången 1986 av Michael Fredman och Robert Tarjan. En Fibonacci heap kallas ibland kort och gott för F-heap
- 斐波那契堆(Fibonacci heap)是计算机科学中最小堆有序树的集合。它和二项式堆有类似的性质，可用于实现合并优先队列。
- Фибоначчиева куча — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году. Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное (для двоичной кучи и биномиальной кучи амортизационное время работы равно). Кроме стандартных операций,, фибоначчиева куча позволяет за время выполнять операцию слияния двух куч.
- 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. 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 +). Dans un tas binomial, une telle séquence d'opérations prendrait un temps O. 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.
|
| rdfs:comment
|
- フィボナッチヒープ（Fibonacci heap）とは、計算機科学におけるデータ構造（ヒープ）の1つ。
- Fibonacci heap, förbättring av datastrukturen heap som bland annat medför snabbare insättning av element och möjlighet att implementera snabbare algoritmer för minimalt uppspännande träd. Strukturen implementerades första gången 1986 av Michael Fredman och Robert Tarjan. En Fibonacci heap kallas ibland kort och gott för F-heap
- 斐波那契堆(Fibonacci heap)是计算机科学中最小堆有序树的集合。它和二项式堆有类似的性质，可用于实现合并优先队列。
- In der Informatik ist ein Fibonacci-Heap eine Datenstruktur, ähnlich zu einem Binomial-Heap, die sich als Vorrangwarteschlange einsetzen lässt. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge effizient in den Heap hinein gelegt werden können und stets ein Element mit höchster Priorität entnommen werden kann. Im Unterschied zu Binomial-Heaps benötigen fast alle Operationen amortisiert nur konstante Laufzeit.
- In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987. The name of Fibonacci heap comes from Fibonacci numbers which are used in the running time analysis. Find-minimum is O(1) amortized time.
- En Informática, un Montículo de Fibonacci (o Heap de Fibonacci) es una estructura de datos subconjunto de los montículos, que a su vez, son un subconjunto especial dentro de los bosques de árboles. Resulta similar a un montículo binomial, pero dispone de una mejor relación entre el coste y su amortización. Los montículos de Fibonacci fueron desarrollados en 1984 por Michael L. Fredman y Robert E. Tarjan y publicados por primera vez en una revista científica en 1987.
- Фибоначчиева куча — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году. Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное (для двоичной кучи и биномиальной кучи амортизационное время работы равно).
- 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.
|
