| dbo:abstract
|
- Fibonacciho halda je druh haldy. Principiálně vychází z binomiální haldy. Hlavní výhodou Fibonacciho haldy je nízká asymptotická složitost prováděných algoritmů. Operace vložení, hledání minima, snížení hodnoty klíče a spojování stromů probíhají v konstantním čase, amortizovaně O(1). Operace mazání a mazání minimálního prvku pracuje s časovou složitostí O(log n), přičemž k výraznému zrychlení výpočtů oproti binomiální haldě dochází zejména v momentě, kdy některá z větví stromu neobsahuje žádná data. Mezi nejčastější aplikace Fibonacciho haldy patří Jarníkův a Dijkstrův algoritmus, které slouží k vyhledávání minimální kostry grafu a k určení nejkratší cesty v grafu. Pojem Fibonacciho haldy zavedli a Robert E. Tarjan v roce 1984 a poprvé jej publikovali v roce 1987 ve vědeckých časopisech. Označení Fibonacciho halda vychází z Fibonacciho čísel, která mají souvislost s počtem vrcholů v každém stromě. Obrázek 1: Počty vrcholů stromů F0, F1, … tvoří Fibonacciho posloupnost (cs)
- In der Informatik ist ein Fibonacci-Heap (englisch heap ‚Halde‘) eine Datenstruktur, ähnlich einem Binomial-Heap, die eine Vorrangwarteschlange realisiert. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge effizient im Heap gespeichert werden können und stets ein Element mit höchster Priorität entnommen werden kann. 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-Gleich-Relation (≤) über den ganzen Zahlen darstellt. Fibonacci-Heaps wurden erstmals 1984 von und Robert E. Tarjan beschrieben. Ihr Name rührt von der Analyse der Datenstruktur her, bei der Fibonacci-Zahlen eine große Rolle spielen. (de)
- In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis. For the Fibonacci heap, the find-minimum operation takes constant (O(1)) amortized time. The insert and decrease key operations also work in constant amortized time. Deleting an element (most often used in the special case of deleting the minimum element) works in O(log n) amortized time, where n is the size of the heap. This means that starting from an empty data structure, any sequence of a insert and decrease key operations and b delete operations would take O(a + b log n) worst case time, where n is the maximum heap size. In a binary or binomial heap, such a sequence of operations would take O((a + b) log n) time. A Fibonacci heap is thus better than a binary or binomial heap when b is smaller than a by a non-constant factor. It is also possible to merge two Fibonacci heaps in constant amortized time, improving on the logarithmic merge time of a binomial heap, and improving on binary heaps which cannot handle merges efficiently. Using Fibonacci heaps for priority queues improves the asymptotic running time of important algorithms, such as Dijkstra's algorithm for computing the shortest path between two nodes in a graph, compared to the same algorithm using other slower priority queue data structures. (en)
- 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 (Benchmarking). 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((a + b)log (n)). 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. (es)
- 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. (fr)
- フィボナッチヒープ（英: Fibonacci heap）とは、計算機科学におけるデータ構造（ヒープ）の1つ。 フィボナッチヒープの名前は、処理時間を解析する際にフィボナッチ数が使用されたことによる。 (ja)
- 피보나치 힙(Fibonacci heap) 자료구조는 두 가지 목적으로 사용된다. 첫째는 “병합 가능한 힙”의 몇가지 연산 지원이며, 둘째는 분할 상환을 빈번히 수행하는 응용 프로그램에 매우 적합하도록 상수의 분할 상환 시간을 가지는 것이다.컴퓨터 과학(computer science)에서 피보나치 힙(Fibonacci heap)은 우선순위 큐(priority queue) 연산을 위한 자료 구조로, 힙-정렬된 트리를 모아놓은 자료 구조이다. 이진 힙(binary heap) 및 이항 힙(binomial heap) 등 다른 많은 우선순위 큐 자료구조에 비해 더 나은 분할 상환된 실행 시간(amortized running time)을 보인다. 피보나치 힙은 Michael L. Fredman과 Robert E. Tarjan이 1984년 개발하였고, 1987년 과학 저널에 발표하였다. 이들은 실행 시간 분석에 피보나치 수가 사용된 것을 따라 피보나치 힙이라 명명하였다. 피보나치 힙에서, 최솟값 탐색(find-minimum) 연산은 분할 상환된 시간이 상수인(O(1)) 만큼 소요된다. 삽입 연산(insert) 및 키 감소 연산(decrease key operation) 또한 상수 분할 상환 시간동안 동작한다. 힙의 크기가 n일때, 구성요소의 삭제는 O(log n) 만큼의 분할 상환 시간이 걸린다. (삭제 연산은 대부분 최소 구성요소를 삭제하는 특수한 경우에 사용된다) 이것은 최대 힙 크기가 n일때, 빈 자료구조부터 시작하여 합쳐서 a개의 삽입연산, 키 감소 연산과 b개의 삭제연산을 임의의 순서대로 수행했을 때 최악의 경우 O(a + b log n) 만큼의 시간이 소요됨을 의미한다. 이진 힙 또는 이항 힙이라면, 이러한 순서의 연산은 O((a + b) log n)의 시간이 소요될 것이다. 그러므로 비상수 요소에 의해 b가 a보다 작을 경우, 피보나치 힙은 이진 힙 또는 이항 힙보다 더 낫다. 두 피보나치 힙을 상수 분할 상환 시간 안에 병합하는 것 또한 가능하다. 이것은 이항 힙의 경우 병합 시간이 O(log n)만큼 소요되는데 이것보다 개선된 것이고, 이진 힙의 경우는 병합을 효율적으로 처리하지 못하는데 이에 비하면 개선된 것이다.우선순위 큐에 대해 피보나치 힙을 사용함으로써, 다른 더 느린 우선순위 큐 자료구조를 사용하는 동일한 알고리즘에 비해 그래프 내 두 노드 사이의 최단거리를 계산하는 데이크스트라 알고리즘 같은 중요한 알고리즘의 점근적 실행시간을 개선하는 효과를 가져온다. (ko)
- W informatyce kopiec Fibonacciego to struktura danych realizująca operacje kolejki priorytetowej, składająca się z kolekcji drzew z porządkiem kopcowym. Kopce te mają lepszy czas zamortyzowany, niż wiele innych implementacji kolejek priorytetowych, w tym kopce binarne i dwumianowe. Michael L. Friedman i Robert E. Tarjan odkryli kopce Fibonacciego w 1984 roku i opublikowali ich opis w czasopiśmie naukowym w 1987 roku. Nazwali je kopcami Fibonacciego w nawiązaniu do liczb Fibonacciego, które są używane do ich analizy. Dla kopców Fibonacciego operacja znalezienia minimum zajmuje czas stały (O(1)) w sensie zamortyzowanym. podobnie jak operacje wstawiania oraz zmniejszania klucza. Usuwanie elementu (najczęściej jest używany w specjalnym przypadku usuwania minimalnego elementu) działa w czasie zamortyzowanym O(log n), gdzie n to rozmiar stosu. Oznacza to, że zaczynając od pustej struktury, dowolny ciąg a operacji wstawiania oraz zmniejszania kluczy i b operacji usunięć zajmie O(a + b log n) czasu (najgorszy przypadek), gdzie n to maksymalny rozmiar kopca. Taki sam ciąg operacji w kopcu dwumianowym miałby złożoność O((a+b) log n). Możliwa jest także operacja łączenia dwóch kopców Fibonacciego w stałym czasie (zamortyzowanym). Implementacja kolejki priorytetowej w oparciu o kopce Fibonacciego poprawia złożoność wielu ważnych algorytmów, takich jak algorytm Dijkstry do obliczania najkrótszej ścieżki między dwoma węzłami grafu. (pl)
- Fibonacci heap är en term inom datavetenskapen och gäller köhantering av datastrukturen heap. I förhållande till tidigare binära och binomala köhanteringar innebär hanteringen via Fibonaccital en mer effektiv datahantering, med snabbare insättning av element och möjlighet att implementera snabbare algoritmer för minimalt uppspännande träd. Fibonacci heap utvecklades av och 1984 och beskrevs i en artikel i tidskriften Journal of the Association for Computing Machinery 1987. Metoden kallas ibland kort och gott för F-heap. (sv)
- 斐波那契堆（Fibonacci heap）是计算机科学中树的集合。它比二项堆具有更好的平摊分析性能，可用于实现合并优先队列。不涉及删除元素的操作有O(1)的平摊时间。 Extract-Min和Delete的数目和其它相比，较小时效率更佳。稠密图每次decrease key只要O(1)的平摊时间，和二项堆的O(lg n)相比是巨大的改进。 斐波纳契堆于1984年由与Robert E. Tarjan提出，1987年公开发表。名字来源于运行时分析使用的斐波那契数。 (zh)
- Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году. Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное (для двоичной кучи и биномиальной кучи амортизационное время работы равно ).Кроме стандартных операций INSERT, MIN, DECREASE-KEY, фибоначчиева куча позволяет за время выполнять операцию UNION слияния двух куч. (ru)
- Купа Фібоначчі — структура даних, ефективна реалізація черги з пріоритетом. З теоретичної точки зору купи Фібоначчі особливо варто використовувати, коли кількість Extract-Min і Delete операцій мала порівняно з кількістю інших операцій. Наприклад, деякі алгоритми на графах можуть викликати Decrease-Key на кожному ребрі. Для щільного графу сталий амортизаційний час кожного виклику Decrease-Key складається у велику перевагу в порівнянні з логарифмічним часом у найгіршому випадку в бінарній купі. Це можна побачити на прикладі алгоритмів про найкоротші шляхи з одного входу і мінімального кістякового дерева. З практичної точки зору сталий множник прихований у складності алгоритму і складність у програмуванні купи Фібоначчі роблять її менш бажаною, ніж звичайну бінарну або d-арну купу для більшості застосувань. (uk)
|
| rdfs:comment
|
- In der Informatik ist ein Fibonacci-Heap (englisch heap ‚Halde‘) eine Datenstruktur, ähnlich einem Binomial-Heap, die eine Vorrangwarteschlange realisiert. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge effizient im Heap gespeichert werden können und stets ein Element mit höchster Priorität entnommen werden kann. 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-Gleich-Relation (≤) über den ganzen Zahlen darstellt. Fibonacci-Heaps wurden erstmals 1984 von und Robert E. Tarjan beschrieben. Ihr Name rührt von der Analyse der Datenstruktur her, bei der Fibonacci-Zahlen eine große Rolle spielen. (de)
- フィボナッチヒープ（英: Fibonacci heap）とは、計算機科学におけるデータ構造（ヒープ）の1つ。 フィボナッチヒープの名前は、処理時間を解析する際にフィボナッチ数が使用されたことによる。 (ja)
- Fibonacci heap är en term inom datavetenskapen och gäller köhantering av datastrukturen heap. I förhållande till tidigare binära och binomala köhanteringar innebär hanteringen via Fibonaccital en mer effektiv datahantering, med snabbare insättning av element och möjlighet att implementera snabbare algoritmer för minimalt uppspännande träd. Fibonacci heap utvecklades av och 1984 och beskrevs i en artikel i tidskriften Journal of the Association for Computing Machinery 1987. Metoden kallas ibland kort och gott för F-heap. (sv)
- 斐波那契堆（Fibonacci heap）是计算机科学中树的集合。它比二项堆具有更好的平摊分析性能，可用于实现合并优先队列。不涉及删除元素的操作有O(1)的平摊时间。 Extract-Min和Delete的数目和其它相比，较小时效率更佳。稠密图每次decrease key只要O(1)的平摊时间，和二项堆的O(lg n)相比是巨大的改进。 斐波纳契堆于1984年由与Robert E. Tarjan提出，1987年公开发表。名字来源于运行时分析使用的斐波那契数。 (zh)
- Fibonacciho halda je druh haldy. Principiálně vychází z binomiální haldy. Hlavní výhodou Fibonacciho haldy je nízká asymptotická složitost prováděných algoritmů. Operace vložení, hledání minima, snížení hodnoty klíče a spojování stromů probíhají v konstantním čase, amortizovaně O(1). Operace mazání a mazání minimálního prvku pracuje s časovou složitostí O(log n), přičemž k výraznému zrychlení výpočtů oproti binomiální haldě dochází zejména v momentě, kdy některá z větví stromu neobsahuje žádná data. Obrázek 1: Počty vrcholů stromů F0, F1, … tvoří Fibonacciho posloupnost (cs)
- In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis. (en)
- 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 (Benchmarking). (es)
- 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. (fr)
- 피보나치 힙(Fibonacci heap) 자료구조는 두 가지 목적으로 사용된다. 첫째는 “병합 가능한 힙”의 몇가지 연산 지원이며, 둘째는 분할 상환을 빈번히 수행하는 응용 프로그램에 매우 적합하도록 상수의 분할 상환 시간을 가지는 것이다.컴퓨터 과학(computer science)에서 피보나치 힙(Fibonacci heap)은 우선순위 큐(priority queue) 연산을 위한 자료 구조로, 힙-정렬된 트리를 모아놓은 자료 구조이다. 이진 힙(binary heap) 및 이항 힙(binomial heap) 등 다른 많은 우선순위 큐 자료구조에 비해 더 나은 분할 상환된 실행 시간(amortized running time)을 보인다. 피보나치 힙은 Michael L. Fredman과 Robert E. Tarjan이 1984년 개발하였고, 1987년 과학 저널에 발표하였다. 이들은 실행 시간 분석에 피보나치 수가 사용된 것을 따라 피보나치 힙이라 명명하였다. (ko)
- W informatyce kopiec Fibonacciego to struktura danych realizująca operacje kolejki priorytetowej, składająca się z kolekcji drzew z porządkiem kopcowym. Kopce te mają lepszy czas zamortyzowany, niż wiele innych implementacji kolejek priorytetowych, w tym kopce binarne i dwumianowe. Michael L. Friedman i Robert E. Tarjan odkryli kopce Fibonacciego w 1984 roku i opublikowali ich opis w czasopiśmie naukowym w 1987 roku. Nazwali je kopcami Fibonacciego w nawiązaniu do liczb Fibonacciego, które są używane do ich analizy. (pl)
- Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году. (ru)
- Купа Фібоначчі — структура даних, ефективна реалізація черги з пріоритетом. З теоретичної точки зору купи Фібоначчі особливо варто використовувати, коли кількість Extract-Min і Delete операцій мала порівняно з кількістю інших операцій. Наприклад, деякі алгоритми на графах можуть викликати Decrease-Key на кожному ребрі. Для щільного графу сталий амортизаційний час кожного виклику Decrease-Key складається у велику перевагу в порівнянні з логарифмічним часом у найгіршому випадку в бінарній купі. Це можна побачити на прикладі алгоритмів про найкоротші шляхи з одного входу і мінімального кістякового дерева. З практичної точки зору сталий множник прихований у складності алгоритму і складність у програмуванні купи Фібоначчі роблять її менш бажаною, ніж звичайну бінарну або d-арну купу для більш (uk)
|
