Fibonacciho halda

Fibonacci Heap

  • Introduction

  • Insert and Extract Min

  • Decrease Key

  • Rank

  • Meld and Delete

Halda s vícero stromy. Kořeny stromů jsou uloženy jako cyklický spojovaný seznam.

Každá posloupnost operací Insert, Extract-Min a Decrease-Key, která zahrnuje Insertů, má složitost .

— Fredman-Tarjan

Původně vznikla, aby vylepšila časovou složitost Dijkstrova algoritgmu z na .