fibonacii_heap

斐波那契堆 是一种优先队列，其具有常数时间的 push 和平均对数时间的 pop。

在实践中，尽管它们具有更好的复杂度，但它们的速度比二叉堆慢

基准测试

斐波那契堆

fibonacii/insert/10     time:   [30.338 µs 30.585 µs 30.881 µs]
fibonacii/insert/11     time:   [63.569 µs 63.850 µs 64.167 µs]
fibonacii/insert/12     time:   [130.63 µs 131.12 µs 131.59 µs]
fibonacii/insert/13     time:   [266.99 µs 269.30 µs 271.98 µs]

fibonacii/pop/10        time:   [80.527 µs 81.042 µs 81.917 µs]
fibonacii/pop/11        time:   [202.34 µs 202.68 µs 203.14 µs]
fibonacii/pop/12        time:   [470.80 µs 471.32 µs 471.99 µs]
fibonacii/pop/13        time:   [1.0504 ms 1.0513 ms 1.0522 ms]

fibonacii/pop1/10       time:   [3.2672 µs 3.2844 µs 3.3007 µs]
fibonacii/pop1/11       time:   [6.8214 µs 6.9715 µs 7.1301 µs]
fibonacii/pop1/12       time:   [13.952 µs 14.476 µs 15.061 µs]
fibonacii/pop1/13       time:   [27.145 µs 27.806 µs 28.695 µs]

从这些数据中，我们可以看到

1. insert 是常数时间
2. pop 是平均对数时间
3. pop1 以线性时间执行（最坏情况示例）

二叉堆

binary/insert/10        time:   [2.5520 µs 2.5645 µs 2.5780 µs]
binary/insert/11        time:   [4.7433 µs 4.7686 µs 4.7959 µs]
binary/insert/12        time:   [9.1789 µs 9.2832 µs 9.4064 µs]
binary/insert/13        time:   [18.284 µs 18.368 µs 18.458 µs]

binary/pop/10           time:   [11.706 µs 11.736 µs 11.768 µs]
binary/pop/11           time:   [30.506 µs 30.577 µs 30.659 µs]
binary/pop/12           time:   [71.859 µs 71.883 µs 71.909 µs]
binary/pop/13           time:   [169.44 µs 169.58 µs 169.68 µs]

binary/pop1/10          time:   [48.880 ns 51.656 ns 53.981 ns]
binary/pop1/11          time:   [80.705 ns 86.656 ns 91.623 ns]
binary/pop1/12          time:   [94.414 ns 104.18 ns 112.66 ns]
binary/pop1/13          time:   [117.77 ns 130.94 ns 143.25 ns]

从这些数据中，我们可以看到

1. insert 是平均常数时间
2. pop 是对数时间
3. pop1 是对数时间
4. 与斐波那契堆相比，二叉堆更快