algorithm - 左派堆中排名的真​​正目的是什么？

Question

左派堆为每个节点维护一个键和一个等级。节点的等级是沿着到叶子的最短路径中的节点数。

整棵树需要维护两个属性：

1. node.key < node.left.key && node.key < node.right.key
2. node.left.rank >= node.right.rank

我可以理解第一个属性，因为它是一个堆并且很自然。

但是第二个属性的目的是什么？为什么我们需要保持右边比左边短？

为了平衡目的？

Answer 1

你引用的那篇文章说：

这些条件保证了左树是一个堆（key最小的元素在堆的顶部），并且通过右链接获得到叶子节点的最短路径

您询问的情况和

P.rank = 1 + min( (P.left).rank, (P.right).rank );

确保第二个。

因为融合操作是沿着正确的节点进行的，这保证了融合的对数性能。