Download the PHP package mathieuviossat/fibonacci-heap without Composer
On this page you can find all versions of the php package mathieuviossat/fibonacci-heap. It is possible to download/install these versions without Composer. Possible dependencies are resolved automatically.
Download mathieuviossat/fibonacci-heap
More information about mathieuviossat/fibonacci-heap
Files in mathieuviossat/fibonacci-heap
Package fibonacci-heap
Short Description PHP implementation of the Fibonacci heap
License MIT
Homepage https://github.com/MathieuViossat/fibonacci-heap
Informations about the package fibonacci-heap
Fibonacci heap
The Fibonacci heap is a heap data structure with the best amortized running time. It was developed by Michael L. Fredman and Robert E. Tarjan in 1984. The running time of Dijkstra's algorithm can be improved to O(|E| + |V| log |V|) by using a Fibonacci heap.
Installation
Example
Methods
minimum() : FibonacciHeapElement
Returns the element with the lowest key, or null if the heap is empty.
Complexity: Θ(1)
insert(int|float $key, mixed $data) : FibonacciHeapElement
Inserts $data with the priority $key in the heap and return the element.
Complexity: Θ(1)
extractMin() : FibonacciHeapElement
Deletes the element with the lowest priority from the heap and return it.
Amortized complexity: O(log n)
decreaseKey(FibonacciHeapElement $element, int|float $key) : void
Replaces $element's key by $key. $key must be lower than the old key.
Amortized complexity: Θ(1)
delete(FibonacciHeapElement $element) : void
Deletes $element from the heap.
Amortized complexity: O(log n)
merge(FibonacciHeap $other) : void
Merges the both heaps. I recommend to only use one of them after that.
Complexity: Θ(1)
isEmpty() : bool
Retuns true if the heap is empty, false otherwise.
Complexity: Θ(1)
size() / count() / count($heap) : int
Retuns the number of elements in the heap.
Complexity: Θ(1)
clear() : void
Removes all elements from the heap.
Complexity: Θ(1)
License
This library is published under The MIT License.