README

Fibonacci堆是一种具有最佳摊销运行时间的堆数据结构。它由Michael L. Fredman和Robert E. Tarjan于1984年开发。通过使用Fibonacci堆，Dijkstra算法的运行时间可以提高至O(|E| + |V| log |V|)。

安装

composer require mathieuviossat/fibonacci-heap

{
    "require": {
        "mathieuviossat/fibonacci-heap": "~1.0.0"
    }
}

示例

use MathieuViossat\Util\FibonacciHeap;

$movies = new FibonacciHeap();

$movies->insert(4, 'The Phantom Menace');
$movies->insert(5, 'Attack of the Clones');
$movies->insert(6, 'Revenge of the Sith');
$movies->insert(1, 'A New Hope');
$movies->insert(2, 'The Empire Strikes Back');
$movies->insert(3, 'Return of the Jedi');
$movies->insert(7, 'The Force Awakens');

while ($movie = $movies->extractMin())
    echo $movie->getKey() . ' - ' . $movie->getData() . PHP_EOL;

方法

minimum() : FibonacciHeapElement

返回具有最低键值的元素，或者如果堆为空，则返回null。
复杂度：Θ(1)

insert(int|float $key, mixed $data) : FibonacciHeapElement

在堆中插入具有优先级$key的数据，并返回该元素。
复杂度：Θ(1)

extractMin() : FibonacciHeapElement

从堆中删除具有最低优先级的元素，并返回它。
摊销复杂度：O(log n)

decreaseKey(FibonacciHeapElement $element, int|float $key) : void

将$element的键替换为$key。$key必须低于旧键。
摊销复杂度：Θ(1)

delete(FibonacciHeapElement $element) : void

从堆中删除$element。
摊销复杂度：O(log n)

merge(FibonacciHeap $other) : void

合并两个堆。合并后，建议只使用其中一个。
复杂度：Θ(1)

isEmpty() : bool

如果堆为空，则返回true，否则返回false。
复杂度：Θ(1)

size() / count() / count($heap) : int

返回堆中的元素数量。
复杂度：Θ(1)

clear() : void

从堆中删除所有元素。
复杂度：Θ(1)

许可证

此库在MIT许可证下发布。

mathieuviossat / fibonacci-heap

维护者

详细信息