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

PropertyValue
prop-cs:wikiPageUsesTemplate
dbpedia-owl: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 Michael L. Fredman 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ě.
dbpedia-owl:thumbnail
dbpedia-owl:wikiPageExternalLink
dbpedia-owl:wikiPageID
  • 223573 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 9191 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 29 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 16352308 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
dbpedia-owl:wikiPageWikiLinkText
  • Fibonacciho haldy
  • Fibonacciho
  • Fibonacciho halda
  • Fibbonaciho haldy
dcterms:subject
rdfs:comment
  • 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).
rdfs:label
  • Fibonacciho halda
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbpedia-owl:wikiPageRedirects of
is dbpedia-owl:wikiPageWikiLink of
is foaf:primaryTopic of