search

danielborowski / fibonacci-heap-python

Implementation of a Fibonacci heap in Python
MIT License
90 stars 37 forks source link

Fixed o(n) complexity in consolidate() (now o(2 log n)) #5

Closed doktormerlin closed 5 years ago

doktormerlin commented 5 years ago

Consolidate used an array of the size of total_nodes to work, while you only need an array of the size of max degree (Which can't go higher than 2*log n). This made extract_min unneccessarily complex on big graphs.

I was able to improve the runtime on my Prim algorithm from 510 seconds to 5.6 seconds on a graph with 100.000 nodes and 200.000 edges with this small change.

alexcdot commented 5 years ago

It works for me as well, would be good to merge in