tem*_*def 11
直观地说,Fibonacci堆维护了一组不同顺序的树,在发生delete-min时合并它们.构建Fibonacci堆的希望是每棵树都包含大量节点.每棵树中的节点越多,需要在树中存储的树的数量就越少,因此在每个delete-min上花费的时间就越少.
同时,Fibonacci堆尝试尽可能快地进行减少键操作.要做到这一点,Fibonacci堆允许子树被"切掉"其他树并移回到根.这使得reduce-key更快,但是使每个树保持更少的节点(并且还增加了树的数量).因此,设计结构存在根本紧张.
为了实现这一点,Fibonacci堆中树的形状必须受到一定限制.直观地说,Fibonacci堆中的树是二叉树,允许丢失少量子节点.具体来说,Fibonacci堆中的每棵树最多只能丢失两个孩子,然后才能在后续步骤中对该树进行"重新处理".Fibonacci堆中的标记步骤允许数据结构计算到目前为止丢失了多少个孩子.未标记的节点没有丢失子节点,标记的节点丢失了一个子节点.一旦标记的节点丢失了另一个子节点,它就丢失了两个子节点,因此需要将其移回根节点进行重新处理.
许多入门算法教科书都记录了其工作原理的具体细节.这根本不起作用并不明显,数学有点棘手.
希望这提供了一个有用的直觉!
