Re: [理工] [资演］109台大电机对答案 joywilliamjo PTT批踢踢实业坊

楼主: joywilliamjo (joywilliamjoy) 2021-01-30 15:06:28

想问这张的第17题
照他上面order的定义是root的child树
那不是应该要是2^6=64吗？
有点看不懂为什么是21以及21怎么画出来的
感谢

作者: try66889 (小皮) 2021-01-30 15:43:00

字有点多用贴图的> <https://i.imgur.com/swEnPD1.jpg发现上面的图刚才手残画错>< 这个才对～https://i.imgur.com/fr3Wrb1.jpg不过最小我觉得应该是可以到19 @@ B4+B0+B1的话好像可以不知道有没有没考虑到的地方@@

作者: linnom (繁星) 2021-01-30 16:04:00

因为费波那契堆积在delete node时采用标记的方式，所以可以从64个node的多项式堆积切看看

作者: try66889 (小皮) 2021-01-30 16:11:00

https://i.imgur.com/Xfxx6vK.jpg可能我也不是很会画Fibonacci tree 所以画的比较丑QQ32+2是B5和B1吗OAO?Degree7最小我觉得应该是16+1+2+4

作者: linnom (繁星) 2021-01-30 16:29:00

https://i.imgur.com/y6WClki.jpg我是这样思考的～可能有更简单的方式，仅供参考抱歉好像写错哈哈我想看看找到了，绿色少看，已更正https://i.imgur.com/WMWPDT2.jpg

作者: try66889 (小皮) 2021-01-30 16:48:00

原Po抱歉，先不要理我，我发现刚才我有弄错的地方。Fibonacci heap 建立时若有剩下没同level可以merge的tree应该是直接link root起来，而不是我画的那样跑到大的tree下面,楼上l大解法应该比较正确，抱歉> <

作者: alex391a (麦基) 2021-01-30 17:02:00

https://i.imgur.com/86cmCVY.jpg我是这样写的能删的最多点剩下的点可以写出递回就变费式数列了圈起来是要删掉的

作者: linnom (繁星) 2021-01-30 17:08:00

喔喔喔楼上的方法好聪明，原来费波那契堆积名字是这样来的吗（？

楼主: joywilliamjo (joywilliamjoy) 2021-01-30 20:04:00

感谢大家

继续阅读